[Richard R Richard]

Un hilo debatido aquí despertó mi curiosidad científica    , todo mi estudio pasó por  seguir un link propuesto y traducirlo automaticamente , he visto que tiene muchas más fuentes para seguir, pero el propio texto de página que no pudo saciar mi duda principal , seguir a las fuentes me pregunto si lo conseguirá…
El tema es sencillo: Dado un número $$n$$ , determinar si es primo o compuesto, ¿cuál la forma mas rápida y eficaz posible?. Hablo de números relativamente grandes para la vida diaria, de bastantes cifras, digamos en principio más de 10.
Mi sesgo es que  la criba de Eratóstenes y la factorización en números primos es el más eficaz... ¿Pero es el único método seguro o eficaz para determinar números primos?  ¿Es el más rápido?, ¿qué complejidad computacional tiene?
Viendo lo que la página dice

Prueba de primalidad
Una prueba de primalidad es un algoritmo para determinar si un número de entrada es primo solo indican si el número de entrada es primo o no.
Se cree su tiempo de ejecución es polinomial en el tamaño de la entrada).
Métodos sencillos
. Por lo tanto, el algoritmo solo necesita buscar divisores primos menores o iguales a  raíz de n.  Pueden aplicarse recursivamente , obteniéndose la Criba de Eratóstenes .

La única que creo funciona y la prueba es inmediata y evidente,  deduzco que es P , entonces no es NP…

Una prueba de primalidad simple pero ineficiente utiliza el teorema de Wilson , que establece que un número natural $$n$$ > 1 es primo el producto de todos los enteros positivos menores que $$n$$ es uno menos que un múltiplo de $$n$$  es primo si y sólo si:
$$(p-1)!\equiv -1 (mod \ p)$$ .

Inconveniente que le veo ...Si $$p$$ ya tiene muchas cifras no me imagino cuantas tiene $$(p-1)!$$ . esto no ayuda.

Pruebas heurísticas
Estas pruebas parecen funcionar bien en la práctica, pero no están probadas!!!!
La prueba de primalidad de Fermat y la prueba de Fibonacci son ejemplos sencillos, y su combinación resulta eficaz. Osea si o si detecta primos…. 
$$2^{ p−1}  \equiv 1 (mod\ p )$$ primalidad de Fermat
$$f_{ (p+1)} \equiv 0 (mod \ p )$$ prueba de Fibonacci.

Sobre esto dicen que

Selfridge, Carl Pomerance y Samuel Wagstaff juntos ofrecen $620 por un contraejemplo

Si estuvieran bien convencidos pondrían un premio mayor!!!, pero si están buscando contraejemplos,  significa que   si estoy  leyendo entre líneas que prevén la no eficacia, es decir que no detecten un primo, o digan que es primo un número y en realidad no lo es.
O sea método no seguro.

Pruebas probabilísticas
Múltiples pruebas populares de primalidad son pruebas probabilísticas. Estas pruebas utilizan, aparte del número probado $$n$$ , algunos otros números a que se eligen al azar de algún espacio muestral .
La estructura básica de las pruebas de primalidad aleatorias es la siguiente:
1.            Escoja al azar un número a .
2.            Comprueba la igualdad (correspondiente a la prueba elegida) entre a y el número dado $$n$$ . Si la igualdad no se cumple, entonces $$n$$ es un número compuesto y a es un testigo de la composición, y la prueba se detiene.
3.            Regrese al paso uno hasta alcanzar la precisión requerida.
Después de una o más iteraciones, si no se descubre que $$n$$ es un número compuesto, entonces puede declararse probablemente primo.

Que sean probabilísticas lo dice todo... Si se basa en un método no seguro y luego se basa en un probabilístico, aún existe la posibilidad de no detectar un falso primo, que es muy mínima , pero no 100% segura o eficaz.

La Prueba de primalidad de Fermat probabilística más simple en realidad, una prueba de composición (detecta compuestos). Funciona de la siguiente manera:
Dado un entero $$n$$ , elija un entero  $$a$$ coprimo con $$n$$ y calcule $$a^{n-1}$$  módulo $$n$$ . Si el resultado es distinto de 1, entonces $$n$$ es compuesto. Si es 1, entonces $$n$$ puede ser primo.

Hay un contraejemplo: si $$n= 341$$ y $$a = 2$$,   que mas decir

