Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 ;) – chiaroscuro Aug 2 '11 at 10:21
Thanks sir, didn't know in really what section place it – Spinach Aug 2 '11 at 10:25
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?) – Srivatsan Aug 2 '11 at 10:31
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). – Arturo Magidin Aug 2 '11 at 10:42
@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. – Arturo Magidin Aug 2 '11 at 10:57
up vote 2 down vote accepted

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
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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