¿Cómo puedo encontrar el menor $n$ que $a^n \equiv 1 \pmod{b}$?

Question

Esto es en su mayoría relacionados con haciendo grandes exponenciación modular con la mano. Por ejemplo, un problema que estaba haciendo era buscar los 3 últimos dígitos de $7^{9729}$; es decir, encontrar $7^{9729}\bmod{1000}$.

Con el simple concepto por el teorema de Euler, me encontré con que $7^{400}\equiv 1\pmod{1000}$, ya que el $\varphi(1000)=400$. El uso del teorema de Carmichael, me encontré con un menor número, $7^{100}\equiv 1\pmod{1000}$$\lambda(1000)=100$. Ahora, de forma manual el multiplicando, me encontré con que $7^{20}\equiv 1 \pmod{1000}$, y que es la primera $n$ por que lo que es verdadero, lo que significa que sólo tiene que encontrar $7^9 \bmod{1000}$, con lo que la respuesta 607.

Hay un camino para llegar a esta respuesta sin multiplicando cada momento para cada número de recibo? Por ejemplo, podría hacer algo como $13^{12937}\bmod{1000}$ sin sentados alrededor de modding a cabo múltiplos de $13^4$? (Sé que la primera $n$ 13 100, por lo que no menos que el uso del teorema de Carmichael, pero quiero saber si hay otras maneras de encontrar los números menores que las dadas por Carmichael del teorema)

Answer 1

Si $\rm\: gcd(a,10)=1\:$, entonces el orden de $\rm\: a\:$ $\:\mathbb Z/1000 \:$ debe ser un divisor de a $100 = \lambda(1000)$. Usted puede calcular el orden de forma sencilla y rápida por la computación en la orden de $\rm a^2, a^4, a^5, a^{10}, a^{20}, a^{25}, a^{50}\:$ elevando al cuadrado o la multiplicación de las entradas anteriores. Esto requiere en la mayoría de los 5 cuadrar y 2 de la multiplicación de las operaciones de $\rm (mod\ 1000)$. Obviamente el mismo tipo de optimizado divisor de celosía en la búsqueda funciona para cualquier módulo.

Alternativamente, se pueden utilizar los siguientes conocida simple orden algoritmo para grupos
Esta tesis es una buena referencia sobre el fin de los algoritmos en grupos genéricos. Aquí está el resumen:

Answer 2

Como les comente en mi respuesta a esta pregunta, este es un duro cantidad para calcular en general. Para efectos prácticos, debe utilizar la exponenciación por el cuadrado de poner a prueba las posibilidades (y debería utilizar exponenciación al cuadrado para el cómputo de los residuos en general; esta es la forma en álgebra computacional sistemas de hacerlo). Tenga en cuenta que el uso del teorema de Carmichael no es trivial, ya que requiere que usted conozca la factorización prima de $b$.