Factorización de sancers

En teoria de números, la factorización de sancers, factorización de cosins, factorización en cosins o arbre d'factorización consistix en descompondre un número compuesto (no primer) en divisores no trivials, que quan es multipliquen donen el número original.

Quan els números són molt grans no es coneix cap algoritme que resolga eficientemente este problema; un recent intent de factorizar un número de 200 dígits va tardar 18 mesos i va consumir més de mig sigle de temps de càlcul. La seua suposta dificultat és el núcleu de certs algoritmes criptográficos, com el RSA. Moltes àrees de les matemàtiques i de les ciències de la computació, com la teoria algebraica de números, les curves elíptiques o la computació quàntica, estan relacionades en este problema.

Descompondre dos números d'igual llongitut no té per qué tindre la mateixa complicació. Actualment (2006) es considera que els casos més durs són aquells per als que els factors són dos número primo, elegits a l'encert, d'aproximadament el mateix tamany.

Descomposició en factors primers

Archiu:PrimeDecompositionExample.svg

L'image demostra la descomposició en cosins del número 864. Un método ràpit d'escriure el resultat en número primo és $2^5\times 3^3$.

Pel teorema fonamental de l'aritmètica, cada sancer positiu té una única descomposició en número primo (factors primers). La major part dels algoritmes d'factorización elementals són de propòsit general, és dir, permeten descompondre qualsevol número introduït, i solament es diferencien substancialment en el temps d'eixecució.

$\begin{array}{cc}72& 2\\ 36& 2\\ 18& 2\\ 9& 3\\ 3& 3\\ 1& \end{array}$

$72=2^3\cdot 3^2$

Factorización de sancers en temps polinòmic

El problema de factorizar sancers en temps polinòmic no ha segut encara resolt en computació clàssica. Si algú ho conseguira, açò tindria gran interés en l'àmbit de la criptografia, ya que molts criptosistemas depenen de la seua impossibilitat. En mijos acadèmics, l'existència de tal alvanç seria una gran notícia; en atres círculs, seria un gran secret, per raons òbvies. Existix, no obstant, un algoritme per a computació quàntica, propost per Peter Shor, capaç de trobar la factorización d'un sancer en els seus factors primers en temps polinomial en error acotat, és dir, de classe BQP. Este descobriment va disparar l'interés en la computació quàntica i ya s'han construït alguns computadors quàntics d'uns pocs qubits, capaços de descompondre números menuts. S'espera que en els trements alvanços dels últims anys, pronte estos sistemes siguen capaços de descompondre números suficientment grans per a quebrantar els múltiples sistemes criptográficos que es basen en esta dificultat de descomposició.

Aplicacions pràctiques

La durea d'este problema, es troba en el núcleu de varis sistemes criptográficos importants. Un algoritme veloç per a la factorización de sancers significaria que l'algoritme de clau pública RSA és insegur. Alguns sistemes criptográficos, com l'algoritme de clau pública Rabin i el generador de números pseudoaleatorios Blum Blum Shub garantisarien una millora en la seua seguritat; qualsevol método que conseguixca quebrar-los pot ser utilisat per a crear un algoritme d'factorización més veloç; si la factorización de sancers és veloç, estos es tornen més durs. En contrast, poden existir atacs més eficients al problema RSA, pero no es coneix cap.

Un problema dur similar en aplicacions criptográficas és el problema del logaritmo discret.

Vore també

• Taula de factors primers

Referències

Bibliografia

• Donald Knuth. The Art of Computer Programming, Volum 2: Seminumerical Algorithms, Tercera Edició. Addison-Wesley, 1997. ISBN 0-201-89684-2. Secció 4.5.4: Factoring into Primes, pp.379–417.
• Richard Crandall i Carl Pomerance, Prime Numbers: A Computational Perspective, 2001, Springer, 1.ª edició, ISBN 0-387-94777-9, Capítuls 5-7.