elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Los 10 CVE más críticos (peligrosos) de 2020


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Numeros Primos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Numeros Primos  (Leído 2,755 veces)
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Numeros Primos
« en: 10 Mayo 2016, 02:11 am »

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?


« Última modificación: 10 Mayo 2016, 02:16 am por AlbertoBSD » En línea

kub0x
Enlightenment Seeker
Colaborador
***
Desconectado Desconectado

Mensajes: 1.486


S3C M4NI4C


Ver Perfil
Re: Numeros Primos
« Respuesta #1 en: 10 Mayo 2016, 03:21 am »

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!


En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Numeros Primos
« Respuesta #2 en: 16 Mayo 2016, 22:28 pm »

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
En línea

kub0x
Enlightenment Seeker
Colaborador
***
Desconectado Desconectado

Mensajes: 1.486


S3C M4NI4C


Ver Perfil
Re: Numeros Primos
« Respuesta #3 en: 17 Mayo 2016, 00:07 am »

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!
En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Numeros Primos
« Respuesta #4 en: 17 Mayo 2016, 21:50 pm »

Detalles  ;D ;D

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!
En línea

kub0x
Enlightenment Seeker
Colaborador
***
Desconectado Desconectado

Mensajes: 1.486


S3C M4NI4C


Ver Perfil
Re: Numeros Primos
« Respuesta #5 en: 19 Mayo 2016, 14:21 pm »

Detalles  ;D ;D

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!
En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
Scripting
katas 2 9,839 Último mensaje 10 Marzo 2010, 01:50 am
por Novlucker
NUMEROS PRIMOS
Programación C/C++
alviera 4 6,011 Último mensaje 7 Diciembre 2010, 06:39 am
por N0body
NUMEROS PRIMOS
Programación C/C++
ALONSOQ 5 3,575 Último mensaje 16 Junio 2012, 18:13 pm
por ALONSOQ
Numeros primos
Programación C/C++
Ander123 6 3,304 Último mensaje 30 Agosto 2012, 21:15 pm
por leosansan
Sucesion parcial o completa entre numeros primos. « 1 2 3 »
Criptografía
Usuario887 23 15,132 Último mensaje 15 Febrero 2021, 23:56 pm
por Usuario887
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines