"Based on Moore’s law and how long it took to run the squaring operation in 1999, Rivest estimated that computing the answer to the puzzle should take approximately 35 years."
So how did Rivest create the puzzle back then in the first place, without taking 35 years to generate it?
The asymmetry of three things is essentially what secures of a lot of cryptography:
1. multiplying two large prime numbers together (easy)
2. Factoring the result without knowledge of those primes (extremely difficult)
3. Factoring the result with knowledge of one of the primes (easy)
Those properties are essentially what make up the foundation of a lot of public key crypto.
For this puzzle, knowing the factorisation of n allowed a shortcut to quickly generate the puzzle, but without that factorisation it required squaring numbers 79,685,186,856,218 times sequentially so parallelism isn't a help.
So how did Rivest create the puzzle back then in the first place, without taking 35 years to generate it?