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.

The actual code to generate the puzzle was in the original puzzle description at https://people.csail.mit.edu/rivest/lcs35-puzzle-description... .