0

Let $x,y,n$ be $1234567809,12345,9087654321$.

My laptop can perform $1$ $64$-bit integer 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=2672633475\pmod n$

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

Community
  • 1
Heyo
  • 167
  • 1
    You don't need to do any calculations with $10^{45}$-digit numbers. Do all the calculations mod $n$ and none of the results​ can exceed $n$. – MJD Apr 24 '17 at 14:34
  • @MJD: Well, intermediate results will usually do exceed $n$, for example when you use ordinary multiplicaton and mod like a·b=(a*n) mod n. You can of course implemend multiplication by hand and then intermediate results won't exceed $2n$. – emacs drives me nuts Sep 02 '22 at 20:45

2 Answers2

0

Let's assume that the time needed to perform a 64bit multiplication is also 1 microsecond. Then $x^y \pmod n$ can be computed in $\log n$ operations of multiplying and dividing modulo with the help of exponentiation by squaring.

Second example: look at prime divisors of $n$. What can you say?

enedil
  • 1,710
0

ad 1: In base 2, $y$ reads:· $$y=12345 = 11\,0000\,0011\,1001_2$$ i.e. in order to perform $x^y\bmod n$ you need

  • $5=\operatorname{popcount}(y)-1\quad$ times (Mul + Mod)
  • $13 = \operatorname{bitlen}(y) - 1\quad$ times (Square + Mod)

assuming you start expansion at the most significant bit of $y$. Hence the number of modular operations needed is:

$$18\times\text{Mul}+18\times\text{Mod}$$

under the assumption that squaring performs no better than multiplying. Notice however that $$n = 9\,087\,654\,321 \geqslant 2^{32}=4\,294\,967\,296$$

and therefore when you are multiplying two numbers in $[0,n)$, then the result will not fit in a 64-bit register in general. (Using signed residues in $[-n/2, n/2]$ won't help). Using 70-bit arithmetic would be sufficient though.

For part 2 of the question depends on what algorithm you are using. You want to compute the discrete logarithm, which is costly.

emacs drives me nuts
  • 10,390
  • 2
  • 12
  • 31