A link to the cryptographic puzzle: https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt The puzzle is designed to foil parallelization by being iterative. The solution relied on...
The puzzle is designed to foil parallelization by being iterative. The solution relied on advanced in hardware, but an alternative solution which relies on a better squaring algorithm has almost been completed as well.
How did the author of the puzzle come up with the correct xor, without himself doing the 80 trillion successive squarings, which should have taken thirty years using the hardware of the time?
How did the author of the puzzle come up with the correct xor, without himself doing the 80 trillion successive squarings, which should have taken thirty years using the hardware of the time?
From the secondary article: They constructed n; they know the factorization, and worked backwards, giving a tedious way to "unlock" the cryptographic key.
From the secondary article:
There is no known way to perform this computation more quickly without knowing the factorization of n.
They constructed n; they know the factorization, and worked backwards, giving a tedious way to "unlock" the cryptographic key.
You are! I just wasn't quite smart enough to explain it well the first time. If you consider a different factorization problem, it's a bit more understandable. Let's say I wanted you to give me...
I wish I were smart enough to know what that meant.
You are! I just wasn't quite smart enough to explain it well the first time.
If you consider a different factorization problem, it's a bit more understandable. Let's say I wanted you to give me the prime factorization of 651571 - it's a potentially difficult problem that you likely cannot do off the top of your head. But I could give you a few clues based on my knowledge of how I put together this problem:
one of the factors is a three digit number that starts with 7
one of the factors is a three digit number that starts with 9
Given that information and a calculator, you could find a solution in about 5 minutes.
This is analogous to the MIT problem, albeit at a much smaller scale. I've chosen my "n" to be 651571, and I've constructed it very simply (I multiplied two random prime numbers). I then gave a very generous clue as to how to identify the prime factorization.
The MIT group chose their n much more carefully (actually I put a second link up to exactly how they did it in a comment chain above this) and then gave a very ungenerous clue, which doesn't identify things anywhere near as quickly.
I am afraid we will have to simply agree to disagree :) I read the link here: https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt I still have no idea how they calculated Z without...
You are!
I am afraid we will have to simply agree to disagree :)
A link to the cryptographic puzzle: https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
The puzzle is designed to foil parallelization by being iterative. The solution relied on advanced in hardware, but an alternative solution which relies on a better squaring algorithm has almost been completed as well.
How did the author of the puzzle come up with the correct xor, without himself doing the 80 trillion successive squarings, which should have taken thirty years using the hardware of the time?
From the secondary article:
They constructed n; they know the factorization, and worked backwards, giving a tedious way to "unlock" the cryptographic key.
I wish I were smart enough to know what that meant.
You are! I just wasn't quite smart enough to explain it well the first time.
If you consider a different factorization problem, it's a bit more understandable. Let's say I wanted you to give me the prime factorization of 651571 - it's a potentially difficult problem that you likely cannot do off the top of your head. But I could give you a few clues based on my knowledge of how I put together this problem:
Given that information and a calculator, you could find a solution in about 5 minutes.
This is analogous to the MIT problem, albeit at a much smaller scale. I've chosen my "n" to be 651571, and I've constructed it very simply (I multiplied two random prime numbers). I then gave a very generous clue as to how to identify the prime factorization.
The MIT group chose their n much more carefully (actually I put a second link up to exactly how they did it in a comment chain above this) and then gave a very ungenerous clue, which doesn't identify things anywhere near as quickly.
I am afraid we will have to simply agree to disagree :)
I read the link here: https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
I still have no idea how they calculated Z without squaring N 80 trillion times.