Prueba de primalidad de Miller-Rabin y Solovay-Strassen
que detectan todos los compuestos (una vez más, esto significa: para cada número compuesto $$n$$ , al menos 3/4 (Miller-Rabin) o 1/2 (Solovay-Strassen) de los números $$a$$ son testigos de la composición de $$n$$ ). Estas también son pruebas de composición, no de primos.

La prueba de Miller-Rabin es una prueba robusta de primos probables , no 100% segura

Y la prueba de Solovay-Strassen es una prueba de primos probables de Euler

Tampoco 100% segura

Prueba de primalidad de Frobenius
...la prueba de pseudoprimalidad de Frobenius ; una ronda de esta prueba tarda aproximadamente tres veces más que una ronda de Miller-Rabin, pero alcanza un límite de probabilidad comparable a siete rondas de Miller-Rabin.
La prueba de Frobenius es una generalización de la prueba de primos probables de Lucas

Ya cuando leí Pseudo... Tampoco 100% segura.

Prueba de primalidad de Baillie-PSW
La prueba de primalidad de Baillie-PSW es una prueba probabilística que combina una prueba de Fermat o Miller-Rabin con una prueba de primos probables de Lucas para obtener una prueba de primalidad sin contraejemplos conocidos. Es decir, no se conoce ningún número compuesto $$n$$ para el cual esta prueba indique que $$n$$ sea probablemente primo. Se ha demostrado que no existen contraejemplos para n.

Que no se conozcan contraejemplos , no significa que no los haya,No?  ... De nuevo, se que esto promete, pero por definición dicen que es probabilística, ósea tampoco es 100% segura ( si no hay contraejemplos debe ser bastante buena para $$n$$ bajos)  pero cuando $$n$$ es alto como hacer si esto no es NP.

Otras pruebas
Leonard Adleman y Ming-Deh Huang presentaron una variante sin errores (pero con un tiempo polinomial esperado) de la prueba de primalidad de la curva elíptica . A diferencia de otras pruebas probabilísticas, este algoritmo produce un certificado de primalidad y, por lo tanto, puede utilizarse para demostrar que un número es primo. [ 7 ] En la práctica, el algoritmo es prohibitivamente lento.
Si existieran computadoras cuánticas , la primalidad podría comprobarse asintóticamente con mayor rapidez que con computadoras clásicas.

Dice que garantiza un primo pero que es muy lento, que mejora con computadoras cuánticas ,claro,  la criba también va mas rápido...

Pruebas deterministas rápidas
primalidad de Pocklington . Sin embargo, como esta prueba requiere una factorización parcial de $$n  − 1$$, el tiempo de ejecución seguía siendo bastante lento en el peor de los casos.

Me pregunto ...Para que factorizar $$n-1$$  si con hacerlo con $$n$$  tenemos el tema resuelto!!

La primera prueba de primalidad determinista significativamente más rápida que los métodos ingenuos fue la prueba de ciclotomía . Se realizaron varias mejoras adicionales, pero ninguna pudo demostrar que tuviera un tiempo de ejecución polinomial.
En 2002, Manindra Agrawal , Neeraj Kayal y Nitin Saxena (AKS) inventaron la primera prueba de tiempo polinomial determinista demostrablemente incondicional para la primalidad ,si la conjetura de Sophie Germain es verdadera .

Si se basa en una conjetura, luego no está 100% probado...

Agrawal, Kayal y Saxena ( prueba AKS)  sugieren una variante de su algoritmo que se ejecutaría en Õ((log  $$n$$ ) 3 ) si la conjetura de Agrawal es verdadera; sin embargo, un argumento heurístico de Hendrik Lenstra y Carl Pomerance sugiere que probablemente sea falsa. Una versión modificada de la conjetura de Agrawal, la conjetura de Agrawal-Popovych, todavía puede ser verdadera.

Nada , mas de lo mismo 100% seguro hasta ahora , nada.

Complejidad
En la teoría de la complejidad computacional , el lenguaje formal correspondiente a los números primos se denota como PRIMES. Es fácil demostrar que PRIMES es co-NP : su complemento COMPOSITES es NP
Se sospechó durante mucho tiempo, pero no se demostró, que la primalidad podía resolverse en tiempo polinomial.
La existencia del test de primalidad AKS finalmente resolvió esta antigua incógnita y situó a PRIMES en P. Sin embargo, no se sabe si PRIMES es P-completo , ni si se encuentra en clases dentro de P, como NC o L. Se sabe que PRIMES no está en AC 0.

