5 votos

¿Existe una forma mejor de encontrar el orden de un número módulo? $n$ ?

Digamos que deseo encontrar el orden de 2 módulo 41.

La forma en que me han enseñado a calcular esto es escribir literalmente $2^k$ y seguir subiendo con $0 \leq k \leq 41$ o hasta que observe una periodicidad en la secuencia, y a partir de ahí establecer el orden.

¿Existe una forma mejor de deducir el orden de un número con respecto a algún módulo?

Esto parece altamente ineficiente, especialmente si estamos trabajando con respecto a algún módulo grande $N$ en la que tardará como máximo $N$ cálculos para determinar cuándo se produce la periodicidad.

10voto

Hagen von Eitzen Puntos 171160

Para cualquier $a$ y $N$ con $\gcd(a,N)=1$ El orden de $a$ modulo $N$ debe ser un divisor de $\varphi(N)$ . Por lo tanto, si se conoce la factorización primaria de $N$ (o $N$ ya es primo) para poder calcular $\varphi(N)$ y también conocer la factorización primaria de $\varphi(N)$ puede proceder de la siguiente manera:

Si conocemos un número entero $m>1$ con $a^m\equiv 1\pmod N$ y conocer los divisores primos de $m$ para todos los primos $p$ dividiendo $m$ hacer lo siguiente: Calcular $a^{m/p}\bmod N$ y si el resultado es $\equiv 1\pmod N$ , reemplazar $m$ con $m/p$ y repetir (o pasar al siguiente divisor primo si $m$ ya no es divisible por $p$ ). Cuando hayas descartado todos los factores posibles, los restantes $m$ es el orden de $a$ . Tenga en cuenta que los cálculos $a^m\bmod N$ hacer no requiere $m$ multiplicaciones, sino sólo $O(\log m)$ multiplicaciones mod $N$ si utilizamos la cuadratura repetida.

Si $N$ es grande y la fatorización de $\varphi(N)$ se conoce (y especialmente si se sospecha el orden de $a$ ser grande), este es de hecho un método rápido.

Tenga en cuenta que se pueden ahorrar un par de cálculos incluso más allá de lo descrito anteriormente: En el caso $p=2$ Podemos acabar computando $a^m, a^{m/2}, a^{m/4},\ldots$ para expulsar los factores de $2$ . Pero los números posteriores eran de hecho resultados intermedios de la computación $a^m$ por la repetición de la cuadratura. Además, una vez que notamos para algunos $p$ con $p^k\mid m$ que $a^{m/p}\not\equiv 1\pmod N$ podemos ahorrarnos unos cuantos cuadrados y así acelerar la tarea para los primos restantes si sustituimos $a$ con $a^{p^k}\pmod N$ y $m$ con $m/p^k$ - sólo recuerda multiplicar el factor $p^k$ ¡en la respuesta final!

En su ejemplo concreto, sabemos que $N=41$ es primo y que $\varphi(N)=40=2^3\cdot 5$ . Comprobamos $p=5$ y observe que $2^{40/5}=256\equiv 10\pmod{41}$ por lo que el factor $5$ no puede ser eliminado. Después comprobamos cuántos $2$ que tenemos que utilizar: $2^5\equiv 32\equiv -9$ Por lo tanto $2^{10}\equiv 81\equiv -1$ , $2^{20}\equiv (-1)^2\equiv 1$ . Concluimos que $2$ tiene orden $20$ modulo $41$ .

1voto

freethinker Puntos 283

El pedido debe ser uno de los siguientes $1,2,4,8,5,10,20,40$ .

Calcular $2^2,2^4=(2^2)^2,2^8=(2^4)^2,...\\2^5=2^4*2,2^{10}=(2^5)^2,2^{20}=(2^{10})^2,2^{40}=(2^{20})^2$ que son siete cálculos.

Si 41 no es primo, digamos $41=a^2b^3c$ entonces

i) calcular el orden de $2\pmod{a^2}$ y la orden $\pmod{b^3}$ y el orden $\pmod c$
ii) calcular el mínimo común múltiplo de los órdenes separados.

0voto

MikeMathMan Puntos 159

Aquí calculamos el orden de $2$ en $(\mathbb{Z}/{41}\mathbb{Z})^\times$ .

Nota: A la hora de calcular puedes utilizar el trabajo anterior a tu favor. Para reducir realmente los cálculos, si sabes que el orden es mayor o igual $10$ una vez que se calcula $2^{10} \pmod{41}$ ya está hecho,

$\quad 2^{10} \equiv 1 \pmod{41} \quad \text{order is } 10$
$\quad 2^{10} \equiv 40 \pmod{41} \quad \text{order is } 20$
$\quad \text{NOT }[2^{10} \equiv 1, 40 \pmod{41}] \quad \text{order is } 40$

Resumen del trabajo : $2^1 \equiv 2 \pmod{41}$ .

El orden de $2$ es uno de $2,4,8,5,10,20,40$ .

Resumen del trabajo : $2^2 \equiv 4 \pmod{41}$ .

El orden de $2$ es uno de $4,8,5,10,20,40$ .

Resumen del trabajo : $2^4 \equiv 16 \pmod{41}$ .

El orden de $2$ es uno de $8,5,10,20,40$ .

Resumen del trabajo : $2^5 = \equiv 32 \pmod{41}$ .

El orden de $2$ es uno de $8,10,20,40$ .

Resumen del trabajo : $2^8 \equiv 10 \pmod{41}$

El orden de $2$ es uno de $10,20,40$ .

Resumen del trabajo : $2^{10} \equiv 40 \pmod{41}$

El orden de $2$ es uno de $20,40$ .

Resumen del trabajo : $2^{20} \equiv 1 \pmod{41}$

El orden de $2$ es igual a $20$ .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X