Preguntas > Matemáticas discretas

¿Como determinar sinun número muy grande es primo?

Sergio Salanitri 2 respuestas
Estoy interesado en saber que algoritmos existen oara saber si un número extremadamente grande es primo. Me refiero a números usados en criptografía de al mebos 255 bits.
0
{0} / {1} caracteres recomendados
La respuesta debe contener algún carácter
Respuestas
José Pérez Leal Pérez Leal
Para saber si un número es primo (divisible sólo por el mismo y por uno), lo dividimos sucesivamente por los primeros números primos: 2, 3, 5, 7, 11, .. ¿Cuándo paramos de dividir? - Si obtenemos división exacta entonces no es primo - Si el cociente es menor que el divisor .. paramos entonces es primo
Escribe una respuesta
0
Sergio Salanitri
Gracias, eso sirve para número muy chicos, también en ese caso se puede usar la criba de Erastostenes. Mi pregunta apunta a númer grande, pero extremadamente grandes como número de 255 bits, o sea del orden de 2^255. Se que exiten algoritmos para estimar pseudoprimos como el de Lucas, o el pequeño teorema de Fermat
Escribe una respuesta
0
Martin Revello
La hipótesis de Riemann es una buena solución
0
Alejandro Carrillo
Bueno, esa es justamente una de los grandes obstáculos en la criptografía moderna (y otros campos). Yo personalmente uso el algoritmo de Miller-Rabin; ojo, no es perfecto y se basa mucho en probabilidades.
Escribe una respuesta
0
Preguntas relacionadas
Sergio Salanitri
Datos verificados