Barrapunto

No es sólo una cuestión de belleza matemática: La facilidad para hallar primos en un tiempo polinomial implica la facilidad de factorizar por fuerza bruta cualquier número grande, es decir, los números utilizados para los sistemas de clave pública. Y el crecimiento de las claves siempre provoca un crecimiento del tiempo de factorización, pero ese crecimiento ahora es, precisamente, polinomial, es decir, que no es exponencial. x^32 es muchísmo mayor que e^x hasta una cierta x, pero a partir de ese punto x^32 es menor para siempre. Y da igual si cambias 32 por cualquier otro número mayor, o cambias e por cualquier otro número menor (siempre que sea mayor que 1): La exponencial siempre acaba superando a la polinomial.

Baranda comenta: "Por lo que yo sé, los algoritmos rápidos actuales determinan si un número es primo sólo con una cierta probabilidad (normalmente muy alta), y no siempre pueden decidir en tiempo finito."

Efectivamente, los algoritmos que se usan en criptografía calculan la probabilidad con la que un número es primo. En realidad, los más potentes y los que se usan, permiten saber hasta una probabilidad dada si un número es primo o no, de forma que podemos generar números pseudoaleatorios primos con un 99,999% de certeza (por ejemplo).

El tiempo requerido por estos algoritmos es siempre finito (al contrario de lo que dice la noticia), aunque quizá no se pueda saber de antemano el tiempo requerido. Es decir, los algorimos siempre dan una respuesta.

http://www.cse.iitk.ac.in/users/manindra/primality .ps

Pongamos los puntos sobre las íes y las jotas. Un algoritmo que fuese capaz de factorizar números primos en tiempo polinómico serviría para romper los criptosistemas que se basan en primos grandes. Pero no es lo mismo saber si un número es primo o no que hallar sus factores. En este caso, el algoritmo hace lo primero; pero no lo segundo... Podemos seguir confiando en los criptosistemas asimétricos, de momento.

Puedo estar equivocado, sólo he leido literatura de divulgación sobre esto. Pero creo que ocurre con la mayoría de los algoritmos probabilísticos para determinar si un número n es primo es que, no se conoce a priori un tiempo t tal que el tiempo en decidir que n es primo con una probabilidad p es menor que ese tiempo t. Lo que no es exactamente que no terminen en tiempo finito, reconozco. ¿Estoy equivocado?

Corregido. Gracias. Se me escapó :-(

La posibilidad es realmente muy alta (más que 99,999 %). De hecho, es casi más fiable que el método determinístico.

Es mucho más probable un fallo del procesador que haga que el método determinístico sea erróneo a que este algoritmo falle. Por tanto, si un algoritmo estadístico de este tipo te dice que es primo... puedes estar seguro de que lo es. Nunca podrás obtener mayor certeza de que lo sea.

Puedes repetir 100 millones de veces el método determinista, y seguramente dará más certeza que el estadístico.

Vamos que el argumento que das es como aquel que todos los niños hacen de que dos errores me dan un acierto...

Seguro que el algoritmo ese es seguro de usar y tal, pero mas que el determinístico...

Saludos!

Claro que durante le ejecucion del metodo estadistico tambien pueden ocurrir fallos de procesador, asi que por lo menos ahi quedan empatados...

Vienen de série ;-)

...lo que significa que cuando eres un usuario registrado con ciertos puntos de karma (creo que 20) tus comentarios tienen de base 2 puntos, sin mediar moderación o la madre que la parió.

Para mí que es un incentivo al registro, amén de los comentarios potencialmente intersantes (puntuables), totalmente diferentes de éste, por supuesto.
   

Ni la titulacion, ni Linux te hace brillante en matematicas :-) es mas, desgraciadamente muchos que han sido brillantes en matematicas, titulados o no... andan por ahi intentando buscar un curro decente en un tiempo discreto. Porque, la verdad todo eso que han aprendido en la carrera o por cuenta propia esta criando moho entre visitas a infojobs.

Naturalmente, cuando hay ocasion de demostrar si sabes o no algo, al entrevistador de turno le importa tres rabanos el Teorema de Godel, la Fi de Euler o las curvas elipticas. Realmente lo que le interesa al 'encargado de recursos humanos', (es decir al capataz), es un tio que le salga barato, que haga las cosas para ayer y 'que funcionen y ya esta', y sobre todo que haga horas extras 'por compromiso con el proyecto'. Los puestos de trabajo en los que esta involucrada la gente Licenciada, experta en Matematicas y que ademas tengan que utilizar esos conocimientos... son minimos.

