domingo, 30 de marzo de 2008

Hugo Scolnik: Avances en la Factorización Entera


El pasado 3 de diciembre se celebró el II Día Internacional de la Seguridad en la Información (DISI 2007). En el, Hugo Scolnik presentó un nuevo algoritmo de factorización, que aunque está por terminar, no tiene mala pinta.

A continuación dejo los enlaces (Criptored) a la presentación y el vídeo de la conferencia:
Estos archivos pueden descomprimirse en Línux con el siguiente comando:

$ cat *.z* > video.zip && unzip video.zip


En el foro de Kriptopolis, alguien que firmaba como "Hugo Scolnik" ponía un ejemplo sencillo de factorización:


Pues ahi va un ejemplo pequeño para ilustrar el tema
Sea n = 507527
Los targets únicos son (23 en total):
(1,0,3) , (1,0,4), (4,1,5),....,(649,576,720)
Esto significa que x^2 = 1+3t(1) = 1+4t(2)=...= 649+720t(23)
con t(23) = 88 se consigue la soluciòn
Con respecto a y^2 tenemos que puede escribirse como 576+720u(23) con u(23) = 793
Obviamente con n grande es impracticable buscar los valores de t o de u.
Ahora, (n + 649 -576)/720 = 705 y algunos targets ùnicos de 705 son
(0,1,4) , (0,1,8), (0,1,16)

Llamaremos (a1,b1,c1) al target ùnico elegido del primer nivel, o sea (649,576,720) y
(a2,b2,c2) al del segundo nivel

Si usamos el primero con la fòrmula x^2 =a1+c1a2+c1c2t = 649+2880t correcto con t = 22
Si usamos el segundo obtenemos x^2 = 649+5760t correcto con t = 11
Pero el tercero da x^2= 649+11520t que es FALSO (deberìa dar x^2 = 6409+11520t)

¿Còmo corregir 649 ? Habrìa que sumarle deltax2 = 5760 = 8c1 (siempre es un mùltiplo de c1)
Para y^2 obtenemos y^2= b1+c1b2+c1c2u
En el primer caso y^2 = 1296+2880u correcto con u = 198
En el segundo caso y^2 = 1296+5760u correcto con u = 99
El tercero falla pues da y^2 = 1296+11520u y deberìa ser 7056+11520u

La correcciòn es deltay2 = 5760 que es igual a deltax2
Varios de los teoremas que mostrè ràpidamente tienen que ver con las correcciones, su relaciòn con las ecuaciones
diofánticas, etc. Casos muy interesantes son los simètricos, donde aparecen en el nivel k > 1 targets ùnicos
idènticos a los del primer nivel (al parecer siempre existen pero todavìa no nos dedicamos a demostrarlo porque
hay otras prioridades). Para ellos se pueden demostrar varios resultados muy interesantes, y ahora los estoy
usando para la exploraciòn de las ramas provenientes de las posibles elecciones de targets.

Cordialmente
Hugo Scolnik