Diferencia entre revisiones de «Test de primalidad de Fermat»
Contenido eliminado Contenido añadido
m Mantenimiento de Control de autoridades |
+reestructurar secciones |
||
Línea 1:
{{Referencias|t=20171029214532}}
El [[pequeño teorema de Fermat]] enuncia que si ''p'' es [[número primo|primo]] y ''a'' es [[coprimo]] con ''p'', entonces ▼
▲El '''test de primalidad de Fermat''' es un algoritmo probabilístico que hace uso del [[pequeño teorema de Fermat]]. este teorema enuncia que si ''p'' es [[número primo|primo]] y ''a'' es [[coprimo]] con ''p'', entonces
''a''<sup>''p''-1</sup> - 1 es [[divisible]] por ''p''. Esto también se puede expresar así: ''a''<sup>''p''-1</sup> = 1 ([[aritmética modular|mod]] ''p''). ▼
:''a''<sup>''p''-1</sup> - 1 es [[divisible]] por ''p''.
Resulta que el recíproco de este teorema suele ser verdad: si ''p'' es compuesto, entonces ''a''<sup>''p''-1</sup> es poco probable que sea congruente con 1 módulo ''p'' para un valor arbitrario de ''a''.▼
▲
El programa de [[Criptografía|cifrado]] [[PGP]] aprovecha esta propiedad del teorema para comprobar si los grandes números aleatorios que elige son primos. Comprueba los valores que llamaremos ''x'' utilizando 4 valores de ''a'' (llamados ''testigos'') utilizando la fórmula anterior. Estos cuatro valores son 2, 3, 5 y 7, los cuatro primeros números primos. Si 1 = 2<sup>''x''-1</sup> = 3<sup>''x''-1</sup> = 5<sup>''x''-1</sup> = 7<sup>''x''-1</sup> (mod ''x''), entonces sabe que el número ''x'' es probablemente primo. Si de alguna de las expresiones anteriores se obtiene un valor distinto de 1, entonces ''x'' es definitivamente compuesto. Utilizar un número mayor de testigos disminuye la probabilidad de que un número compuesto ''x'' parezca primo, aunque muy pocos números grandes pueden engañar a los cuatro testigos ya mencionados.▼
▲Resulta que el recíproco de este teorema suele ser verdad: si ''p'' es compuesto, entonces ''a''<sup>''p''-1</sup> es poco probable que sea congruente con 1 módulo ''p'' para un valor arbitrario de ''a''. Sin embargo, tomando un número compuesto ''n'' y eligiendo un ''a'' coprimo con este, algunos números compuestos pueden hacer fallar este test. Estos números se denominan [[pseudoprimo]]s.
== Algoritmo ==
Línea 28 ⟶ 27:
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.
== Usos ==
▲El programa de [[Criptografía|cifrado]] [[PGP]] aprovecha esta propiedad del teorema para comprobar si los grandes números aleatorios que elige son primos. Comprueba los valores que llamaremos ''x'' utilizando 4 valores de ''a'' (llamados ''testigos'') utilizando la fórmula anterior. Estos cuatro valores son 2, 3, 5 y 7, los cuatro primeros números primos. Si 1 = 2<sup>''x''-1</sup> = 3<sup>''x''-1</sup> = 5<sup>''x''-1</sup> = 7<sup>''x''-1</sup> (mod ''x''), entonces sabe que el número ''x'' es probablemente primo. Si de alguna de las expresiones anteriores se obtiene un valor distinto de 1, entonces ''x'' es definitivamente compuesto. Utilizar un número mayor de testigos disminuye la probabilidad de que un número compuesto ''x'' parezca primo, aunque muy pocos números grandes pueden engañar a los cuatro testigos ya mencionados.
== Véase también ==
*[[Test de primalidad]]
== Enlaces externos ==
*{{MathWorld|FermatsPrimalityTest|Fermat's Primality Test}}
{{Control de autoridades}}
[[Categoría:Tests de primalidad]]
| |||