¿Hay atajos para evaluar [matemáticas] a ^ b \! \! \! \! \ pmod {n} [/ math] cuando [math] \ gcd (a, n) = 1 [/ math]?

Answer 1

Lo siguiente es útil para saber al hacer aritmética modular que involucra números primos y / o primos:

• Teorema “Pequeño” de Fermat [1]: Si [math] p [/ math] es un número primo, entonces para cualquier número entero [math] a [/ math], sostiene que [math] a ^ {p} \ equiv a \ mod {p} [/ math]. Además, si [math] a [/ math] es co-prime con [math] p [/ math] (es decir, [math] \ gcd (a, p) = 1 [/ math]) , sostiene que [ matemáticas] a ^ {p-1} \ equiv 1 \ mod p [/ matemáticas].
• Función Totient / Phi de Euler [2, 3]: Si [math] \ gcd (a, n) = 1 [/ math], entonces sostiene que [math] a ^ {\ varphi (n)} \ equiv 1 \ mod n [/ math], donde [math] \ varphi (n) [/ math] es el número de enteros positivos menores o iguales a [math] n [/ math] que son primos con [math] n [/ matemáticas]. [matemáticas] \ varphi (1) = 1 [/ matemáticas] porque 1 es primo consigo mismo; [matemática] \ varphi (9) = 6 [/ matemática] porque 1, 2, 4, 5, 7, 8 son primos con 9; [math] \ varphi (p) = p – 1 [/ math] para un número primo [math] p [/ math] y, por lo tanto, el pequeño teorema de Fermat es solo un caso especial del teorema de Euler. [matemáticas] \ varphi (n) = n (1 – \ frac {1} {p_1}) (1 – \ frac {1} {p_2})… (1 – \ frac {1} {p_r}) [/ math ] donde [math] p_1, p_2, … p_r [/ math] son ​​todos los números primos que dividen [math] n [/ math]. Dada la redacción de esta pregunta, el teorema de Euler produce [matemáticas] a ^ b \ equiv a ^ {b \! \! \! \! \ mod \ varphi (n)} \! \! \! \! \ mod n [/ math] como menciona Sam Tetruashvili.

[1]: http://en.wikipedia.org/wiki/Fer…
[2]: http://en.wikipedia.org/wiki/Eul…
[3]: http://mathworld.wolfram.com/Tot…

Answer 2

En este caso, el teorema de Euler dice que [matemáticas] a ^ b \ equiv a ^ {b \! \! \! \! \ mod \ varphi (n)} \! \! \! \! \ mod n [/ math], donde [math] \ varphi (n) = | \ mathbb {Z} ^ {*} _ {n} | [/ math], es decir, el número de enteros entre [math] 0 [/ math] y [math] n – 1 [/ math] que son relativamente primos para [math] n [/ math].

Answer 3

Estos son buenos métodos si se conoce la factorización y / o primalidad de [math] n [/ math]. Sin embargo, si no es así, entonces podemos calcular [matemática] a ^ b \ mod n [/ matemática] de manera eficiente utilizando exponenciación modular.

Usamos dos hechos útiles:
1. [matemáticas] a ^ 2 \ mod n = (a ^ 2 \ mod n) \ mod n [/ matemáticas]
2. Si [math] b [/ math] es par, entonces [math] a ^ b \ mod n = (a ^ 2) ^ {b / 2} \ mod n [/ math]. Si [math] b [/ math] es impar, entonces [math] a ^ b \ mod n = a (a ^ 2) ^ {\ frac {b-1} {2}} \ mod n [/ math].

Repetir la reducción del exponente y el cálculo de la base arroja el resultado. Esto funciona independientemente de [math] gcd (a, n) [/ math].