Prueba de primalidad BPSW - Selección de los parámetros D y Q

Question

Estoy estudiando un artículo de los autores del verificador de primalidad Baillie-PSW aquí pero estoy desconcertado por un detalle de su prueba de primalidad Lucas.

Una aplicación BPSW por lo general:

1. Ordena $n \le 3$ incluso $n$ entonces $n$ divisible por factores pequeños.
2. Temas $n$ a una prueba de primalidad de Fermat de base 2 fuerte.
3. Comprobar la cuadratura de $n$ .
4. Temas $n$ a una prueba de primalidad Lucas fuerte con un protocolo particular para la selección de su $P$ , $D$ y $Q$ parámetros.
5. Si los preliminares, la prueba de Fermat fuerte, la comprobación de la cuadratura y la prueba de Lucas fuerte no demuestran $n$ compuesto, entonces $n$ se supone primo.

La prueba de primalidad de Lucas para $n$ requiere tres parámetros enteros auxiliares, $P$ , $D$ y $Q$ relacionados por la ecuación $D = P^2 - 4Q \ne 0$ . Los autores de BPSW insisten en ciertas propiedades adicionales: En particular, que un valor de $D$ para que el Símbolo de Jacobi $\left( \frac{D}{n} \right)$ es -1 (si es 0, ¡qué suerte! ¡Has encontrado un factor!). Señalan claramente que si $n$ o $D$ es cuadrado, entonces el símbolo de Jacobi será $\ge 0$ (por las reglas del símbolo).

Los autores ofrecen varias estrategias para la selección de $P,D,Q$ . El más popular se debe a John Selfridge:

1. Seleccione el primer $D \in \{ 5, -7, 9, -11, 13, -15, \ldots \}$ s.t. $\left( \frac{D}{n} \right) = -1$ (o 0).
2. $P=1$
3. $Q = (P^2 - D)/4 = (1-D)/4$

Los autores también señalan que si $Q \ne \pm 1$ encima de $\left( \frac{D}{n} \right) = -1$ entonces la prueba de primalidad puede reforzarse aún más con un coste adicional muy bajo.

Por último, los autores también demuestran que la búsqueda de un $D$ que satisface el requisito del símbolo de Jacobi suele terminar en 2-3 evaluaciones.

Y ahora llegamos a mi pregunta. Como se ha descrito, la estrategia de Selfridge comienza con $D=5$ . Si esto se acepta, entonces $Q=(1-5)/4=-4/4=-1$ perdiendo fuerza la comprobación de la primalidad. A continuación $D=7$ que está bien, pero si eso no funciona entonces estamos en $D=9$ que es cuadrado (y, por tanto, inutilizable (?)). Y muy pronto podría encontrarse con $D=25$ que también es cuadrado.

¿Por qué la estrategia de selección de parámetros BPSW Lucas más utilizada comienza con un conjunto de valores tan pobre? ¿Por qué es preferible esta estrategia?

Por lo demás, todas las estrategias examinadas por el autor piden la primero $D$ en algunas series para satisfacer $\left( \frac{D}{n} \right) = -1$ y, sin embargo, los autores parecen pasar por alto la posibilidad de una búsqueda aleatoria, o de una búsqueda iniciada con un valor (más) alto de $D$ donde

1. $Q$ estaría garantizada $\ne \pm 1$
2. Cuadrado $D$ son mucho menos densos.

especialmente a la luz de su prueba de que sólo 2-3 valores de $D$ de media antes de encontrar una adecuada.

Incluso podría diseñar una estrategia garantizado para evitar el cuadrado $D$ 's. Del mismo modo que el incremento de $1$ por enteros Impares sucesivos $3, 5, 7, \ldots$ genera todos los cuadrados ( $1^2+3=2^2$ , $2^2+5=3^2$ , $3^2+7=4^2 \ldots$ ), incrementando $2$ por esos mismos enteros Impares sucesivos produce números que no pueden ser cuadrados ( $5, 10, 17, 26, 37, 50, \ldots$ ). Tomando uno de cada dos no cuadrados así producidos se cumpliría el requisito de que 4 divide a partes iguales $(1-D)$ : 5, 17, 37...

