Cómo ejecutar la prueba de Fermat de primalidad en menos de 3 minutos

La prueba de Fermat se basa en un resultado de la teoría de números conocida como el pequeño teorema de Fermat.

Según el pequeño teorema de Fermat, si n es un número primo yd es cualquier entero positivo menor que n , entonces d elevado a la n - ésima potencia es congruente con d módulo n .

Si dos números tienen el mismo resto cuando se dividen entre n , se dice que son congruentes módulo n . d módulo n es simplemente el resto de un número d cuando se divide por n .

Por ejemplo, 34 es congruente con 16 (módulo 3) como

34 módulo 3 = 1 y 16 módulo 3 = 1.

Prueba Fermat de primalidad

  1. Para un número dado n , elija un número positivo aleatorio d tal que d < ; norte.
  2. Calcule (d ^ n) módulo n .
  3. d módulo n siempre va a ser d ya que siempre elegimos d que satisface la condición d < ; norte.
  4. Si el resultado de (d ^ n) módulo n no es igual ad , entonces d ciertamente no es primo.
  5. Si el resultado de (d ^ n) módulo n es igual ad , entonces es muy probable que n sea ​​primo.
  6. Elija otro d aleatorio que satisfaga la condición d < ny repita los pasos anteriores.

Nota : Los ejemplos de esta publicación usan Swift 4.1

Necesitamos una función para calcular la exponencial de un número módulo otro número.

Usamos la exponenciación modular para calcular valores cuando el exponente es mayor que 1, ya que esto nos permite realizar el cálculo mientras solo tratamos con números menores que n ( módulo en la función anterior).

La prueba de Fermat elige al azar un número d entre 1 y n-1 ( número - 1 en la función anterior) inclusive. El objetivo es comprobar si el módulo n restante de la enésima potencia de d es igual a d.

La prueba de Fermat se ejecuta para el recuento especificado. Si un número no pasa la prueba de Fermat, tenemos la seguridad de que no es primo. Si un número pasa la prueba de Fermat, no se garantiza que sea primo. Intentamos reducir la probabilidad de error en nuestra prueba de primalidad ejecutando la prueba suficientes veces.

Al probar más y más valores de d (un número positivo aleatorio entre 1 y n-1), podemos aumentar nuestra confianza en el resultado.