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?

  • $\begingroup$ I'm pretty sure this isn't "calculus", is it? I edited the tags but roll back if this is indeed from some esoteric calculus problem ;) $\endgroup$
    – Josh Chen
    Aug 2 '11 at 10:21
  • $\begingroup$ Thanks sir, didn't know in really what section place it $\endgroup$ Aug 2 '11 at 10:25
  • $\begingroup$ If $x$ is relatively prime to $n$, and it's multiplicative order mod $n$ is $ord(x)$, then you can add/subtract integer multiples of $ord(x)$ from $y$ without affecting the expression. (BTW is this homework?) $\endgroup$
    – Srivatsan
    Aug 2 '11 at 10:31
  • 1
    $\begingroup$ If $x$ is relatively prime to $n$, you can always reduce $y$ modulo $\varphi(n)$ (Euler's $\phi$). Of course, you may not know $\varphi(n)$ ahead of time (e.g., if $n$ is a product of two large but unknown primes). $\endgroup$ Aug 2 '11 at 10:42
  • 2
    $\begingroup$ @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. $\endgroup$ Aug 2 '11 at 10:57

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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