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.

Hoy en dia si algun matematico encontrara alguna forma de acelerar de forma considerable la factorizacion del RSA , teniendo en cuenta las implicaciones que tendria (economicas, militares, etc), lo mas probable es que se lo callara y lo usara para proveerse algun tipo de beneficio o bien para evitar sufir algun accidente del tipo que sufrio el ingeniero Gerry Bull

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.

Oh dios, ¿un editor de barrapunto admitiendo que puede estar equivocado? Ah, espera, que es el bueno de Baranda y no poncho...

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!

Como cojones se le pueden dar puntos a un comentario de este tipo?!?!

He leido algo sobre el teorema de Godel y he creido entender que segun el, en las matematicas hay ciertas afirmaciones que nunca podra demostrarse si son ciertas o si son falsas, y, (esta segunda parte no lo tengo tan claro), que ni siquiera podemos saber que afirmaciones son indemostrables. En las matematicas siempre habra pozos oscuros.

Me pregunto si el orden que siguen los primos sera uno de esos pozos. Si algun dia podremos llegar a predecir en que lugar de la recta real esta el primo enesimo.

No deberiamos confiar tanto en el RSA. No podemos descartar que algun dia alguien descubra alguna propiedad de los primos hasta ahora desconocida, gracias a la cual aparezcan algoritmos de factorizacion con complejidad logaritmica. Entonces ni las claves de un millon de bits serian seguras.

pero estoy seguro de que todos los informaticos sin titulación universitaria, que tanto saben de Linux, de programación y de tal pascual podrán demostrar ahora todo lo que realmente saben.
Ya he avisado que no quería iniciar un flame, cada cual que se lo tome como le venga en gana :P

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

A ver, un par de cosas:

i) NO es lo mismo descubrir un algoritmo para factorizar un numero que para decir si es primo o no. Por lo tanto los "sistemas de criptorafia" basados en primos grandes estan seguros. NADIE sabe si el problema de la factorizacion es P o NP.

ii) Ya existia un algoritmo para decidir si un numero es primo o no en un tiempo polinomico (a decir verdad en un tiempo que crece como nlog(n), con n el numero de cifras). Por o tanto en este sentido ya se sabia que decidir si un numero es primo o no era un problema P y no NP.

Nada mas.

He leido algo sobre el teorema de Godel y he creido entender que segun el, en las matematicas hay ciertas afirmaciones que nunca podra demostrarse si son ciertas o si son falsas, y, (esta segunda parte no lo tengo tan claro), que ni siquiera podemos saber que afirmaciones son indemostrables La hipotesis del condinuo es indecidible, es decir que no puedes saber si es cierto o no. De hecho un profe de Analisis Funcional nos contó una vez que si supones que hay un conjunto de cardinal intermedio entre los enteros y los reales, todo funciona bien, y si no también (sólo cambia la teoría)¿curioso verdad?

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.
   

Ahora bien, ahora dirán que esto no tiene ningún interés para programar en Visual Basic o en JAvascript.
Es probable pero nin tan siquiera la programación más burda puede hacerse sin algoritmos más o menos complejos y tener unas nociones sólidas sobre complejidad algorítmica o decidibilidad matemática me parece básico para no hacer el burro.
Saludos

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 :-))

Estoy rodeado de titulados universitarios: matemáticos, informáticos diplomados, ... y sinceramente no conozco a ninguno capaz de demostrar nada. :-)

...también sería interesante ver a los que defienden a ultranza el Colegio de Ingenieros Informáticos reconocer la aportación de los "intrusistas" matemáticos al campo.

Ya vemos que tu aportación al debate ha sido muy productiva, se te ve puesto en matemáticas.

Quien fue Gerry Bull ??

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.

Creo que se refiere a un tipo interesado en hacer un super cañón capaz de poner en órbita pequeñas cargas, al final de su vida se decantó por venderlo al único interesado en su proyecto, Mr Sadam Hussein además de acordar con Mr Sadam participar en un proyecto de misiles, fue por esto que el servicio de inteligencia Israelí (probablemente) le pegó 5 tiros en la cabeza.

http://www.cse.iitk.ac.in/news/primality.pdf

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.

pues dada tu amplia demostracion de conocimientos no creo que los demas deban demostrar lo que tu antes no muestras

pero con ganas de aprender, si se pone a googlear sobre el tema durante un par de dias, (¿o horas?), deja en bolas a casi cualquier ingeniero/matematico.

E incluso si se lo propone, con la motivacion, tiempo y esfuerzo suficiente, tal vez años, eso si, se mete en la elite de personas que investigan la teoria de numeros orientada a la factorizacion de grandes numeros.