Claro, para un despistado como yo,   la clase P consiste de todos aquellos problemas de decisión que pueden ser resueltos en una máquina determinista secuencial en un período de tiempo polinomial en función a los datos de entrada.
Estos test, no son lo que pienso,  tiran un número que se aseguran es primo,  pero en realidad lo que busco es lo contrario , yo doy el número y busco determinar que es primo osea que la complejidad del problema que yo planteo al inicio pasa a ser no NP.
Revisando la definición para los despistados como yo ,  la clase NP consiste de todos aquellos problemas de decisión cuyas soluciones positivas/afirmativas pueden ser verificadas en tiempo polinómico a partir de ser alimentadas con la información apropiada, por supuesto $$n$$ y todos los primos por debajo de $$\sqrt n$$, o en forma equivalente, cuya solución puede ser hallada en tiempo polinómico en una máquina no determinista.
Claro eso es lo que busco, ver si $$n$$ es o no primo, que interesa saber si un número creado por un algoritmo sea seguro un número primo, solo es de interés para criptografía, pero si a ese número le sumas o restas dos no tienen idea si es primo o no.
Para ir al grano si hago un programa que tire consecutivamente al azar $$m-1$$ dígitos entre 0 y 9 y al emésimo lo tire al azar escogiendo equiprobablemente también entre 1,3,7 y 9, probar que el número creado por la concatenación de los $$m$$ dígitos es Primo,  como dije $$m>9$$ eso ninguno lo puede probar con 100%,  insisto la criba sí tarde lo que tarde si lo hace, entiendo que  no podemos almacenar cantidades cercanas ya a 10^80 numero primos en ninguna computadora (no hay átomos en el universo para construirla).
Tampoco me cierra como esfuerzo el logro de hallar y escribir en un libro gordo todas cifras del primo mas alto conocido, todo interés se me extingue, cuando  no podemos afirmar cual es el anterior y menos claro está el siguiente a ese número.

métodos de teoría de números
Existen ciertos métodos de teoría de números para comprobar si un número es primo, como la prueba de Lucas y la prueba de Proth . Estas pruebas suelen requerir la factorización de $$n$$  + 1, $$n$$ − 1 o una cantidad similar, lo que significa que no son útiles para pruebas de primalidad de propósito general, pero suelen ser bastante eficaces cuando se sabe que el número $$n$$ analizado tiene una forma especial

De nuevo ....Si lo difícil es factorizar, y estoy obligado a hacerlo ... entonces lo haría para $$n$$ , que importa  hacerlo para $$n+1$$ o $$n-1$$

Bueno , no quería menospreciar omitiendo los sugeridos  de la página  ¿hay algo que no estoy teniendo en cuenta al clasificarlos,  así subjetivamente?.... más no he  leído, supongo que seguiría a las fuentes de la página, pero no veo ninguno que me asegure nada  y quizá me motive a programarlo.
Perdón por el choclazo... aver como me pueden alinear los patitos , gracias

[feriva]

Hola, Richard

En general, el pequeño teorema de Fermat dice

\( a^{p}\equiv a(mod\,p) \) con “a” y “p” coprimos.

Al ser coprimos, podemos dividir a ambos lados de la congruencia por “a” y queda

\( a^{p-1}\equiv1(mod\,p) \)

donde “a”, la base, puede ser 2, como has puesto tú, o cualquier otro número.

Básicamente, una de las cosas que ocurre, entonces, es que se puede probar la congruencia con varias bases (dado un candidato a primo “p”) y, si la congruencia falla para alguna base, ya no es primo. Miller inventó un test basado en esto que no era seguro del todo, pero Rabin lo perfeccionó para que fuera más eficiente; con este test se comprueban primos con total seguridad, pero no siempre se puede, hay casos en los que a lo mejor no es seguro del todo para un cierto número, y ahí se dice que pasa eso; o sea, cuando una cosa no es segura, no se afirma que es primo (pero eso no suele pasar, es muy raro, la inmensa mayoría de las veces se determinan). Y ese test se llama Miller-Rabin. Lo tienes aquí explicado (creo, porque no lo he leído ahora, hace mucho que lo leí).

