Factorització dels enters

De Viquipèdia
Dreceres ràpides: navegació, cerca

En matemàtiques i més precisament en teoria de nombres, la factorització dels enters és el procés de trobar un divisor no trivial (diferent del 1 i del mateix nombre) d'un nombre compost. 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 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, cóm escriure'l en forma d'un producte de nombres primers; per exemple, si el nombre donat és 45, la factorització en nombres primers és 32·5..

Per definició, un nombre primer no es pot descompondre. També es pot dir que és el resultat de la seva pròpia descomposició. Exemples:

11 = 11
25 = 5 × 5 = 52
125 = 5 × 5 × 5 = 53
360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 5
1.001 = 7 × 11 × 13
1.010.021 = 17 × 19 × 53 × 59

La factorització és sempre única, d'acord amb el teorema fonamental de l'aritmètica. Aquest problema és d'una importància considerable en matemàtiques, en criptografia, en teoria de la complexitat, i per als ordinadors quàntics.

Descomposició en nombres primers[modifica | modifica el codi]

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= 32·5, 45 llavors és divisible entre 30·50, 30·51, 31·50, 31·51, 32·50, i 32·51, é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[modifica | modifica el codi]

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 què 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[modifica | modifica el codi]

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(nk) independentment de quina sigui la constant k. Existeix algoritmes, no obstant això, que són més ràpids que (en). 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\over3} (\log b)^{2\over3}\right)\right)

Al 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 ser 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ó[modifica | modifica el codi]

De propòsit general[modifica | modifica el codi]

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:

De propòsit específic[modifica | modifica el codi]

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.

Altres algorismes[modifica | modifica el codi]

Article principal: ordinador quàntic
Article principal: Algorisme de Shor

Per a un ordinador clàsic, 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 cryptografia si algún día es construeix un gran ordinador quàntic. L'algorisme de Shor necessita només O(n3) en temps i O(n) en espai. Només es coneixen versionsde 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. Va factoritzar el nombre 15.

Vegeu també[modifica | modifica el codi]

Wikibooks A Viquillibres hi ha llibres de contingut lliure i altres textos relatius a Taula de factors primers


Enllaços externs[modifica | modifica el codi]

Referències[modifica | modifica el codi]