La base de toda la ciencia actual se desarrolló en un tiempo en que no existían universidades, sólo personas llenas de curiosidad y ávidas de conocimiento. Un título universitario se puede conseguir con tesón, tiempo, paciencia y disciplina. La inteligencia es innata.

Ya, pero la forma actual de romper el RSA y similares (si no recuerdo mal de lo que de en criptografia) es precisamente hallar cuales son esos primos. Para ello lo que se hace es hallar todos los numeros primos menores que el producto (que es lo que se pretende factorizar) y comprobar si este es divisible por alguno de ellos. Con este nuevo algoritmo, esa busqueda de primos es polinomial. Creo que es ahí donde radica la novedad. Para mi los dias de RSA estan contados.

Me parece, macho, que no tienes ni idea de lo que estas hablando.

Esta claro que NO hace falta ir a la universidad para aprender algo, todo esta en los libros, y en las hemerotecas de cualquier universidad publica, a la que puedes ir sin estar matriculado.

Pero para tener algo de idea de teoria de numeros, hay que saber bien Teoria de Conjuntos, algebra lineal, etc... Una cosa es que en un par de dias puedas aprender dos chascarrillas para vacilar con los colegas, pero saber de verdad teoria de numeros (no a un nivel para investigar, sino lo que podemos lamar una cultura matematica en ese campo), le lleva a una persona que halla acabado el equivalente de las matematicas de COU, por lo menos un año, y eso una persona con capacidad, con la base necesaria, y trabajando bastante.

En cuanto a trabajar a nivel investigador en este campo, te lleva no menos de 6 años. La gente que hace un doctorado (duranto 4 años, es capaz de hacer nada sin la "guia" de su director de Tesis).

Estas hablando de cosas bastante complicadas, no de entender como funciona el RSA solamente.

Por cierto, los ingenieros no tienen ni puta idea de nada de esto, a no ser que se lo hayan estudiado por gusto personal (igual que un matematico no sabe calculo de estructuras).

Una cosa es que en un par de dias puedas aprender dos chascarrillas para vacilar con los colegas, pero saber de verdad teoria de numeros (no a un nivel para investigar, sino lo que podemos lamar una cultura matematica en ese campo), le lleva a una persona que halla acabado el equivalente de las matematicas de COU, por lo menos un año, y eso una persona con capacidad, con la base necesaria, y trabajando bastante.

Recuerdo que en tercero de bup nos tiramos 3 o 4 meses para aprender a derivar, (si, la profesora que tuve era bastante mala). Cuando tuve que prepararme las derivadas para dar clases particulares, me sorprendio que pude condensar toda la teoria en una hora de clase, y los problemas en otra. Esto es extrapolable a lo que tu cuentas.

Una persona con la motivacion adecuada e informacion de calidad puede hacer maravillas, es mi opinion.

En cuanto a trabajar a nivel investigador en este campo, te lleva no menos de 6 años. La gente que hace un doctorado (duranto 4 años, es capaz de hacer nada sin la "guia" de su director de Tesis).

Estas hablando de cosas bastante complicadas, no de entender como funciona el RSA solamente.

Lo se. Por eso distingo entre esos dos niveles, el que puede cogerse en un par de dias con el que ya podrias tener conversaciones sobre el tema, y el que tardarias años en coger, con el que podrias publicar algo en alguna revista especializada y de calidad, algo que hiciera avanzar de alguna manera el estado del arte del tema que escojas. Bueno, o si no ir mas alla de a donde se ha llegado, si por lo menos ser capaz de comprender hasta donde se ha llegado.

Todo se puede aprender. Desde que tenemos la red lo que nos limita es la motivacion, no el acceso a la informacion, por lo menos con respecto al tema del que hablamos. En las news y listas de correo especializadas tenemos todos los tutores que queramos.

>"RecuRecuerdo que en tercero de bup nos tiramos 3 o 4 meses para aprender a derivar, (si, la profesora que tuve era bastante mala). Cuando tuve que prepararme las derivadas para dar clases particulares, me sorprendio que pude condensar toda la teoria en una hora de clase, y los problemas en otra. Esto es extrapolable a lo que tu cuentas. erdo que en tercero de bup nos tiramos 3 o 4 meses para aprender a derivar, (si, la profesora que tuve era bastante mala). Cuando tuve que prepararme las derivadas para dar clases particulares, me sorprendio que pude condensar toda la teoria en una hora de clase, y los problemas en otra. Esto es extrapolable a lo que tu cuentas. "

