I have the following formula: $$d \cdot 65537 \equiv 1 \pmod{9999...}$$ I have to find $d$, even in case the modulo is 30 digits long.

This means I am not supposed to brute force it, but I haven't yet come across to anything that would help me with this matter.

I thought cryptography uses modulo exactly because this problem is hard to solve. Can you give a hint on how to approach this problem? I think the 65537 prime is supposed to help in some way, but I'm not sure how.

  • $\begingroup$ Your solution can't be unique: if $d_1$ is such a solution, then so is $d_2=d_1+9999999...$. $\endgroup$ – probablystuck May 17 at 15:16
  • 1
    $\begingroup$ Welcome to Math Stack Exchange. Note $2^{16}=65536$ $\endgroup$ – J. W. Tanner May 17 at 15:17
  • $\begingroup$ The Euclidean algoirthm works well, even if one of the terms is quite large. $\endgroup$ – lulu May 17 at 15:18
  • $\begingroup$ So you need to find such $d$ so that $d\left(2^{16}+1\right) + 1 = 10^k$ for some integer $k$ $\endgroup$ – gt6989b May 17 at 15:19
  • 2
    $\begingroup$ To be clear: $30$ digits is not especially big for the euclidean algorithm. wolfram alpha is able to handle it almost instantaneously. $\endgroup$ – lulu May 17 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.