¿Existe algún algoritmo eficiente para la prueba de primalidad para números que tienen la forma usando la función de raíz cuadrada?

8

Estaba leyendo CLRS y me pidió que mostrara que si es un primo de la forma y era un residuo cuadrático, entonces es una raíz cuadrada (también se puede mostrar fácilmente que es una raíz cuadrada).p4k+3aak+1ak

Me preguntaba si usar el hecho anterior y también que sabíamos que teníamos un número de la forma (no necesariamente primo), entonces tal vez hay una prueba de primalidad diferente para (¿alguna?) usando la función de raíz cuadrada (es decir, ).N=4k+3NSQRTN(a)=ak+1

Entonces el algoritmo que pensé era el siguiente:

Elija un Residuo cuadrático (QR) (se puede hacer fácilmente al verificar si a ^ {\ frac {p-1} {2}} \ equiv 1 \ pmod p se mantiene). Una vez que tengamos un QR, calcule a ^ {k + 1} = x_a y verifique si x_a ^ 2 es igual a a . Si es cierto, entonces concluimos que a es primo. De lo contrario, elegimos un QR diferente a '\ in \ mathbb {Z} ^ * _ N y repetimos el algoritmo. Uno puede repetir este algoritmo k veces. Si después de k veces no hay éxito, concluya que el número es compuesto.aZNap121(modp)ak+1=xaxa2aaaZNkk

Tengo principalmente intuiciones sobre por qué es correcto pero no una prueba formal. Del primer hecho de que xa=ak+1 es una raíz cuadrada cuando p es primo, debe significar que xa2a(modp) . Por lo tanto, si a es un QR, entonces ese cheque pasará (la mitad del tiempo elegiremos un QR, por lo que probablemente elijamos un QR que no sea solo 1/2)

Sin embargo, si N es compuesto, parece que tenemos ninguna garantía de que xa2a(modN) . Entonces, si no se mantiene, estamos seguros de que no es primo. Pero si se mantiene, entonces si es primo, tenemos razón, pero si es compuesto, podríamos estar equivocados Básicamente, ¿es posible usar la función SQRT cuando N=4k+3 para decidir si N es primo o no?


También pensé en otro algoritmo que merecía su propia pregunta: ¿calcular la raíz cuadrada de un número y tener más de 2 raíces es una forma confiable de decidir la primalidad?

Charlie Parker
fuente
@Kyle Jones, ¿hay alguna posibilidad de que esté dispuesto a restaurar (recuperar) su respuesta? Creo que tiene una buena idea, no lo aprecié a primera vista, pero en una inspección más profunda creo que es un buen ejemplo.
DW
@DW OK. No pensé que tuviera mucho valor dada su respuesta más completa, pero lo traeré de vuelta si cree que vale la pena.
Kyle Jones
Tuve una nueva idea después de revisar Miller-Rabin. ¿Qué opinas sobre mi nuevo algoritmo propuesto? @KyleJones
Charlie Parker
@CharlieParker Si tiene una nueva pregunta, debe hacerla en una publicación separada. Si edita esta pregunta para que invalide las respuestas existentes, anula el propósito de tener un repositorio de preguntas y respuestas.
Kyle Jones
@KyleJones es difícil de decidir porque realmente se trata del mismo tema. ¿Que sugieres? Puedo abrir una nueva pregunta, simplemente no estaba seguro de si era apropiado.
Charlie Parker

Respuestas:

5

Permítanme comenzar con un contraejemplo donde su algoritmo da la respuesta incorrecta: es decir, donde es compuesto pero su algoritmo concluye que es primo. Supongamos que y . Entonces , entonces pasa su cheque para ser un QR. Además, y , por lo que esto pasa su segunda prueba, su algoritmo concluir que 91 es primo. Sin embargo, 91 no es primo: . Por lo tanto, su algoritmo ha llegado a una conclusión incorrecta en este caso. Esto demuestra que su algoritmo puede generar respuestas incorrectas en al menos algunos casos.NN=91a=9a(N1)/2=9451(mod91)aa(N+1)/4=92381(mod91)8129(mod91)91=7×13


En realidad, hay un problema más serio con su algoritmo. No hay un número donde su algoritmo saldrá alguna vez "compuesto". Piensa que todos los números son primos. Más precisamente, para cada , su algoritmo se repetirá para siempre (tratando de encontrar un número que pase la prueba QR, en vano), o terminará y generará "primo". Entonces, su algoritmo es tan incorrecto como podría ser.NN

Puedes ver esto aplicando alguna teoría de números. Tiene una prueba de si es un QR y una segunda prueba basada en la información de raíz cuadrada. Si pasa la primera prueba, pasará la segunda.aa

