algorithm math number-theory

algorithm - encontrando un ^ b ^ c ^… mod m



math number-theory (6)

Me gustaría calcular:

a b c d . . . mod m

¿Conoces alguna forma eficiente ya que este número es demasiado grande pero a, b, c, ... y m caben en un simple int de 32 bits?

¿Algunas ideas?

Advertencia: esta pregunta es diferente de encontrar un mod b mod.

También tenga en cuenta que a b c no es lo mismo que (a b ) c . El último es igual a un bc . La exponencia es asociativa por derecho.

La respuesta no contiene la prueba matemática formal completa de la corrección. Supuse que es innecesario aquí. Además, sería muy ilegible en SO, (no MathJax por ejemplo).
Usaré (solo un poco) un algoritmo específico de factorización prima . No es la mejor opción, pero sí suficiente.

tl; dr

Queremos calcular a^x mod m . Usaremos la función modpow(a,x,m) . Descrito abajo.

  1. Si x es lo suficientemente pequeño (no es una forma exponencial o existe p^x | m ) simplemente calcúlelo y devuélvalo
  2. Divida en primos y calcule p^x mod m por separado para cada primo, usando la función modpow
    1. Calcule c'' = gcd(p^x,m) y t'' = totient(m/c'')
    2. Calcule w = modpow(x.base, x.exponent, t'') + t''
    3. Guardar pow(p, w - log_p c'', m) * c'' en A tabla
  3. Múltiples todos los elementos de A y regresan módulo m

Aquí el poder debería verse como el poder del pitón.

Problema principal:

Debido a que la mejor respuesta actual es solo sobre el caso especial gcd(a,m) = 1 , y OP no consideró este supuesto en cuestión, decidí escribir esta respuesta. También usaré el teorema totient de Euler . Citando Wikipedia:

Teorema totient de Euler :
Si n y a son enteros positivos coprime, entonces donde φ (n) es la función totient de Euler .

Los numbers are co-prime supuestos numbers are co-prime son muy importantes, como muestra Nabb en los comentarios . Por lo tanto, primero debemos asegurarnos de que los números sean primarios. (Para mayor claridad, supongamos que x = b^(c^...) .) Porque , dónde podemos factorizar a , y calcular por separado q1 = (p1^alpha)^x mod m,q2 = (p2^beta)^x mod m... y luego calcular la respuesta de manera sencilla (q1 * q2 * q3 * ... mod m) . El número tiene a lo sumo o(log a) factores primos, por lo que estaremos obligados a realizar como máximo o(log a) cálculos.

De hecho, no tenemos que dividirnos en todos los factores primos de a (si no todos se producen en m con otros exponentes) y podemos combinarlos con el mismo exponente, pero hasta ahora no es digno de mención.

Ahora eche un vistazo a (p^z)^x mod m problema, donde p es primo. Note alguna observación importante:

Si a,b son enteros positivos más pequeños que m y c es algún entero positivo y entonces la verdad es la oración .

Usando la observación anterior, podemos recibir una solución para el problema real . Podemos calcular fácilmente gcd((p^z)^x, m) . Si x * z son grandes, es un número la cantidad de veces que podemos dividir m por p . Sea m'' = m /gcd((p^z)^x, m) . (Aviso (p^z)^x = p^(z*x) .) Sea c = gcd(p^(zx),m) . Ahora podemos (ver abajo) calcular fácilmente w = p^(zx - c) mod m'' usando el teorema de Euler, ¡porque estos números son primarios! Y luego, usando la observación anterior, podemos recibir p^(zx) mod m . Desde la suposición anterior, wc mod m''c = p^(zx) mod m , por lo que la respuesta por ahora es p^(zx) mod m = wc w,c son fáciles de calcular.

Por lo tanto podemos calcular fácilmente a^x mod m .

Calcula a^x mod m usando el teorema de Euler

Ahora supongamos que a,m son co-prime. Si queremos calcular a^x mod m , podemos calcular t = totient(m) y observar a^x mod m = a^(x mod t) mod m . Puede ser útil, si x es grande y conocemos solo la expresión específica de x , como por ejemplo x = 7^200 .

Mira el ejemplo x = b^c . podemos calcular t = totient(m) y x'' = b^c mod t usando exponentiation por algoritmo de cuadratura en Θ(log c) tiempo. Y después (usando el mismo algoritmo) a^x'' mod m , que es igual a la solución.

