magic dlog

A server asks you to input a modulus (here required to be prime, but relaxed to any number in magic rsa), an exponent , and then a number such that .

So the obvious approach is to make smooth such that we can construct after fixing (and consequently ).

There’s one more caveat, in that the upper bits of has to match some given (random) ~136-bit pattern . I’m not sure of any direct construction of smooth numbers on a form like , but since is “small” we can hope that it itself1 is smooth-ish and just multiply it with smooth numbers that is “almost” . I chose to find the acceptably smooth numbers on the form (which was easy as these “Mersenne numbers” tend to be rich in divisors, especially for composite exponents) and then just pick numbers from this list with exponents that summed to 248. The -factor will need to be adjusted upward to make the upper bits match. In the end we have a lot of candidates and once we find such a prime we’re all set.

Pick some primitive root , compute and do a discrete log using all the factors of .

A pretty good Euler hack problem overall, I thought.

  1. Or really the adjusted that we’ll end up actually using.