P.D. A mi personalmente lo que has dicho me parece un Flame en toda regla :-) (de los alimentados por gas), de desprecio al projimo y prepotencia ya no hablo que nos quemamos :-))

Lo que dices es correcto. Sin embargo, que no sepamos en que tiempo t acabará el algoritmo, no es lo mismo que decir que el tiempo de calculo no sea finito.

Si tenemos la certeza de que acabará el calculo en todos los casos, el tiempo de cálculo es finito.

En caso contrario, debería haber algun caso en el que el calculo probabilístico convergiera en el infinito a una probabilidad dada. Sin embargo esto no parece que pueda ocurrir con los algorítmos que se usan (lo siento, no tengo la bibliografía a mano y hace un par de años que estuve tocando este tema). De hecho, una convergencia tal debería indicar que el número no es primo. 8)

Teniendo en cuenta que tanto el algoritmo determinístico como el probabilístico pueden verse afectados por fallos de procesador, y el imprevisible efecto que este produciría, no es posible sacar ninguna conclusión en favor de una u otra.

Los métodos determinísiticos siempre son más fiables, de hecho totalmente fiables (100% de probabilidad/certeza) (a no ser que el método no sea válido claro). Los probabilísticos son fiables hasta el umbral de certeza que se quiera, por lo cual nunca te dan una seguridad pareja a los métodos deterministas.

El problema es siempre buscar un buen equilibrio entre tiempo de proceso y certeza. Los algoritmos probabilísticos, en certezas razonables (del orden de 99,999%) suelen ser muchísimo más rápidos que los deterministas.

"la probabilidad de que las rutinas de generación de números primos den como resultado un número compuesto en lugar de primo (es decir que el número pase los tests probabilísticos) para una clave de 1024 bits (es decir un candidato a primo de 512 bits) son 10-44 (aprox. 2-146).

Por poner las cosas en perspectiva, la probabilidad de que otro asteroide mata-dinosaurios golpee la tierra HOY son de 2-36"

Lamentablemente, no encuentro las fuentes donde leí el ejemplo del procesador. Es evidente que el método probabilístico nunca va a ser más seguro que el determinístico. Pero en este caso, dada la fiabilidad del metodo probabilístico, la certeza que obtienes es igual en ambos caso. Esto es así porque la probabilidad de que NO sea primo es menor que la probabilidad de un fallo del procesador.

En resumen. Las posibilidades de que los dos métodos fallen y te den como primo un número que no lo es, es la misma.

PD: Me suena que leí lo del procesador en SET-EZINE...

   

Hasta donde llegan mis matemáticas los números primos sólo son divisibles entre sí mismo y la unidad, por lo que no se pueden factorizar.

Cierto, menudo fallo... Más que no poderse factorizar, la factorización es trivial (el factor primo es el propio número). Supongo que, de todos modos, se puede sobreentender lo que en realidad quería decir: en los criptosistemas asimétricos lo que se usa es un producto de números primos grandes (que obviamente no es primo), y es esto lo que conviene factorizar para romper el criptosistema. Y este algoritmo no puede hacer dicha factorización, sino que sólo nos dirá que ese producto no es primo, cosa que no rompe nada.

Me he demostrado lo "primo" que puedo llegar a ser por coleccionar títulos universitarios

a) Los algoritmos de factorización incluyen tests de primalidad, por lo tanto un buen algoritmo para determinar rápidamente si un numero es primo o no también es importante para los problemas de factorización.

b) Lo de nlog(n) no es válido para los tests de proposito general, aplicables tanto a números pequeños como grandes, puede que sea válido para algún subconjunto particular, o para números pequeños. Además la función logaritmica está siempre por debajo de y=x para valores de la base mayores que 1, eso quiere decir que n < nlog(n) < n*n. Está entre la función lineal y la cuadrática. De hecho es el tiempo medio para el algoritmo quick-sort.

Para que queden más claras las cosas ahí van algunos datos:
- 1983. Algoritmo determinista. (log n)^O(log log log n)
- 1986. Algoritmo probabilistico basado en curvas elipticas. Tiempo polinomial.

El algoritmo del que estamos hablando es universal, incondicional, determinista y Ô((log n)^12), es decir sitúa el chequeo de primalidad dentro de P, lo hace por primera vez en la historia y además lo hace de una forma simple y elegante: se deriva del teorema chino del resto.

Por último una referencia básica sobre los tests de primalidad, aparte de la propia publicación

Nada menos.

Pero... no existía antes "aporte" para decir eso mismo...
Como dijo Julio Cesar: "tu también, Bruto..."