2
$\begingroup$

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?

  • 2
    @Chris: If $x$ is not relatively prime to $n$, write $x=dz$ with $d=\gcd(n,x)$. Then $x^y = d^yz^y$; you can consider $z^y\bmod {n/d}$, which is the relatively prime case, and consider $d^y$ modulo $n$ separately; either $d^k\equiv 0\pmod{n}$ for sufficiently large $d$, in which case $x^y\equiv 0\pmod{n}$ for sufficiently large $d$, or else it will cycle among nonzero values and you can reduce. Then handle each part separately.2011-08-02

1 Answers 1

2

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