Faktorigo de entjero

En nombroteorio, faktorigo de entjero aŭ entjera faktorigo estas la procezo kaj la rezulto de malkomponigo de komponigita nombro en pli malgrandajn nebagatelajn divizoroj, tiel ke multiplikitaj ĉiuj kune la divizoroj estas egalaj la originala entjero. Nebagatela divizoro estas tiu ne egala al 1 kaj ne egala al la fonta entjero.

Prima malkomponaĵo

Per la fundamenta teoremo de aritmetiko, ĉiu pozitiva entjero pli granda ol unu havas unika priman faktorigo. Tamen, la fundamenta teoremo de aritmetiko donas ne diras kiel ricevi entjeran priman faktorigon; ĝi nur garantias ĝian ekziston.

Per donita algoritmo por entjera faktorigo, oni povas faktorigi ĉiun entjeron suben al ĝiaj komponantaj primaj faktoroj per ripeta apliko de ĉi tiu algoritmo al rezultoj de la antaŭa rulo.

Malfacileco

Se la nombroj estas tre grandaj, ne estas konata bona faktoriga algoritmo. La supozebla malfacileco de ĉi tiu problemo estas je la koro de certaj ĉifrikaj algoritmoj, ekzemple RSA. Multaj branĉoj de matematiko kaj komputiko estas ligitaj al tiu ĉi problemo, ekzemple elipsaj kurboj, algebra nombroteorio kaj kvantuma komputado.

Ne ĉiujn entjerojn estas egale malfacile faktorigi. Plej malfacile estas (per ĝis nun konataj metodoj) malkomponigi duonprimojn, kiuj estas la produtoj de nur du diversaj primoj. La plej malfacila kazo estas kiam ambaŭ primoj estas proksimume same grandaj kaj hazarde elektitaj, sed ne tre proksimaj unu al la alia.

Se granda, b-bita entjero estas produto de du primoj, kiuj estas de proksimume sama amplekso, ne ekzistas publikigita algoritmo, per kiu eblas faktorigi ĝin en polinoma tempo, kio estas, kiu povas faktori en tempo O(b^k) por iu konstanto k. Estas publikigitaj algoritmoj kiuj estas pli rapidaj ol O((1+ε)^b) por ĉiu pozitiva ε, kio estas, sub-eksponenta funkcio.

La plej bona publikigita asimptota rula tempo estas por la ĝenerala nombra kampa kribrilo, kiu por b-bita nombro n, estas:

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

Por ordinara komputilo, ĝenerala nombra kampa kribrilo estas la plej bona publikigita algoritmo por grandaj n (pli ol proksimume 100 ciferoj).

Por kvantuma komputilo, tamen, estas esploritaj algoritmoj kiuj solvas la taskon en polinoma tempo. Ĉi tio, se estos realigita praktike per granda kvantuma komputilo, havos gravajn implikaciojn por ĉifriko. Ĉi tia algoritmo de Shor bazonas nur tempon O(b³) kaj spacon O(b) por b-bita nombro. En 2001, la unua 7-kvantumbita kvantuma komputilo ruligis la algoritmon de Shor. Ĝi faktorigis nombron 15.

Je flanko de komplikeco de entjera faktoriga problemo, necesas distingi du malmulte malsamajn versiojn de la problemo:

• La funkcia problema versio: por donita entjero N, trovi entjeron d, 1<d<N tiu ke d dividas na N, aŭ konkludi ke N estas primo. Ĉi tiu problemo estas bagatele en komplikeco FNP kaj ne estas sciate ĉu ĝi kuŝas en komplikeco FP. Ĉi tiu estas la versio solvata per plejparto de la praktikaj realigoj.

• La decida problema versio: por donita entjero N kaj entjero M, 1<M<N, decidi ĉu N havas faktoron d, 1<d<M. Ĉi tiu versio estas utila ĉar plej bone studitaj komplikecaj klasoj estas difinitaj kiel klasoj de decidaj problemoj, ne funkciaj problemoj. Ĉi tio estas natura decida versio de la problemo, analoga al tiuj ofte uzitaj por optimumigaj problemoj, ĉar ĝi povas esti kombinita kun duoniga serĉo por solvi la funkcian version de la problemo en logaritma kvanto de demandoj.

Estas ne sciata akurate al kiu komplikeca klaso apartenas la decida versio de la entjera faktoriga problemo. Ĝi estas sciata al aparteni al ambaŭ NP kaj co-NP. Ĉi tio estas ĉar ambaŭ jesa kaj nea respondoj povas esti kontrolitaj. La kontrolado estas bagatele se estas donitaj la primaj faktoroj, oni povas kontroli primecon de la faktoroj per la AKS primeca provo, kaj kontroli ke ilia produto estas la fonta nombro; ambaŭ kontroloj estas fareblaj en polinoma tempo.

Ĝi estas sciata al aparteni al BQP pro algoritmo de Shor. Ĝi estas suspektita al esti ekster ĉiuj tri el la klasoj P, '''NP'''-plena kaj '''co-NP'''-plena. Se eblas pruvi ke ĝi estas NP-plena aŭ co-NP-plena, do sekvos ke NP = co-NP. Ĉi tiu devus esti tre surprizanta rezulto, kaj pro tio entjera faktorigo estas larĝe suspektita al esti ekster ambaŭ el ĉi tiuj klasoj. Multaj penis trovi polinomo-tempajn algoritmojn por ĝi kaj malsukcesis, pro tia ĝi estas larĝe suspektita al esti ekster P.

