Factorització dels enters

En teoria de nombres, la factorització dels enters és el procés de trobar quins nombres primers es multipliquen per fer un nombre compost, doncs els divisors no trivials (diferent de l'1 i del mateix nombre). Aquests nombres primers és diuen «factors».

Si es té un algorisme per factoritzar qualsevol enter llavors el mateix algorisme serveix per factoritzar-lo en factors primers a base d'aplicar el mateix algorisme repetidament fins que tots els factors siguin nombres primers. Aquesta factorització es coneix com a descomposició en producte de factors primers o factorització en nombres primers i és el procés de resolució del problema següent: sigui un enter estrictament positiu, com escriure'l en forma d'un producte de nombres primers; per exemple, si el nombre donat és 45, la factorització en nombres primers és 3² × 5. La factorització entera és única, llevat de l'ordre dels factors i la multiplicitat de les unitats positiva i negativa (1 i -1).

Per definició, un nombre primer no es pot descompondre. També es pot dir que és el resultat de la seva pròpia descomposició. La factorització és sempre única, d'acord amb el teorema fonamental de l'aritmètica. Ja el 1801, el matemàtic Carl Friedrich Gauss a les seves Disquisicions artimètiques el va assenyalar com un dels grans problemes de l'aritmètica. Té una importància considerable en criptografia, en teoria de la complexitat i per als ordinadors quàntics.

Exemples

11 = 11

25 = 5 × 5 = 5²

125 = 5 × 5 × 5 = 5³

360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5

1.001 = 7 × 11 × 13

1.010.021 = 17 × 19 × 53 × 59

Descomposició en nombres primers

Tot nombre natural n no nul es pot escriure de manera única com el producte finit de nombres primers elevats a una potència adequada.

$\forall n\in \mathbb {N} ^{*},\exists !(\alpha _{p})_{p\in {\mathcal {P}}}\in \mathbb {N} ^{({\mathcal {P}})}:n=\prod _{p\in {\mathcal {P}}}p^{\alpha _{p}}$.

La llista completa dels divisors d'un nombre pot ser deduïda de la descomposició en factors primers incrementant els exponents de zero fins al nombre buscat. Per exemple, com que 45= 3²·5, 45 llavors és divisible entre 3⁰·5⁰, 3⁰·5¹, 3¹·5⁰, 3¹·5¹, 3²·5⁰, i 3²·5¹, és a dir els seus divisors són 1, 5, 3, 15, 9, i 45. En canvi la descomposició en factors primers inclou només els factors primers.

Aplicacions pràctiques

Siguin dos nombres primers grans donats, és fàcil obtenir-ne el producte. En canvi, és molt més difícil trobar els factors primers d'aquest producte. És el que es diu una funció unidireccional. Això s'aplica en els sistemes moderns en criptografia. La base està en el fet que el xifratge es fa coneixent el producte però per fer el desxifratge cal conèixer la factorització. Si es trobés un mètode ràpid per resoldre el problema de la factorització dels nombres enters, llavors es podrien trencar diversos sistemes criptogràfics importants, incloent l'algorisme de clau pública RSA i el generador de nombres pseudoaleatoris Blum Blum Shub. La posada a punt d'un ordinador quàntic és un d'aquests mètodes.

Encara que la factorització sigui una manera de trencar aquests sistemes, poden existir-ne d'altres que no impliquin la factorització. Així, és possible que el problema de la factorització entera sigui verdaderament difícil, però que aquests sistemes puguin ser trencats ràpidament. Una excepció rara és el generador Blum Blum Shub. S'ha demostrat que és exactament igual de difícil com la descomposició en producte de factors: si es pot trencar el generador en temps polinòmic llavors, es pot factoritzar els enters en temps polinòmic, i viceversa.

Dificultat i Complexitat

Si un nombre de n bits és el producte de dos nombres primers que són probablement de mida similar, llavors actualment no hi ha cap algorisme publicat per poder factoritzar-lo en temps polinòmic. El que vol dir aquesta afirmació és que no existeix cap algorisme publicat que pugui factoritzar-lo en temps O(n^k) independentment de quina sigui la constant k. Existeix algoritmes, no obstant això, que són més ràpids que (eⁿ). En Altres Paraules, els millors algorismes publicats són subexponencials, però superpolinomics. En particular, el millor algorisme publicat que compleixi en temps asimptòtic és el garbell general del cos de nombres (GNFS), la seva complexitat és:

$O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}b\right)^{1 \over 3}(\log b)^{2 \over 3}\right)\right)$

En analitzar les classes de complexitat del problema de la factorització dels enters, cal distingir dues versions del problema lleugerament diferents:

