Zenbaki osoen faktorizazio

Zenbaki osoen faktorizazioa, zenbakien teorian, zenbaki oso bat zenbaki lehenen biderketa bezala adieraztean datza.

Zenbakiak oso handiak badira ez dago arazo hau efizienteki konpondu dezakeen algoritmorik. Adibidez, 232ko digitu zenbaki bat faktorizatzeko, 100 konputagailuko kluster batek 2 urte behar izan zituen, 2009an.

Baina digitu kopuruak ez du konplexutasunarekin zerukusirik; faktorizatzeko kasu zailenak, uste denez, bata bestearen gertu dauden bi zenbaki lehenen biderketa bezala faktorizatzen diren zenbakiak dira.

Matematikako eta konputagailuen teknologiako arlo asko arazo hau konpontzeko sortu dira, hauen hartean konputazio kuantikoa, zenbakien teorema algebraikoa eta kurba eliptikoak.

Faktorizazioa faktore lehenetan 
Aritmetikaren oinarrizko teoremaren arabera, edozein zenbaki oso zenbaki lehenen (faktore lehen) konbinazio bezala idatzi daiteke. Faktorizazioaren algoritmo gehienak helburu orokorrekoak dira, hau da, edozein zenbakirekin funtzionatzen dure, eta erreakzio denboran bakarrik bereizten dira.
{|
|
|-
| 
|}

Zenbaki osoen faktorizazioa denbora polinomikoan 
Zenbaki osoen faktorizazioa denbora polinomikoan ez da oraindik konpondua izan konputazio klasikoan, baina konputazio kuantikorako, Peter Shor-ek egindako algoritmoarekin %25 baino errore txikiagoarekin kalkulatu daiteke, horrek konputagailu kuantikoetan interesa piztu zuen. Konputazio klasikorako algoritmo azkar bat lortuko balitz, kriptografian aurrerapen handiak ekarriko lituzke.

Arazo honen garrantzia sistema kriptografiko inportanteen barnealdean aurkitzen da. Osoen faktorizaziorako algoritmo azkar bat aurkitzeak RSA klabe publikoaren segurtasuna ezeztatuko luke. Zenbait sistema kriptografikok, hala nola klabe publikorako Rabin algoritmoak eta Blum Blum Shub ausazko zenbakien sortzaileak, segurtasuna bermatu ahal izango lukete. Sistema hauek apurtuko lituzkeen edozein metodo, faktorizazio algoritmo azkarragoak egiteko erabili daiteke, eta hau azkarragoa egiten bada, sistemak gogorragoak bihurtuko lirateke. Aitzitik, RSA arazorako eraso metodo hobeak existitu daitezke, baina ez dira ezagunak.

Antzeko arazo gogor bat aplikazio kriptografikoekin logaritmo diskretoen arazoa da.

Gaur egungo egoera 
2005eko maiatzaren 9an Alemaniako Teknologiaren eta Informazioaren Segurtasunerako Agentzia Federalak RSA faktorizazio-lehian errekor bat lortu zuen RSA-200, 663 biteko zenbakia deszifratzen.

Hilabete batzuk geroago agentzia berdinak RSA-640-aren faktorizazioa lortu zuela esan zuen, zenbaki hau txikiagoa zen, 193 digitu dezimaletakoa.

Bi zenbaki hauek deszifratu ahal izateko, superkonputagailuak hilabete batzuz jardunarazi zituzten lanean, 80 AMD Opteronen konbinazioaren ahalmenari esker lortu zen.

Zailtasun eta konplexutasuna 
Bi zenbaki lehen tamaina berdinekoen arteko biderkaduraren emaitza b biteko zenbaki handi bat bada, ez dago munduan eragiketa hori denbora polinomikoan deskonposatu dezakeen superkonputagailurik. Honek esan nahi duena da ez dagoela algoritmo ezagunik denbora tarte laburrean faktorizatu dezakeena O(bk), edozein k konstanterako. Algoritmo hauek existitzen dira, baina super-polinomikoak dira eta sub-esponentzialak. Espezifikoki, zenbaki handi hauek faktorizatzeko lor daitekeen denbora laburrena, Zenbakizko Behatze Orokorrean oinarrituta dago (Ingelesez: the General Number Field Sieve (GNFS) deritzona).

Konputagailu normal batentzako ZBO algoritmoa soluzio onena da, baina 1994ean Peter Shor-ek konputagailu kuantiko batek denbora polinomikoan ebatzi dezakeen algoritmoa garatu zuen. Honek, kriptografian izugarrizko aldaketa ekarriko luke, zeren, algoritmo honek behar duen denbora faktorizazioa ebazteko O((log n)3)-koa da eta gehienezko memoria O(log n) behar du. 2001ean, 7 qubiteko konputagailu batek Shor algoritmoa erabiliz 15 zenbakia faktorizatu zuen.

