Diferencia entre revisiones de «Test de primalidad de Fermat»

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 ''xn'' 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^''xn''-1 =≡ 3^''xn''-1 =≡ 5^''xn''-1 =≡ 7^''xn''-1 (mod ''xn''), entonces sabe que el número ''xn'' es probablemente primo. Si de alguna de las expresiones anteriores se obtiene un valor distinto de 1, entonces ''xn'' es definitivamente compuesto. Utilizar un número mayor de testigos disminuye la probabilidad de que un número compuesto ''xn'' parezca primo, aunque muy pocos números grandes pueden engañar a los cuatro testigos ya mencionados.