2 ms·
From the actual problem description: Note that the puzzle can be solved by performing t successive squarings modulo n, beginning with the value 2. That is, se
by adastra22 3y ago
From the actual problem description:
Note that the puzzle can be solved by performing t successive
squarings modulo n, beginning with the value 2. That is, set
W(0) = 2
W(i+1) = (W(i) ^ 2) (mod n) for i=1, 2, ...
and compute W(t).
There is no known way to perform this computation more quickly than to
perform the t squarings sequentially, unless the factorization of n is
known.
- lucb1e 3y agoAh! Thanks. That immediately answers the second thing I was wondering about, since 2k RSA keys are still deemed safe (if barely / not for secrets that need to last a long time into the future)
- adastra22 3y agoYeah the cost of breaking the time lock is presumably less than breaking the order of the group.
- TacticalCoder 3y agoIn addition to what GP answered: note that I didn't crack anything. I just really did all the 79 trillion sequential computation needed to find the solution. That's the really need thing: you can encode the problem in a split second and yet decide how many sequential steps are needed to find the solution.