No 4s comparable en abnsoluto. El tener una "cultura matematica" en teoria de numeros, es comparable a entender del orden de 200 conceptos vomo el de derivar. Para entender bine la derivada no basta con saber derivar cualquier funcion, y para saber teoria de numeros no basta con saber los resultados, hay que saber las demostraciones del pequeño teorema de Fermat, del teorema hino del resto, del teorema de los numeros primos, de un millon de cosas, las cuales cuesta bastante entender (lo digo por experiencia)

>"Una persona con la motivacion adecuada e informacion de calidad puede hacer maravillas, es mi opinion. "

Cierto, pero casi todo el mundo que se dedica a la investigacion en casi cualquier area de las matematicas teoricas hace maravillas, le dedica 8-10 horas al dia de despacho a investigar y 14h de cabeza pensando en esos temas, asi que no te creas que los que hacen investigacion se tocan los huevos, y tu vas a dedicarle mas tiempo que los demas.

>"Por eso distingo entre esos dos niveles, el que puede cogerse en un par de dias con el que ya podrias tener conversaciones sobre el tema"

Mira, tio, en un par de dias con el unico que puedes tener "discusiones" es con uno que lleve tambien un par de dias, porque con culquiera que se dedique a esto lo que tu con tu par de dias le cuentes son trivialidades!!!

La investigacion es MUCHO MAS DIFICIL DE COMO TU LA PINTAS, te lo digo con conocimiento de causa, y si no vete a "discutir " a una universidad, con un grupo en teoria de numeros, y veras que estan casi siempre te ves a años luz de donde ellos estan, ya no hablemos de ublicar algo nuevo...

Todo se puede aprender, esta claro, pero decir que en un par de dias puedes tener "discusiones" de algo es sencillamente mentira. Genet muy lista se dedica a esto en odo el mundo, y tener siquiera una idea globla de para que valen las cosas que investigas requiere un par de años.

Todo se puede aprender dedicandole muuuuuuuuuuuuuucho tiempo, como a cualquier trabajo, que le dedicas minimo 8h diarias, y asi al final de 4 años, se supone que con ayuda de una persona que sabe muuucho del tema, has conseguido hacer algo, asi que ni muvho menos esto es tan facil como parece.ç

Otra cosa es tener una idea a nivel divulgativo de como funciona la criptografia, etc... sin entrar en detalles. Pero la realidad es que toda la investigacion, y todas las discusiones interesantes de un t3ema estan en los detalles.

No 4s comparable en abnsoluto. El tener una "cultura matematica" en teoria de numeros, es comparable a entender del orden de 200 conceptos vomo el de derivar. Para entender bine la derivada no basta con saber derivar cualquier funcion, y para saber teoria de numeros no basta con saber los resultados, hay que saber las demostraciones del pequeño teorema de Fermat, del teorema hino del resto, del teorema de los numeros primos, de un millon de cosas, las cuales cuesta bastante entender (lo digo por experiencia)

No dije comparable, dije extrapolable. En la hora de teoria que enseñaba a derivar cualquier funcion tambien explicaba el concepto de derivada.

La investigacion es MUCHO MAS DIFICIL DE COMO TU LA PINTAS,

La clave esta en la motivacion. Supongo que tambien es dificil correr maratones y rodar una media de 15 kilometros diarios, pero hay gente que si no lo hace le da algo, lo necesita.

Echale un vistazo a esta web y luego dime si no es posible lo "imposible".

Todo se puede aprender dedicandole muuuuuuuuuuuuuucho tiempo

Estamos de acuerdo.

no te creas que los que hacen investigacion se tocan los huevos

Yo no he dicho eso.

y tu vas a dedicarle mas tiempo que los demas.

No estaba hablando de mi, sino de alguien con la motivacion adecuada. Cuando digo adecuada me refiero a muuuuucha motivacion.

Otra cosa es tener una idea a nivel divulgativo de como funciona la criptografia, etc... sin entrar en detalles. Pero la realidad es que toda la investigacion, y todas las discusiones interesantes de un t3ema estan en los detalles.

Ahi esta la distincion que hice al principio entre el nivel que coges en varias horas o dias de googleo y el que podrias coger en varios años.

Ah.. y cuando dije tercero de bup, quise decir segundo de bup.

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.

Eso, que hacen falta 25 punto de karma para el salto cualitativo. Lo mejor es la opción de quitarte uno y aumentar el margen para los puntos de moderación positivos o disminuirlo para los negativos.

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

Es bastante difícil romper RSA probando "todos" los primos hasta la raiz cuadrada, si el número a factorizar es de 512 bits (ya en desuso), los factores primos tienen 256 bits, y para números de 256 bits, cada 176 uno es primo, aunque pudieras saber en un tiempo mínimo cuales son dichos primos, habría que hacer la división para saber si es un factor del número dado, y 2^256/176 divisiones son muchas divisiones.
Un saludo