Osoen faktorizazioaren mailen konplexutasuna ez da ezaguna. Bere erabaki-problemaren formaren ("N-k M baino faktore txikiagoa du?") konplexutasuna NP eta co-NP dela jakina da, BAI eta EZ erantzunak egiaztatuak izan daitezkelako, baldin eta faktore lehenak eta hauen lehentasun agiria ematen badira. BQP-n (Algoritmo kuantiko mota bat) dagoela ezaguna da, Shor-en algoritmoari esker. Hiru konplexutasun mailen kanpoan dagoela uste da (P, NP osoa, co-NP osoa):
 Osoen faktorizazioa azkeneko bietako batean aurkitu ahal izango balitz, NP eta co-NP berdinak direla inplikatuko luke, harrigarria izango litzatekeena. Honegatik zabalki uste da osoen faktorizazioa bietatik kanpo dagoela.
 Asko saiatu dira algoritmo klasikoekin (hau da, ez kuantikoak) denbora polinomialean problema honi erantzuten, baina inork ez du lortu orain arte; honegatik uste da P-ren kanpoan dagoela.
 NP-rekin beste problema bat algoritmoa P edo NP osorik ez izatea da; grafoaren isomorfismoa deiturikoa.
"N zenbaki konplexua da?" edo, berdina dena, "N zenbaki lehena da?" aukeradun arazoa N-ren faktore lehenak aurkitzea baino problema errazagoa dirudi, interesgarriki. Konkretuki, lehen problema denbora polinomikoan ebatzi daiteke (N-ren n digituren oinarrian), artikulu baten arabera. Honez gainera, ausazko algoritmo oso azkarrak exititzen dira, akats tarte txikiarekin. Zenbaki bat lehena izatea probatzen duen algoritmoa RSA-ren parte garrantzitsua da, zenbaki lehen handiak aurkitzeko beharrezkoa baita.

Faktorizazio algoritmoak

Asmo Orokorrekoak 
Asmo orokorreko faktorizazio algoritmo baten gauzatze denbora zenbakiaren tamainari dagokio soilik. Algoritmo mota hau RSA zenbakiak faktorizatzeko erabiltzen da. Algoritmo mota honetako gehienak laukien kongruentzian oinarrituta daude. Hona hemen zenbait asmo orokorreko algoritmo ezagun:
 Dixon-en algoritmoa
 Frakzio etengabedun faktorizazioa
 Zetabe koadratikoa
 Zetabe arrazionala
 Zenbakien gorputzaren zetabearen algoritmo orokorra
 Shanks-en forma karratuetako algoritmoa

Asmo espezikikoak 
Asmo espezifikoko faktorizazio algoritmo baten gauzatze denbora honen propietate ezezagunetan datza (tamaina. forma bereziak, etab). Faktoreak algoritmoz algoritmo aldatzen dira, hona hemen zenbait algoritmo espezifiko:
 Saiakuntzazko zatiketa
 Pollard-en rho algoritmoa
 Pollard-en p-1 algoritmoa
 Williams-en p+1 algoritmoa
 Lenstra-ren kurba eliptikoaren faktorizazioa
 Fermat-en faktorizaziorako metodoa
 Euler-en faktorizaziorako metodoa
 Zenbakien gorputzaren zetabearen algoritmo berezia

Beste algoritmo nabarmenak 
 Shor-en konputagailu kuantikoetarako algoritmoa

Erreferentziak 

 Donald Knuth. The Art of Computer Programming, Volumen 2: Seminumerical Algorithms, Hirugarren argitalpena. Addison-Wesley, 1997. ISBN 0-201-89684-2. 4.5.4 sekzioa: Factoring into Primes, pp.379–417.
 Richard Crandall y Carl Pomerance, Prime Numbers: A Computational Perspective, 2001, Springer, 1. argitalpena, ISBN 0-387-94777-9, 5-7 kapituluak.
 Samuel S. Wagstaff Jr. , The Joy of Factoring. Providence, RI: American Mathematical Society, 2013. ISBN 978-1-4704-1048-3.
 Warren Jr., Henry S. Hacker's Delight, 2 ed. Addison Wesley - Pearson Education, Inc., 2013. ISBN 978-0-321-84268-8.

Kanpo estekak 

Zenbaki lehenak
Algoritmoak
Zenbaki osoak