¿A qué se debe? ¿Se basa el algoritmo BPSW en la primero o bajo valores de $D$ ?

Mi investigación me ha llevado sólo a esta página de Thomas R. Nicely, que sólo escribe una frase en off sobre el tema:

Las condiciones adicionales que a veces se imponen (Riesel, 1994, p. 130), que N no divida a Q y que D sea libre de cuadrados, resultaron ser irrelevantes para esta aplicación de las secuencias de Lucas.

lo que en realidad no me dice mucho.

Answer 1

En primer lugar, calcular Jacobi (D/n) es aproximadamente equivalente a GCD(n, algo). Comparado con el resto de la prueba de primalidad, se trata de un cálculo minúsculo.

En segundo lugar, la última sección del documento Lucas Pseudoprime muestra que normalmente no es necesario probar muchas D antes de encontrar una con (D/n) = -1.

En tercer lugar, he encontrado que exactamente cómo se obtiene P, Q no importa mucho en el sentido de que el número de Lucas pseudoprimes hasta x es aproximadamente el mismo. Como la persona que escribió la pregunta anterior señaló, es una buena idea para asegurarse de abs(Q) > 1. El método A* en el documento Lucas Pseudoprimes hace esto.

Yo diría que la estrategia es conveniente, pero no necesariamente "preferible" a otros métodos. Excepto que, después de todos estos años utilizando el método A o A*, nadie ha encontrado un contraejemplo. Si eliges otro método para encontrar P y Q, corres el riesgo de que uno de los pseudoprimos de Lucas resultantes sea un pseudoprimo fuerte de base 2.

Una sugerencia para reforzar la prueba: También sugeriría comprobar, al final del cálculo, que V_{n+1} = 2Q (mod n). Actualmente estoy utilizando el método A* y buscando soluciones compuestas. Hasta ahora, n = 913 es el único n compuesto impar hasta 60 mil millones que satisface esta congruencia. Una vez calculado V_{n+1} (mod n), esta comprobación adicional es prácticamente gratuita.

Answer 2

Aquí está la prueba determinista de primalidad de Lucas, sólo se necesita una prueba para descartar cualquier número compuesto, NO es necesario comprobar pseudoprimes fuertes de base dos, buena suerte.

aquí te presentaré la mejor manera de elegir $P, Q$ y $D$ parámetros para la prueba de primalidad de Lucas. esta selección es siempre correcta y ningún número compuesto pasará esta prueba. aquí está mi resumen de $BPSW$ prueba.

Puntos débiles de la prueba BPSW

• no es dinámico, para cualquier número $n$ siempre selección de $D$ empezar con $5$ . Al final utilizamos el mismo $D$ para comprobar la primalidad de muchos $n$
• el segundo orden está controlado por los dos términos anteriores, por lo que para comprobar la primalidad de un número debemos idear una forma que compruebe los dos términos en un punto que utilicemos para comprobar la primalidad del número $n$ .
• pruebas combinadas, prueba lucas y spsp2

Nueva forma de seleccionar $P, Q$ y $D$

Sea $n$ sea un número cuya primalidad estamos comprobando, calcula $y = floor(\sqrt{n})$ . A continuación, compruebe si $n$ es cuadrado perfecto. Sea $D = P^2 + 4Q$ Utiliza pequeñas $P$ , $\{1, 2, ..., 9\}$ prefieren primos. entonces calcula $D$ variando $Q$ , $Q> y - 1$ calcular el símbolo de Jacobi $(D/n)$ , $(D/n)= - 1$ . y ya está. $P, Q$ y $D$ . Utilizar el símbolo de Jacobi para evitar la factorización de números grandes

Pruebas

no necesitamos repetir los errores, computa $U_n$ y $U_{n+ 1}$ . si $n$ es primo, $\{U_n, U_{n+1}\} = \{n - 1, 0\}$ el número de $Q$ que tendrá que probar depende del Valor de $P$ . es $P$ es $!$ máximo $47$ $Q$ s, no depende de $n$ . Muchos números compuestos satisfacen sólo una de estas dos pruebas, y muchos de ellos la prueba de divisibilidad.