Este es el por qué. Su prueba QR éxito si . Su segunda prueba tiene éxito si . Esta última es equivalente a . Pero . Por lo tanto, si , entonces (multiplicando ambos lados por ) inmediatamente vemos que debemos tener .a(N1)/21(modN)(a(N+1)/4)2a(modN)a(N+1)/2a(modN)a(N+1)/2a×a(N1)/2(modN)a(N1)/21(modN)aa(N+1)/2a(modN)

Cada una de las pasadas de su algoritmo básicamente equivale a buscar una que pase la primera prueba, y luego verificar si pasa la segunda prueba, pero según la información previa, vemos que cualquier que pase la primera prueba estar garantizado para pasar la segunda prueba también. Por lo tanto, si el algoritmo encuentra algún valor que pase la prueba QR, la segunda prueba pasará automáticamente y el algoritmo generará "primo".kaaa

La lección que debe aprender: cada vez que piense que tiene un algoritmo que parece prometedor, vale la pena codificarlo y probarlo en algunos casos de prueba y ver si parece funcionar bien. Probarlo en algunos casos de prueba no es un sustituto de una prueba de corrección , pero puede ser una forma útil de eliminar rápidamente algún algoritmo incorrecto.


Finalmente, a su pregunta real: ¿podemos usar algo como esto para construir una prueba de primalidad? Bueno, puedes pensar que la prueba de primalidad de Miller-Rabin se basa libremente en algo como esto. Se basan en una caracterización de cómo deberían ser las raíces cuadradas de , si es primo. Si encuentra una raíz cuadrada de que no es o , puede concluir que no es primo. Sin embargo, no se limita a los números de la forma , por lo que en ese sentido es definitivamente diferente.1N111NNN=4k+3

DW
fuente
Tuve una nueva idea después de revisar Miller-Rabin. ¿Qué opinas sobre mi nuevo algoritmo propuesto?
Charlie Parker
1
@CharlieParker, en lugar de editar la pregunta de una manera que invalida las respuestas existentes, generalmente preferimos que haga una nueva pregunta. Te sugiero que hagas eso. (Sugerencia: piense en cómo planea calcular sqrt ...)
DW
3

La congruencia es verdadera para todos los primos de la forma correcta, pero también es cierta para algunos números compuestos, lo que hace que la congruencia por sí sola sea inútil como prueba de primalidad.p

Ejemplo: establezca en el número , que obviamente es compuesto y tiene la forma con . es , entonces mod produce el residuo cuadrático = . = = ; aplicando mod a eso produce . Ahora la prueba: bajo mod se supone que es la raíz cuadrada de ( ) solo si es primo, perop154k+3k=31000010021000015a1010k+110410000p10p 10a10p102 = que es mod , por lo que ha pasado la prueba de la primacía. Sin embargo, sabemos que es compuesto.10010ppp

Esto demuestra que incluso si su método para elegir QR es perfecto, el algoritmo aún puede errar. Por ejemplo, aquí sería una forma razonable para recoger : recoger un número aleatorio , cuadrado, y llamar a el resultado (es decir, ). Entonces sabe que está garantizado que es un QR, y no hay necesidad de probarlo usando la prueba que enumeró. Si así fue como su algoritmo eligió , entonces el ejemplo anterior muestra que su algoritmo puede dar la respuesta incorrecta en algunos casos (p. Ej., , ).araa=r2modNaap=15r=5

Kyle Jones
fuente
Me pregunto si hay algún error en alguna parte de sus cálculos, o si no entiendo el algoritmo propuesto. no pasa la prueba QR: , no . Por lo tanto, de acuerdo con mi comprensión del algoritmo propuesto, no sería aceptado como un QR y el algoritmo no trataría de hacer más cálculos con él. Supongo que la forma en que el algoritmo encuentra un QR aceptable es elegir azar y probar si ; eso parece ser lo que sugiere el texto. a=10a(N1)/2=10710(mod15)1a=10aa(N1)/21(modN)
DW
@DW OK. Tu respuesta es completamente mejor de todos modos.
Kyle Jones
1
Ahh, mirando un poco más de cerca, veo lo que está sucediendo: 10 es de hecho un QR, pero el cheque erróneamente piensa que no es un QR. Por lo tanto, si la forma en que el algoritmo trabajó como para recoger un número aleatorio , cuadrado, y llamar a resultado (es decir, ), entonces su respuesta sería un contraejemplo válida - y eso no es Una interpretación irrazonable del algoritmo propuesto. Genial, buena respuesta! a(N1)/2=1(modN)raa=r2modN
DW