Autor Tema: Método eficiente para calcular orden dado un módulo.

0 Usuarios y 1 Visitante están viendo este tema.

12 Mayo, 2011, 03:48 am
Leído 1426 veces

luchoferronir

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 237
  • Karma: +1/-0
  • Sexo: Masculino
Hola, planteo mi duda, concreta, y sin vueltas:

¿Cuál es el método más eficiente para calcular \( \mbox{ord}_{169}(10) \)?

Saludos, y gracias.

12 Mayo, 2011, 10:33 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 No se si te refieres a "más eficiente" en el sentido más riguroso de la palabra, es decir, aquel que rqeuiere menos tiempo de cálculo computacional en un ordenador.

 Sea como sea un camino es usar el Teorema de Euler.

 En tu caso nos asegura que:

\(  10^{\varphi(169)}=1\quad mod\quad 169 \)

 donde:

\(  \varphi(169)=\varphi(13^2)=13\cdot 12 \)

 Deducimos que el orden es divisor de \( 12\cdot 13 \).

Saludos.

12 Mayo, 2011, 08:44 pm
Respuesta #2

luchoferronir

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 237
  • Karma: +1/-0
  • Sexo: Masculino
Hola,

Sí, hasta ahí, de acuerdo. Mi problema radica en hallar exactamente el valor del orden, con lo cual, si bien ahora tengo una cantidad finita de posibilidades, todavía me veo imposibilitado de especificar cuál es el valor correcto.

¿Cómo se haría en tal caso?

Gracias y saludos.

PD: Con 'eficiente' me refería a la manera más rápida de hallarlo 'a mano'.