https://es.wikipedia.org/wiki/Test_de_primalidad_de_Miller-Rabin

*(Normalmente, cuando se usa “P vs NP”, se hace referencia una conjetura famosa donde esa P se refiere a un tiempo de computación polinómico, no a números primos).

Saludos.

[Luis Fuentes]

Hola

*(Normalmente, cuando se usa “P vs NP”, se hace referencia una conjetura famosa donde esa P se refiere a un tiempo de computación polinómico, no a números primos).

Si, feriva. Así lo ha interpretado Richard R Richard. No se muy bien porque hiciste esa aclaración.

La única que creo funciona y la prueba es inmediata y evidente,  deduzco que es P , entonces no es NP…

Ojo, en el caso de la primalidad se analiza la complejidad frente al número de cifras del número. Entonces es frente a \( N=log_2(n) \) (la base del logaritmo es lo de menos porque dos logaritmos en distintas bases son proporcionales).

Por eso \( =O(\sqrt{n})=O(\sqrt{2}^N) \) no es polinomial (en este contexto).

Respecto a lo demás como te comenté en el otro hilo, no soy ni mucho menos experto en este tema. Y hace años que me interesé un poco por el asunto, lo tenía un poco más fresco. Yo te aconsejo que consultes la Wiki en inglés y vayas a las páginas de los métodos deterministas (que son los que te interesan):

https://en.wikipedia.org/wiki/Pocklington_primality_test

https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test

https://en.wikipedia.org/wiki/Elliptic_curve_primality

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Miller_test

https://en.wikipedia.org/wiki/AKS_primality_test

Luego hay alguna cosa que has dicho que no es exacta; por ejemplo el AKS si es seguro 100%. La dependencia de la conjetura de Sophie Germain tiene que ver con garantizar que funciona en un determinado tiempo de computación, frente a otro más largo (pero igualmente no es malo) si fallase.

Métodos que se basen en la descomposición \( n-1 \) bien porque por la particularidad de \( n \) tengamos información sobre esa descomposición; o simplemente porque \( n-1 \) pueda descomponerse de manera rápida. Evidentemente esto no puede asegurarse en general para cualquier número, pero hay casos en los que funciona.

Los test probabilísticos, tienen sentido, como mínimo para descartar números no primos rápidamente; y quedarse sólo con primos probables para atacarlos con métodos deterministas.

En fin, cualquier cosa que te diga sería leyendo los enlaces, porque tendría que refrescar todo. Así que no añado nada más. 

Saludos.

[feriva]

Hola

*(Normalmente, cuando se usa “P vs NP”, se hace referencia una conjetura famosa donde esa P se refiere a un tiempo de computación polinómico, no a números primos).

Si, feriva. Así lo ha interpretado Richard R Richard. No se muy bien porque hiciste esa aclaración.

Se ve que he leído tan por encima como siempre, sí Pero ya me he fijado bien en lo que dice.

(Me tengo que hacer gafas; casi mejor me debería operar de cataratas, pero lo voy dejando... y ya deben de ir 20 años dejándolo).

Gracias. Luis.

Saludos.

[Luis Fuentes]

Hola

(Me tengo que hacer gafas; casi mejor me debería operar de cataratas, pero lo voy dejando... y ya deben de ir 20 años dejándolo).

¿Las cataratas no suelen evolucionar más rápido?

¡Opérate!. Yo estoy operado de los dos ojos de cataratas y la verdad es una maravilla; lentes trifocales y hasta dejé las gafas. Eso si de la vista cansada no me libro...

Saludos.

[Richard R Richard]

Hola, gracias por las respuestas,  los algoritmos  basados en explorar primos $$a$$ y su congruencia para alguno $$a$$ menores a$$\sqrt n$$, los imagino del mismo estilo que probar todos esos $$a$$ en la criba de Eratostenes... uno que no pruebes, ya no tienes garantía  de que el número  no es primo, (cosa diferente a que sea muy pero muy probable que lo sea, mas cuando se evitan los más próximos a la raiz)


No sé si se notó bien en la lectura de todo ese interminable post, que no me terminaba de convencer que cada test, no me cerraba por no ser seguro, ahora que me aclaras que eso no es cierto  para algunos , voy a leer más detalladamente esos. Gracias por los links de divulgación.


