Numeros Primos

[AlbertoBSD]

Muy buen dia.

Busco un metodo 100% seguro para deterinar si un numero dado es primo o no.

Es el metodo que estoy usanfo como lo indica wikipedia es dividir el numero dado entre todos los numeros primos que ya tengo guardados que sean menores o iguales a la raiz del numero dado y si en algun momento el resto de la divicion es 0 entonces el numero no es primo.

Para hacer mas eficiente el trabajo tengo guardadas los cuadrados n^2 en una tabla y cuando pregunto por un numero N solo hago una busqueda binaria y retorno el numero n mas cercano.

Cabe mencionar que ahorita apenas llevo numeros de hasta 7 bytes.

La pregunta aqui es.

¿Hay uno que sea mas rapido y con la misma certeza?

[kub0x]

En efecto existen todo tipo de métodos pero en teoría de números computacional se emplean algoritmos probabilisticos deterministas, los cuales tienen un coste polinomial. Revisa: https://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests

Concretamente te recomiendo que utilices Miller-Rabin, es el más utilizado por la comunidad criptógrafa. https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test También tienes AKS, con el que he obtenido buenos resultados. https://en.wikipedia.org/wiki/AKS_primality_test En ambos enlaces encontrarás sus respectivos costes computacionales.

Si te interesa aprender la base consulta https://en.wikipedia.org/wiki/Fermat_primality_test
El test de primalidad de Fermat es el core de estos algoritmos, se basa en que un número es primo si a toda base coprima con p le corresponde el elemento identidad a través del índice totient(p). El problema de fermat son los números de Carmichael, ya que son módulos compuestos que pasan el test de Fermat, por lo que el test devuelve pseudoprimos o probable primes.

Saludos!

[AlbertoBSD]

Si te interesa aprender la base consulta https://en.wikipedia.org/wiki/Fermat_primality_test
El test de primalidad de Fermat es el core de estos algoritmos, se basa en que un número es primo si a toda base coprima con p le corresponde el elemento identidad a través del índice totient(p).

Buen dia. ya he implememtado el test de primalidad de fermat y el algoritmo mejoro notablemente. Ahora solo corro el test completo contra los probables primos.

Luego le hecho un ojo mas a fondo a loa demas algoritmos.

Primero quiero entender bien la base matematica de los mismos antes de aplicarlos al codigo.


Saludos

[kub0x]

Me alegro de que lo pongas en práctica, es un tema muy apasionante. Miller-Rabin corre en tiempo polinomial, aunque lo que suelen recomendar es hacer varias rondas de Fermat y si el número parece primo pasarlo por Miller-Rabin. Otras implementaciones primero hacen trial division con una lista de primos considerables, lo pasan a Fermat y a Miller-Rabin, en fin, como más cómodo te sientas.

Ojo que si lo que buscas es hacer una criba de números primos, hay métodos más eficientes, lo único que necesitas una estructura auxiliar para ir guardando los números.

Saludos!

[AlbertoBSD]

Detalles 

El algoritmo estaba funcionando bien pero su puso lento... el problema fue la multiplicacion, era algo ineficiente, lo mejore con multiplicacion modular y posteriomente volvio a ir lento, ahora era la exponenciacion, ya la optimize tambien ahora tendre que ver como se comporta.

Por cierto cuantos testigos recomiendan para el Test de primalidad de fermat estoy usando 5 actualmente pero en wikipedia dicen que solo use 4.

¿Que opinan?

Saludos!

[kub0x]

Detalles 

El algoritmo estaba funcionando bien pero su puso lento... el problema fue la multiplicacion, era algo ineficiente, lo mejore con multiplicacion modular y posteriomente volvio a ir lento, ahora era la exponenciacion, ya la optimize tambien ahora tendre que ver como se comporta.

Por cierto cuantos testigos recomiendan para el Test de primalidad de fermat estoy usando 5 actualmente pero en wikipedia dicen que solo use 4.

¿Que opinan?

Saludos!

Sobre la exponenciación, te recomiendo que checkees https://en.wikipedia.org/wiki/Montgomery_modular_multiplication y si estás utilizando exponentiation by squaring mejor migra a éste. Revisa https://en.wikipedia.org/wiki/Modular_exponentiation también.

Sobre los witness en Fermat, bueno hay una regla que indica que la mitad de la clase de residuos son witnesses, por lo tanto testigos de que 'n' es compuesto, como ves hay una alta probabilidad de acierto a la hora de testear si n es compuesto (a no ser que sea un nº de carmichael), 5 en total estarían bien.

También tienes el Lehmann test, que particularmente me gusta mucho por su simpleza y eficacia, se centra en el teorema de Cauchy el cúal afirma que existen elementos dentro del grupo cuyo orden multiplicativo es un factor primo del orden del grupo, por lo tanto si cogemos varios elementos del grupo (bases) y las elevamos a (p-1)/2 y no obtenemos 1 congruente, entonces no satisface el teorema, pero cuidado, que hay algo llamado raíz primitiva, cuyo orden multiplicativo en el grupo es el propio orden en el grupo, pero sólo hay una cantidad de totient(totient(p)), por lo tanto un par de vueltas de este test son muy RECOMENDABLES.

Lehmann:

http://en.algoritmy.net/article/48610/Lehmann-test
https://en.wikipedia.org/wiki/Cauchy's_theorem_%28group_theory%29

Saludos!