Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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 ;) –  Josh Chen Aug 2 '11 at 10:21
    
Thanks sir, didn't know in really what section place it –  Chris 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
1  
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
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. –  Arturo Magidin Aug 2 '11 at 10:57
show 3 more comments

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.