El diccionario de la lengua Española dice para factorizar: Expresar un número entero como producto de sus divisores. Perfecto pero con matices, la factorización, respecto de los números enteros, tiene dos visiones en función del contexto:
- Factores primos. Es el proceso de descomponer un número en sus factores primos, es decir, dividirlo por números primos y obtener la relación de los mismos y escribir ese número como un producto de los primos obtenidos. Dicho de otra forma, todo número entero positivo se puede descomponer como el producto de dos o más números primos elevados a una potencia. Sólo existe una única solución.
- Factores. En este caso es indiferente que los números sean o no primos, es el problema inverso a la multiplicación. Dado n, se trata de encontrar un conjunto de números tales que su producto valga n. En este caso se pueden obtener varias soluciones.
A partir de ahora hablaremos de factorización como la obtención de factores primos. La importancia de la factorización radica, hoy, en el cifrado de clave pública y su relación con las actividades económicas y de seguridad. La dificultad de factorizar grandes enteros es la base del cifrado de clave pública y quien esté en disposición de factorizar esos números, de forma rápida, tiene un enorme poder en sus manos. En la actualidad (2.014) no se conoce ningún algoritmo de factorización eficiente no cuántico y éste actualmente no es viable.
La factorización no sólo tiene la inconveniencia de la elección del algoritmo, sino la problemática con determinados números, los más difíciles de factorizar son aquellos que son productos de dos números primos de tamaño similar, por esta razón, estos son los enteros utilizados en aplicaciones criptográficas.
Las primeras formas de transmisión de los números factorizados fue mediante tablas que los contenían y que se publicaban con gran trascendencia en el ámbito científico, pero que dejaron de tenerlo cuando los dispositivos mecánicos y electrónicos comenzaron a desarrollarse.
La evolución en el tiempo de números factorizados podemos verla en la siguiente tabla:
Avanzamos unos pocos de años y la carrera sigue, ahora ya no es con lápiz y papel sino con algoritmos para computadores y continuamos compitiendo, pasados otros pocos de años la computación cuántica nos permitirá dar un salto tan grande que lo que hoy nos parece increíble estará trasnochado. Estamos completamente seguros que seguiremos compitiendo
| Últimas factorizaciones |
| Año | Autor | Comentarios |
| 2.017 | Samuel Wagstaff | 22246 + 1 = 10668670230000179802365738756155613324642694467793437268722465236229 x … |
| 2.017 | R. Propper | 21563 – 1 = 2281545765135387055770463020534665082129848151230492922548825535349609 x … |
| 2.012 | Greg Childers y otros | 21061 – 1 = 468172263510722656207776706750069723016189792142528328750689763038394004 13682313921168154465151768472420980044715745858522803980473207943564433 x 527739642811233917558838216073534609312522896254707972010583175760467054 896492872702786549764052643493511382273226052631979775533936351462037464 331880467187717179256707148303247 |
| 2.006 | Shimoyama Takeshi – Fujitsu Laboratories LTD | 7352 + 1 = 45493637292816464852067014736571339792315419859784218076875841 x 241856301831338437537787898096062692359819543303619864074410382977 |
| 2.002 | F. Bahr – J. Franke – T. Kleinjung |
2953 + 1 = 3388495837466721394368393204672181522815830368604993048084925840555281177 x 11658823406671259903148376558383270818131012258146392600439520994131344334162924536139 |
| 1.981 | Richard Brent – John Pollard | 2256 + 1 = 1238926361552897 x 93461639715357977769163558199606896584051237541638188580280321 |
| 1.975 | Brillhart – Morrison | 2128 + 1 = 59649589127497217 x 5704689200685129054721 |
Algunos expertos pronosticaron:
- 1.874 William Stanley Jevons: “Tomando dos números cualquiera podemos obtener rápidamente su producto, ¿Puede el lector decir qué dos números multiplicados producen el número 8.616.460.799?, el trabajo probablemente ocuparía una buena calculadora durante muchas semanas”. Ponemos esta cita por la importancia que tiene y la conexión con RSA.
- En la década de 1.960, John Brillhart y John Selfridge predijeron que factorizar números de ? 25 dígitos sería muy difícil.
- 1.976 Richard Guy: “Me sorprendería si alguien factorizase en este siglo, números del tamaño 80 dígitos”
- 1.977 Ron Rivest: “factorizar un número de 129 dígitos llevaría más de 4 × 1016 de años”. En 1.994 se factorizó el RSA-129, propuesto por Rivest, con sólo 8 meses de trabajo y mediante la criba cuadrática.
Si hay alguna lección en todo esto es, hacer predicciones en el mundo de los números es equivocarse, o casi.
Hemos factorizado hasta 3 mil millones para obtener los primos más comunes y los resultados son los de la tabla de abajo, no existen diferencias significativas entre los 3 márgenes establecidos
Un ejemplo básico en lenguaje Java para grandes enteros.
