On Fri, 10 Nov 2000, Horacio Castellini wrote:
> Alguien conoce un algoritmo para calcular n�meros primos de 200
> d�gitos, como los usados en generaci�n
> de claves? La criba de Erast�teles no corre, y al algoritmo de Fermat es
> la muerte.
Hay varios algoritmos muy eficientes (dentro de lo que se puede
esperar...) para hacer eso. El �nico problema es que en gral son
probabilistas (no garantizan que el n�mero encontrado sea primo, solamente
te dicen que la probabilidad que no lo sea es muy muy muy baja) Si lo
necesitas, creo que puedo encontrar referencias precisas (casi seguro, hay
referencias y un ap�ndice sobre este tema en unas notas de un (muy buen)
curso de criptograf�a que dio en el MIT un tal Goldwasser hace un par de
a�os--lo podes bajar del MIT); pero si lo que quer�s es implementarlos, lo
m�s razonable me parece que es buscar algo ya armado, porque tienden a ser
algoritmos extremadamente complejos, muy sensibles a detalles m�nimos en
la implementacion (y matematicamente escabrosos!)
El problema con la criba de Erast�tenes es que es extremadamente eficiente
(porque elimina la necesidad de dividir) si quer�s generar la lista de
los primeros n numeros primos, pero no si solo quer�s uno grande. No se
bien a qu� llam�s ``algoritmo de Fermat'', pero supongo que debe ser
probar calcular a^p mod p y ver que siempre da a... Hay que tener en
cuenta que eso *no* funciona: hay (infinitos) n�meros p que cumplen esa
propiedad y no son primos (se llaman n�meros de Carmicheal); de cualquier
manera, varios algoritmos para verificar primalidad se basan en la prueba
de Fermat y un an�lisis increiblemente fino de la probabilidad de
encontrar un n�mero de Carmicheal.
Si lo que necesitas es generar solamente algunos primos, aunque en el
rango de los 30 bits, pod�s usar p. ej. el Mathematica, que encuentra
primos bastante r�pido: Prime[10000000000] calcula el primo n�mero
10000000000, que es 252097800623, en menos de una cent�sima de segundo (y
no est� usando una tabla...)
> Duda existenci�l: Es el 1 un n�mero primo?
Eso depende, por supuesto, de la definicion que est�s usando, y la
definici�n que uno usa depende de lo que uno este haciendo (m�s all� de
que tiene que capturar la idea usual, no?) En general, la gente que hace
teor�a de n�meros excluye al 1 del conjunto de los primos, porque, sino no
lo hicieran, la mayor parte de los teoremas dir�an cosas del estilo de
``si p es un n�mero primo distinto de 1...'' (Conozco un libro sobre
formas cuadraticas sobre cuerpos finitos que en el capitulo 0 dice que en
ese libro 2 no es considerado primo para simplificar los enunciados :) )
Y los griegos no considerban ni al 1 ni al 2 n�meros primos, pero por una
raz�n de lo m�s simp�tica: porque no los consideraban, de hecho, ni
siquiera numeros
-- m
-----------------------------------------------------------------------
Mariano Suarez Alvarez
Departamento de Matematica - Universidad Nacional de Rosario
Pellegrini 250 - Rosario 2000 - Argentina
De la observacion de la irreductibilidad de las creencias ultimas
he sacado la mayor leccion de mi vida. Aprendi a respetar las ideas
ajenas, a detenerme ante el secreto de las conciencias, a entender
antes de discutir, a discutir antes de condenar. Y como estoy en
vena de confesiones, hago una mas, quizas superflua: detesto con
toda mi alma a los fanaticos.
Norberto Bobbio, Italia civil.
-----------------------------------------------------------------------