Si x = b^(c^(d^...) lo resolveremos de forma recursiva. Primero, calcularemos t1 = totient(m) , después de t2 = totient(t1) y así sucesivamente. Por ejemplo, tome x=b^(c^d) . Si t1=totient(m) , a^x mod m = a^(b^(c^d) mod t1) , y podemos decir b^(c^d) mod t1 = b^(c^d mod t2) mod t1 , donde t2 = totient(t1) . todo lo que estamos calculando usando la exponenciación mediante el algoritmo de cuadratura Nota : si algún totient no es co-primo al exponente, es necesario usar el mismo truco, como en el problema principal (de hecho, deberíamos olvidar que es exponente y el problema resuelto recursivamente, como en el problema principal). En el ejemplo anterior, si t2 no es primo con c, tenemos que usar este truco.

Calcular φ(n)

Note hechos simples:

  1. si gcd(a,b)=1 , entonces φ(ab) = φ(a)*φ(b)
  2. si p es primo φ(p^k)=(p-1)*p^(k-1)

Por lo tanto, podemos factorizar n (ak. n = p1^k1 * p2^k2 * ... ) y calcular por separado φ(p1^k1),φ(p2^k2),... usando el hecho 2. Luego combine esto usando hecho 1. φ(n)=φ(p1^k1)*φ(p2^k2)*...

Vale la pena recordar que, si calculamos totient repetidamente, es posible que queramos usar Tamiz de Eratóstenes y guardar números primos en la tabla. Se reducirá la constante.

Ejemplo de python : (es correcto, por la misma razón que este algoritmo de factorización )

def totient(n) : # n - unsigned int result = 1 p = 2 #prime numbers - ''iterator'' while p**2 <= n : if(n%p == 0) : # * (p-1) result *= (p-1) n /= p while(n%p == 0) : # * p^(k-1) result *= p n /= p p += 1 if n != 1 : result *= (n-1) return result # in O(sqrt(n))

Caso: a b c mod m

Porque en realidad está haciendo lo mismo muchas veces, creo que este caso le mostrará cómo resolverlo en general.
En primer lugar, tenemos que dividir a en primos poderes. La mejor representación será par <number, exponent> .
Ejemplo de c ++ 11 :

std::vector<std::tuple<unsigned, unsigned>> split(unsigned n) { std::vector<std::tuple<unsigned, unsigned>> result; for(unsigned p = 2; p*p <= n; ++p) { unsigned current = 0; while(n % p == 0) { current += 1; n /= p; } if(current != 0) result.emplace_back(p, current); } if(n != 1) result.emplace_back(n, 1); return result; }

Después de dividir, tenemos que calcular (p^z)^(b^c) mod m=p^(z*(b^c)) mod m para cada par. Primero debemos verificar, si p^(z*(b^c)) | m p^(z*(b^c)) | m . Si, sí, la respuesta es solo (p ^ z) ^ (b ^ c), pero solo es posible en el caso de que z,b,c sean muy pequeños. Creo que no tengo que mostrar código de ejemplo.
Y finalmente si p^(z*b^c) > m tenemos que calcular la respuesta. Primero, debemos calcular c'' = gcd(m, p^(z*b^c)) . Después podemos calcular t = totient(m'') . y (z*b^c - c'' mod t) . Es una forma fácil de obtener una respuesta.

function modpow(p, z, b, c, m : integers) # (p^z)^(b^c) mod m c'' = 0 m'' = m while m'' % p == 0 : c'' += 1 m'' /= p # now m'' = m / gcd((p^z)^(b^c), m) t = totient(m'') exponent = z*(b^c)-c'' mod t return p^c'' * (p^exponent mod m'')

Y debajo del ejemplo de trabajo de Python :

def modpow(p, z, b, c, m) : # (p^z)^(b^c) mod m cp = 0 while m % p == 0 : cp += 1 m /= p # m = m'' now t = totient(m) exponent = ((pow(b,c,t)*z)%t + t - (cp%t))%t # exponent = z*(b^c)-cp mod t return pow(p, cp)*pow(p, exponent, m)

Usando esta función, podemos calcular fácilmente (p^z)^(b^c) mod m , después de que solo tengamos que multiplicar todos los resultados ( mod m ), también podemos calcular todo de forma continua. Ejemplo a continuación. (Espero no haber cometido un error, escribiendo). Solo la suposición, b, c son lo suficientemente grandes ( b^c > log(m) ak. Cada p^(z*b^k) no divide m ), Es un simple cheque y no veo el punto de desordenar con él.

def solve(a,b,c,m) : # split and solve result = 1 p = 2 # primes while p**2 <= a : z = 0 while a % p == 0 : # calculate z a /= p z += 1 if z != 0 : result *= modpow(p,z,b,c,m) result %= m p += 1 if a != 1 : # Possible last prime result *= modpow(a, 1, b, c, m) return result % m

Parece que funciona.
DEMO y es correcto !

  1. Como para cualquier relación a=x^y , la relación es invariante con respecto a la base numérica que está utilizando (base 2, base 6, base 16, etc.).

  2. Dado que la operación mod N es equivalente a extraer el dígito menos significativo (LSD) en la base N

  3. Dado que el LSD del resultado A en la base N solo puede verse afectado por el LSD de X en la base N, y no los dígitos en lugares más altos. (por ejemplo, 34 * 56 = 30 * 50 + 30 * 6 + 50 * 4 + 4 * 5 = 10 * (3 + 50 + 3 * 6 + 5 * 4) + 4 * 6)

Por lo tanto, a partir de LSD(A)=LSD(X^Y) podemos deducir

LSD(A)=LSD(LSD(X)^Y)

Por lo tanto

A mod N = ((X mod N) ^ Y) mod N

y

(X ^ Y) mod N = ((X mod N) ^ Y) mod N)

