¿Qué es la prueba de primalidad p + 1?

Una prueba de primalidad es un algoritmo para determinar si un número de entrada es primo.

Por ejemplo, para probar si 17 es primo, pruebe si 17 es divisible por 2, o 3, o 4, 5, 6, …, 16. Dado que un primo solo es divisible por 1 y por sí mismo, si llegamos a 16 sin encontrar un divisor, entonces hemos demostrado que 17 es primo. Sin embargo, en realidad no tenemos que verificar todos los números hasta n . Veamos otro ejemplo: todos los divisores de 100:
2, 4, 5, 10, 20, 25, 50
aquí vemos que el factor más grande es 100/2 = 50. Esto es cierto para todos los n : todos los divisores son menores o iguales a n / 2. Sin embargo, podemos hacerlo mejor. Si observamos más de cerca los divisores, veremos que algunos de ellos son redundantes. Si escribimos la lista de manera diferente:
100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2
se vuelve obvio. Una vez que lleguemos a 10, que es , los divisores simplemente giran y repiten. Por lo tanto, podemos eliminar aún más los divisores de prueba que . También podemos eliminar todos los números pares mayores que 2, ya que si un número par puede dividir n , también puede 2.