Una prueba de primalidad es un algoritmo para determinar si un número de entrada es primo . Entre otros campos de las matemáticas , se utiliza para la criptografía . A diferencia de la factorización de enteros , las pruebas de primalidad generalmente no dan factores primos , solo indican si el número de entrada es primo o no. Se cree que la factorización es un problema computacionalmente difícil, mientras que la prueba de primalidad es comparativamente fácil (su tiempo de ejecución es polinomial en el tamaño de la entrada). Algunas pruebas de primalidad prueban que un número es primo, mientras que otras como Miller-RabinDemostrar que un número es compuesto . Por lo tanto, estas últimas podrían denominarse con mayor precisión pruebas de composición en lugar de pruebas de primalidad.
La prueba de primalidad más simple es la división de prueba : dado un número de entrada, n , verifica si es divisible por cualquier número primo entre 2 y √ n (es decir, que la división no deja resto ). Si es así, entonces n es compuesto . De lo contrario, es primo . [1]
Tenga en cuenta que el factor más grande, 50, es la mitad de 100. Esto es válido para todo n : todos los divisores son menores o iguales que n /2.
En realidad, cuando probamos todos los divisores posibles hasta n /2, descubriremos algunos factores dos veces . Para observar esto, reescribe la lista de divisores como una lista de productos, cada uno igual a 100:
Tenga en cuenta que los productos más allá de 10 × 10 simplemente repiten números que aparecieron en productos anteriores. Por ejemplo, 5 × 20 y 20 × 5 consisten en los mismos números. Esto es válido para todo n : todos los divisores únicos de n son números menores o iguales que √ n , por lo que no necesitamos buscar más allá de eso. [1] (En este ejemplo, √ n = √ 100 = 10.)
Todos los números pares mayores que 2 también se pueden eliminar ya que, si un número par puede dividir a n , también lo puede hacer 2.