Por lo tanto, puede hacer la modificación antes de cada paso de potencia, lo que mantiene su resultado en el rango de enteros.

Esto supone que a no es negativo, y para cualquier x ^ y, a ^ y <MAXINT

Esta respuesta responde a la pregunta incorrecta. (alex)

La Exposiciónción Modular es una forma correcta de resolver este problema, aquí hay una pequeña pista:

Para encontrar a b c d % m, debes comenzar calculando a% m, luego a b % m, luego a b c % my luego a b c d % m ... (tienes la idea)

Para encontrar un b % m, básicamente necesitas dos ideas: [Sea B = piso (b / 2)]

  • a b = (a B ) 2 si b es par O a b = (a B ) 2 * a si b es impar.
  • (X * Y)% m = ((X% m) * (Y% m))% m
    (% = mod)

    Por lo tanto,
    si b es par
    a b % m = (a B % m) 2 % m
    o si b es impar
    a b % m = (((a B % m) 2 ) * (a% m))% m

    Entonces, si conoces el valor de B , puedes calcular este valor.

    Para encontrar una B , aplica un enfoque similar, dividiendo B hasta que alcances 1.

    Por ejemplo, para calcular 16 13 % 11:

    16 13 % 11 = (16% 11) 13 % 11 = 5 13 % 11 = (5 6 % 11) * (5 6 % 11) * (5% 11) <---- (I)

    Para encontrar 5 6 % 11:
    5 6 % 11 = ((5 3 % 11) * (5 3 % 11))% 11 <---- (II)
    Para encontrar 5 3 % 11:
    5 3 % 11 = ((5 1 % 11) * (5 1 % 11) * (5% 11))% 11
    = ((((5 * 5)% 11) * 5)% 11 = ((25% 11) * 5)% 11 = (3 * 5)% 11 = 15% 11 = 4
    Conectando este valor a (II) da
    5 6 % 11 = ((((4 * 4)% 11) * 5)% 11 = ((16% 11) * 5)% 11 = (5 * 5)% 11 = 25% 11 = 3
    Conectando este valor a (I) da
    5 13 % 11 = ((3% 11) * (3% 11) * 5)% 11 = ((9% 11) * 5)% 11 = 45% 11 = 4

    De esta manera 5 13 % 11 = 4
    Con esto puedes calcular cualquier cosa del 5 13 % 11 y así sucesivamente ...

    • La respuesta de Tacet es buena, pero hay simplificaciones sustanciales posibles.

    Los poderes de x, mod m, son preperiódicos. Si x es relativamente primo a m, las potencias de x son periódicas, pero incluso sin esa suposición, la parte anterior al período no es larga, como máximo el máximo de los exponentes en la factorización prima de m, que es a lo sumo log_2 m . La duración del período divide phi (m) y, de hecho, lambda (m), donde lambda es la función de Carmichael , el orden multiplicativo máximo mod m. Esto puede ser significativamente menor que phi (m). Lambda (m) se puede calcular rápidamente a partir de la factorización prima de m, tal como puede hacerlo phi (m). Lambda (m) es el GCD de lambda (p_i ^ e_i) sobre todas las potencias primarias p_i ^ e_i en la factorización prima de m, y para las potencias primarias impares, lambda (p_i ^ e_i) = phi (p_i ^ e ^ i). lambda (2) = 1, lamnda (4) = 2, lambda (2 ^ n) = 2 ^ (n-2) para potencias mayores de 2.

    Defina modPos (a, n) para que sea el representante de la clase de congruencia de a en {0,1, .., n-1}. Para un no negativo a, esto es solo un% n. Para un negativo, por alguna razón,% n se define como negativo, por lo que modPos (a, n) es (a% n) + n.

    Defina modMin (a, n, min) para que sea el entero menos positivo congruente con un mod n que sea al menos min. Para un positivo, puede calcular esto como min + modPos (a-min, n).

    Si b ^ c ^ ... es más pequeño que log_2 m (y podemos verificar si esta desigualdad se mantiene tomando logaritmos de forma recursiva), entonces simplemente podemos calcular a ^ b ^ c ^ ... De lo contrario, a ^ b ^ c ^ ... mod m = a ^ modMin (b ^ c ^ ..., lambda (m), [log_2 m])) mod m = a ^ modMin (b ^ c ^ ... mod lambda (m), lambda (m), [log_2 m]).

    Por ejemplo, supongamos que queremos calcular 2 ^ 3 ^ 4 ^ 5 mod 100. Tenga en cuenta que 3 ^ 4 ^ 5 solo tiene 489 dígitos, por lo que esto es factible por otros métodos, pero es lo suficientemente grande como para que no quiera calcular directamente Sin embargo, por los métodos que proporcioné aquí, puedes calcular 2 ^ 3 ^ 4 ^ 5 mod 100 a mano.

    Desde 3 ^ 4 ^ 5> log_2 100,

    2^3^4^5 mod 100 = 2^modMin(3^4^5,lambda(100),6) mod 100 = 2^modMin(3^4^5 mod lambda(100), lambda(100),6) mod 100 = 2^modMin(3^4^5 mod 20, 20,6) mod 100.

    Calculemos 3 ^ 4 ^ 5 mod 20. Desde 4 ^ 5> log_2 20,

    3^4^5 mod 20 = 3^modMin(4^5,lambda(20),4) mod 20 = 3^modMin(4^5 mod lambda(20),lambda(20),4) mod 20 = 3^modMin(4^5 mod 4, 4, 4) mod 20 = 3^modMin(0,4,4) mod 20 = 3^4 mod 20 = 81 mod 20 = 1

    Podemos enchufar esto en el cálculo anterior:

    2^3^4^5 mod 100 = 2^modMin(3^4^5 mod 20, 20,6) mod 100 = 2^modMin(1,20,6) mod 100 = 2^21 mod 100 = 2097152 mod 100 = 52.

    Tenga en cuenta que 2 ^ (3 ^ 4 ^ 5 mod 20) mod 100 = 2 ^ 1 mod 100 = 2, lo cual no es correcto. No se puede reducir a la parte preperiódica de los poderes de la base.

    Observa el comportamiento de A^X mod M medida que X aumenta. Eventualmente debe entrar en un ciclo. Supongamos que el ciclo tiene una longitud P y comienza después de N pasos. Entonces X >= N implica que A^X = A^(X+P) = A^(X%P + (-N)%P + N) (mod M) . Por lo tanto, podemos calcular A^B^C calculando y=B^C, z = y < N ? y : y%P + (-N)%P + N, return A^z (mod m) y=B^C, z = y < N ? y : y%P + (-N)%P + N, return A^z (mod m) .

    Tenga en cuenta que podemos aplicar recursivamente esta estrategia en el árbol de poder, porque la ecuación derivada tiene un exponente < M o un exponente que involucra una torre de exponentes más pequeña con un dividendo más pequeño.

    La única pregunta es si puede calcular de manera eficiente N y P dados A y M Observe que sobreestimar N está bien. Podemos poner N en M y las cosas funcionarán. P es un poco más difícil. Si A y M son primos diferentes, entonces P=M-1 . Si A tiene todos los factores primos de M , entonces nos quedamos atascados en 0 y P=1 . Lo dejo como un ejercicio para resolverlo, porque no sé cómo.

    ///Returns equivalent to list.reverse().aggregate(1, acc,item => item^acc) % M func PowerTowerMod(Link<int> list, int M, int upperB = M) requires M > 0, upperB >= M var X = list.Item if list.Next == null: return X var P = GetPeriodSomehow(base: X, mod: M) var e = PowerTowerMod(list.Next, P, M) if e^X < upperB then return e^X //todo: rewrite e^X < upperB so it doesn''t blowup for large x return ModPow(X, M + (e-M) % P, M)

    a b c mod m = a b c mod n mod m, donde n = φ (m) función totient de Euler .

    Si m es primo, entonces n = m-1.

    Edición: como señaló Nabb, esto solo es válido si a es coprime to m. Así que tendrías que revisar esto primero.