Let $x,y,n$ be $1234567809, 12345, 9087654321$. My laptop can perform 1 64-bit mod operation in 1 microsecond. Estimate the number of seconds needed for each of the following:

  1. Find $x^y \pmod{n}$
  2. Find $t$ such that $x^t \equiv 2672633475 \pmod{n}$.

I guess around 10^45 digits, am I right and how do I calculate time from here?

  • 4
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help with conceptual questions but just answering homework-style exercises for you is unlikely to really help you. $\endgroup$ – David Richerby Apr 24 '17 at 16:08
  • 2
    $\begingroup$ Welcome to Computer Science! Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Apr 24 '17 at 18:38

Hint: If you want to calculate $1234567809^{12345}$ modulo 9087654321, you do not start by calculating $1234567809^{12345}$. After every operation, you reduce the result modulo 9087654321.

Hint 2: You can calculate $x^{12345}$ with about 25 multiplications, not 12345.

Hint 3: Probably less than 10 seconds for the last question if you find factors of n first, and use brute force and a tiny bit of maths (but that answer won't do you any good if you can't find that tiny bit of maths).


Not the answer you're looking for? Browse other questions tagged or ask your own question.