Diferencia entre revisiones de «Test de primalidad de Fermat»
Contenido eliminado Contenido añadido
+referencia -plantilla |
+ejemplo |
||
Línea 22:
Utilizando algoritmos rápidos de [[exponenciación modular]], se puede comprobar que el [[complejidad computacional|tiempo de ejecución]] de este algoritmo es O(''k'' × log<sup>2</sup>''n'' × log log ''n'' × log log log ''n''), donde ''k'' representa el número de veces que se comprueba la [[congruencia]] para el número aleatorio ''a'' y ''n'' es el número a testear.
== Ejemplo ==
Supongamos que se quiere determinar si ''n'' = 221 es primo. Escogiendo aleatoriamente 1 < ''a'' < 221, digamos ''a'' = 38, se puede chequear la expresión para determinar si se cumple:
:<math>a^{n-1} = 38^{220} \equiv 1 \pmod{221}.</math>
luego 221 puede ser primo, o también puede que 38 sea un número que falsee el test, de manera que tomamos otro ''a'', esta vez 24:
:<math>a^{n-1} = 24^{220} \equiv 81 \not\equiv 1 \pmod{221}.</math>
Luego 221 es compuesto y 38 era en efecto un número que falsaba el test. Además, 24 es un testigo de Fermat de la no primalidad de 221.
== Usos ==
| |||