Seminario de Teoría de números

Resumen:

Se dice que el problema de factorizar es maleable si dado un módulo RSA n=pq, producto de dos primos, existe otro entero m cuya factorización permita encontrar los factores p y q en tiempo polinómico.

En 2006, Pailler y Villar hicieron la conjetura de que eso no era posible, es decir, factorizar no es un problema maleable. En este trabajo conjunto con L. Dieulefait probamos que la conjetura es falsa. Para ello utilizamos aritmética elemental, algunos resultados de distribución de números primos, y aritmética de curvas elípticas.