Let's consider $x^y\bmod{n}$.
$y$ comparing to $x$ and $n$ is veeeeeeeery big. How can we minimize $y$ such that $(x^{\mathrm{newy}}) \bmod{n}$ gives same result as $(x^y) \bmod{n}$? What are the rules?
Let's consider $x^y\bmod{n}$.
$y$ comparing to $x$ and $n$ is veeeeeeeery big. How can we minimize $y$ such that $(x^{\mathrm{newy}}) \bmod{n}$ gives same result as $(x^y) \bmod{n}$? What are the rules?
First compute $z = (x^y \mod n)$ using the binary method (also called square and multiply). The computational effort is $O(\lg_2 y)$. Then compute the partial products $x, x^2, ...$ until you get $x^e = z\mod n$. $e$ is the searched minimal exponent. The effort is $O(n)$ because there are at most $n$ different products.
Here is the algorithm in Python:
def binary(a): # returns binary represention of a, e.g. binary(6) = "110" b = "" while (a > 0): b = str(a & 1) + b a = a >> 1 return b def minExp(x, y, n): # compute z = x^y mod n, effort O(lg y): b = binary(y) L = len(b) z = 1 for i in range(0, L): # O(lg y) steps z = z * z if b[i] == '1': # i-th bit of b is set z = z * x z = z % n # find minimal exponent (effort O(n)): product = 1 e = 0 # minimal exponent while product != z: product = (product * x) % n e += 1 return e