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).

| cite | improve this answer | |

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