Fundamentalmente creo que en general se necesita  un test 100% fiable, porque en el caso de que devuelva  "primo probable" no hay forma de checarlo con la criba, porque evidentemente ya no tienes todos los primos necesarios para asegurar  100% y eso es lo que , sería innegociable en mi cesuda concepción de usar primos para algo computacionalmente, que no es la criptografía que por ahora no me atrae.

[feriva]

Hola

(Me tengo que hacer gafas; casi mejor me debería operar de cataratas, pero lo voy dejando... y ya deben de ir 20 años dejándolo).

¿Las cataratas no suelen evolucionar más rápido?

¡Opérate!. Yo estoy operado de los dos ojos de cataratas y la verdad es una maravilla; lentes trifocales y hasta dejé las gafas. Eso si de la vista cansada no me libro...

Saludos.

En mi caso no han ido a mucho peor durante todos estos años. He puesto en el buscador a ver si esto es normal o posible y el Gemini me dice que sí: “Sí, las cataratas suelen evolucionar de manera gradual, pudiendo pasar meses o años para que se note un cambio en la visión”.

Todo el mundo me dice lo mismo que tú, que me opere, que es muy rápido y queda muy bien, conozco a varias personas que se han operado y casi todas están contentas. Algún día me tendré que decidir.

Gracias por la recomendación, Luis.

Saludos.

[Richard R Richard]

¿Si $$p$$ es primo, $$ p \vert N - 1$$  debo entender que  $$p$$ divide exactamente a  $$N-1$$?

y si $$ p > \sqrt{N} - 1$$  entonces existe $$a$$ tal que $$p.a=N-1$$  y a la vez $$a<\sqrt{N}+1$$       y existe el caso que $$p=a$$

Cual es la idea tras la condición 2 de https://es.wikipedia.org/wiki/Test_de_Pocklington-Lehmer

[Luis Fuentes]

Hola

¿Si $$p$$ es primo, $$ p \vert N - 1$$  debo entender que  $$p$$ divide exactamente a  $$N-1$$?

Si. En general \( k|m \) es una notación que significa que \( k \) es un divisor de \( m \) o equivalentemente que \( m \) es mútliplo de \( k \).

y si $$ p > \sqrt{N} - 1$$  entonces existe $$a$$ tal que $$p.a=N-1$$  y a la vez $$a<\sqrt{N}+1$$  y existe el caso que $$p=a$$

Si \( p|(N-1) \) entonces existe \( a \) tal que \( p\cdot a=N-1 \).

Si \( p>\sqrt{N}-1 \), entonces \( a=\dfrac{N-1}{p}<\dfrac{N-1}{\sqrt{N}-1}=N+1 \).

Y si, podría ser que \( p=a \). Por ejemplo \( N=5 \) y \( p=a=2 \).

Cual es la idea tras la condición 2 de https://es.wikipedia.org/wiki/Test_de_Pocklington-Lehmer

No estoy seguro de en que sentido lo preguntas.

De manera objetiva (2) dice que existe un primo \( p \) que es divisor de \( N-1 \) y \( >\sqrt{N}-1 \). Pero bueno aquí no te he dicho nada... es lo que está escrito.

Si me preguntar por que idea intuitiva hay detrás de eso, no sabría decirte; coloquialmente es decir que existe un primo divisor de \( N-1 \) suficientemente grande.

En el enlace viene demostrado el teorema; si tengo tiempo lo miro con más calma.

Saludos.

[Richard R Richard]

Ok, no le encontraba importancia, para ser dato del teorema, por eso pregunté, por si me perdía algo y después ando preguntando cosas demasiado obvias para alguien  bien ejercitado. Si la idea es que si comprendo el teorema ,me convenza de que es útil y que me sirve y puedo usar  otra herramienta  que no es la criba o una base de datos de primos ordenados.
Por ahora vengo viendo que si $$N$$ tiene 100 cifras y $$a$$ tiene 30 entonces $$a^{N-1}$$ es un número muy grande rondando lass $$a(N-1)$$ cifras , averiguarle la congruencia requiere algoritmos de división más avanzados que un simple signo divisor o resto dado por teclado, eso ralentiza  las cosas, pero no me quiero adelantar. Primero entender. Se que $$a$$ puede ser $$2$$ y que el número a averiguar la congruencia tendría 30 cifras, aunque con fijarse si es par o impar basta... en fin no se si me voy rápido a los extremos de lo que puedo encontrar.