En kontrasto, la primeca provo, kiu estas la decida problemo "ĉu N estas komponigita nombro?", aŭ ekvivalente: "ĉu N estas primo?", aspektas kiel multe pli simpla ol la problemo de reala trovo de faktoroj de N. Aparte, la premieca provo povas esti solvita en polinoma tempo de kvanto de ciferoj de la nombro per la AKS primeca provo. Aldone, estas kelkaj probablecaj algoritmoj kiuj povas kontroli primecon tre rapide se oni konsentas akcepti malgrandan eblecon de eraro. En praktiko, primeca provo estas krita parto de la RSA algoritmo, ĉar necesas trovi grandajn primojn por la algoritmo.

Praktikaj aplikoj

La malfacileco de ĉi tiu problemo estas krita supozo de kelkaj gravaj ĉifrikaj sistemoj. Ekzisto de rapida entjera faktoriga algoritmo rezultus je tio ke la publiko-ŝlosila algoritmo RSA estas malsekura. Iuj ĉifrikaj sistemoj, ekzemple la ĉifrosistemo de Rabin kaj la pseŭdo-stokasta generilo de Blum Blum Shub povas pli forte garantii, ĉi tio signifas ke rompo de ili povas esti farita per rapida entjera faktoriga algoritmo; sed se entjera faktorigo estas malfacila, tiam ili estas fortaj. En kontrasto, povas okazi ke ekzistas atako al RSA pli kompetenta ol entjera faktorigo, kvankam neniu estas nun publikigita.

Simila malfacila problemo uzata por ĉifrikaj aplikoj estas la diskreta logaritma problemo.

Entjera faktorigo havas ankaŭ multajn pozitivajn aplikojn en algoritmoj. Ekzemple, se entjero n estas skribita en ĝia prima faktoriga prezento, aperas ebleco rapide kalkuli multiplikajn funkciojn sur n.

Aktuala stato de la arto

Teamo en la Germana Federacia Agentejo por Informa Teknologia Sekureco (Federacia Oficejo por Informa Sekureca) tenas la rikordon por faktorigo de duonprimoj en la serio proponita de la RSA faktoriga defio sponsorita de RSA sekureco. En la 9-a de majo, 2005, ĉi tiu teamo anoncis faktorigon de RSA-200, 663-bita nombro (200 dekumaj ciferoj). La sukcesa peno pri faktorigo prenis dek ok monatojn kaj uzis pli ol duono jarcentojn de komputila tempo per la ĝenerala nombra kampa kribrilo.

La sama teamo poste anoncis faktorigon de RSA-640, pli malgranda nombro 640-bita nombro (193 dekumaj ciferoj) en la 4-a de novembro, 2005.

Algoritmoj

Ĝenerala celo

Algoritmoj de ĝenerala celo havas rulan tempon dependan nur de amplekso de la fontaentjero. Plejparto de ĝeneralo-celaj algoritmoj estas bazitaj sur la maniero de kongrueco de kvadratoj.

• Algoritmo de Dixon
• Ĉenfrakcia faktorigo
• Kvadrata kribrilo
• Ĝenerala nombra kampa kribrilo
• Kvadrata forma faktorigo de Shanks

Specialaj celoj

Algoritmoj de specialaj celoj havas rulan tempon dependan de propraĵoj de la nekonataj faktoroj: amplekso, speciala formo kaj tiel plu. Akurate de kio dependas la rula tempo varias inter la algoritmoj.

• Prova divido
• ρ algoritmo de Pollard
• Algebro-grupa faktoriga algoritmo
  • ρ-1 algoritmo de Pollard
  • ρ plus 1 algoritmo de Williams
  • Elipsa kurba faktorigo de Lenstra
• Faktoriga maniero de Fermat
• Eŭlera faktoriga maniero
• Speciala nombra kampa kribrilo

Aliaj algoritmoj

• Algoritmo de Shor por kvantuma komputilo

Primeca provo

Ĉi tiuj algoritmoj estas por primeca provo, kiu ne estas fakte faktoigo.

• AKS primeca provo
• Probablecaj:
  • Primeca provo de Fermat
  • Primeca provo de Solovay-Strassen
  • Primeca provo de Miller-Rabin

Vidu ankaŭ

• Algoritmoj de multiplikado

Eksteraj ligiloj

• [1] Richard P. Brent, "Lastatempa progreso en entjeraj faktorigaj algoritmoj", Komputado kaj kombinatoriko", 2000, pp.3-22.
• PDF versio de aŭgusto de 2005 Manindra Agrawal, Neeraj Kayal, Nitin Saxena" Primoj estas en P." Analoj de matematiko 160(2): 781-793 (2004).
• [2] - publika entjera faktoriga programo por Vindozo. Ĝi pretendas prilabori 80-ciferajn nombrojn. Vidu ankaŭ la retpaĝaron por ĉi tiu programo MIRACL
• [3] - entjera faktoriga Java apleto kiu uzas la elipsan kurban manieron kaj la mem iniciatigatan kvadratan kribrilon.
• La RSA defiaj nombroj Arkivigite je 2006-12-09 per la retarkivo Wayback Machine
• [4] MathWorld pri RSA-640
• Qsieve, suito de programoj por entjera faktorigo. Ĝi enhavas kelkajn faktorigajn manierojn
• ρ-1 algoritmo de Pollard, enkonduko de la algoritmoj kaj C fonta kodo
• Klasika maniero, enkonduko de la algoritmoj kaj C fonta kodo

Referencoj

• Donald Knuth. La Arto de Komputila Programado, Volumeno 2: Duonnombraj algoritmoj, Tria Redakcio. Addison-Wesley, 1997. ISBN 0-201-89684-2. Sekcio 4.5.4: Faktorigo en primojn, pp. 379–417.
• Richard Crandall kaj Carl Pomerance. (2001) Prime Numbers: A Computational Perspective - Primoj: komputa perspektivo, 1‑a eldono, Springer. ISBN 0-387-94777-9.