cómo minimizar y en la expresión $(x^y) \bmod{n}$ ?

Question

Consideremos $x^y\bmod{n}$ .

$y$ comparando con $x$ y $n$ es muy grande. ¿Cómo podemos minimizar $y$ tal que $(x^{\mathrm{newy}}) \bmod{n}$ da el mismo resultado que $(x^y) \bmod{n}$ ? ¿Cuáles son las normas?

Answer 1

Primero computa $z = (x^y \mod n)$ utilizando el método binario (también llamado cuadrar y multiplicar ). El esfuerzo computacional es $O(\lg_2 y)$ . A continuación, calcule los productos parciales $x, x^2, ...$ hasta que consigas $x^e = z\mod n$ . $e$ es el exponente mínimo buscado. El esfuerzo es $O(n)$ porque hay como máximo $n$ diferentes productos.

Aquí está el algoritmo en 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