18 feb. 2014

Un vistazo al método de factorización de Hugo Scolnik

Hace unos años se habló en el antiguo Kriptópolis de Hugo Scolnik, que estaba desarrollando un método de factorización de tiempo polinómico. Desde entonces poco se ha vuelto a saber, y lo poco nuevo no parece haber tenido mucha repercusión. Desde que ví el enlace, he estado buscando regularmente en Internet posibles avances y noticias, pero no he encontrado mucho. Durante bastante tiempo, el único documento que encontré que explicaba un poco su método fue éste (hay otros enlaces con documentos similares que se pueden encontrar fácilmente). Hace unos meses encontré por casualidad otro documento, del 2011, en el que se explicaban un poco más sus avances.

Cuando leí el primer trabajo de Hugo Scolnik me encontré con un punto en el método a partir del cual no lograba entender cómo se obtiene la factorización de los enteros, y es en el cálculo de la delta, que dice que factorizar el valor de esta delta es equivalente a factorizar el entero. Cuando leí el segundo trabajo con detenimiento ya lo comprendí. A pesar de todo, sin duda hay mucho más que esto para obtener la factorización, porque si no, Hugo Scolnik ya habría resuelto el problema y sería mundialmente conocido... bueno, en realidad ya es mundialmente conocido... pero sería mucho más mejor conocido.

Desde que leyera por primera vez su documento he estado intentando comprender el método. En este intento por comprender he encontrado dos enfoques diferentes, equivalentes al enfoque original de Hugo Scolnik, uno de los cuales es el que voy a explicar aquí. Lamentablemente el método de Hugo Scolnik, desde el punto de vista que explico aquí, todavía es inaplicable, no porque el método esté mal, sino porque las propiedades de los elementos matemáticos que permitirían directamente la factorización están limitadas a valores muy pequeños.

De hecho, el método de Hugo Scolnik es de lo más acertado, y de no existir esta limitación, hace tiempo que se habría encontrado un método de factorización de tiempo polinomial (respecto al número de bits del entero a factorizar) muy rápido (permitiría factorizar enteros grandes (más de 1000 bits) en cuestión minutos, quizá en segundos). Lo explicaré.

Contenido completo en fuente original Kriptopolis

0 comentarios:

Publicar un comentario

Gracias por dejar un comentario en Segu-Info
Si vas a dejar una consulta, procura tener habilitado tu perfil en Blogger o deja una forma de contacto.

Gracias por comentar!