• La versió problema funció: donat un enter N, trobar un enter d amb 1 < d < N que sigui divisor de N (o concloure que N és primer si no n'hi ha cap). Aquest problema és evidentment FNP i no se sap si té complexitat FP o no. Aquesta és la versió del problema que resolen la majoria de les implementacions pràctiques.
• La versió problema decisió: donat un enter N i un enter M amb 1 ≤ M ≤ N, té N un factor d amb 1 < d < M? Aquesta versió és útil perquè les clases de complexitat que han estat més estudiades són classes de problemes decisió, no de problemes funció. Aquesta versió del problema en forma de decisió és una elecció natural perquè es pot combinar amb una cerca binaria per resoldre la versió funció del problema en una quantitat logarítmica que decisions.

No se sap exactament quines classes de complexitat conté el problema de factorització d'enters. Se sap que la seva forma de decisió-problema (" Té N un factor menor que M? ") té complexitat NP i co-NP. Això és perquè tant la resposta Si com la resposta No es poden comprovar si es tenen els factors primers amb els seus certificats de primalitat. Se sap que és de classe BQP gràcies a l'algorisme de Shor. Se sospita que es troba fora de les tres classes de complexitat (P, NP Complet, co-NP Complet). Si fos possible provar que és de qualsevol d'aquestes dues últimes, això implicaria que NP = co-NP. Aquest seria un resultat molt sorprenent, i per això se sospita que la factorització d'enters es troba fora d'ambdues. Molta gent ha intentat trobar algoritmes clàssics de temps polinòmic, i ha fallat; per això se sospita que es troba fora de P.

Curiosament, un problema de decisió diferent però relacionat, el problema: " és N un nombre compost? " (o el que és el mateixl: " és N un nombre primer? ") sembla molt més senzill que el problema de trobar els factors en els quals es descompon N. En concret, pot ser resolt en temps polinòmic. Vegeu test de primalitat

Algorismes de factorització

De propòsit general

El temps d'execució d'un algorisme de factorització de propòsit general depèn només de la mida de l'enter a factoritzar. Aquest és el tipus d'algorisme que es fa servir per factoritzar nombres RSA. La majoria d'algorismes de factorització de propòsit general estan basats en el mètode de congruència de quadrats. A continuació es llisten alguns dels algorismes de propòsit general més coneguts:

• Algorisme de Dixon
• Factorizació amb fraccions contínues
• Garbell quadràtic
• Algorisme general de garbell de cos de nombres
• Factorizació de formes quadrades de Shanks

De propòsit específic

El temps d'execució d'un algorisme de factorització de propòsit específic depèn de les propietats dels seus factors desconeguts: mida, forma especial, etc. Dits factors canvien d'un algorisme a l'altre.

• Factorització per prova de divisions
• Algorisme rho de Pollard
• Algorisme p-1 de Pollard
• Algorisme p+1 de Williams
• Factorització de corba el·líptica de Lenstra
• Mètode de factorització de Fermat
• Algorisme especial de garbell de cos de nombres

Algorisme de Shor

• Article principal: Algorisme de Shor

Per a un ordinador clàssic, GNFS és el millor algorisme publicat per als n grans. Per a un ordinador quàntic, en canvi, Peter Shor va descobrir un algorisme el 1994 que ho resol en temps polinòmic. Això tindrà implicacions significatives per a la criptografia si algun dia es construeix un gran ordinador quàntic. L'algorisme de Shor necessita només O(n³) en temps i O(n) en espai. Només es coneixen versions de l'algorisme que requereixen la utilització de 2n qubits. El 2001, el primer ordinador quàntic de 7-qubit va executar l'algoritme de Shor i va factoritzar el nombre 15.

Bibliografia

• Alpern, Dario. «Integer factorization calculator (Factorització de nombres emprant corbes el·líptiques» (en anglès), 18-09-2019.
• Brent, Richard P. Recent Progress and Prospects for Integer Factorisation Algorithms (en anglès). 1858. Berlín, Heidelberg: Springer Berlin Heidelberg, 2000, p. 3–22. DOI 10.1007/3-540-44968-x_2. ISBN 9783540677871. 
• Crandall, Richard E.; Pomerance, Carl. Prime numbers : a computational perspective (en anglès). Nova York: Springer, 2001, p. capítols 5-7. ISBN 0387947779. 
• Knuth, Donald Ervin. «4.5.4: Factoring into Primes». A: The art of computer programming (en anglès). volum 2: Seminumerical Algorithms. 3a edició. Reading, Mass.: Addison-Wesley Pub. Co, 1973-1981, p. 379–417. ISBN 0201038099. 
• Weisstein, Eric W. «RSA-640 Factored» (en anglès). MathWorld News, 08-11-2005. [Consulta: 7 novembre 2019].

Enllaços externs

• Calculadora en línia per trobar els factors: LLC, CalculatorSoup. «Prime Factorization Calculator» (en anglès). [Consulta: 7 novembre 2019].