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?

$\endgroup$
  • $\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$ – Krzysztof Lewko 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$ – Arturo Magidin 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$ – Arturo Magidin Aug 2 '11 at 10:57
2
$\begingroup$

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
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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