Malfacileco

Se la nombroj estas tre grandaj, ne estas konata rapida faktorada 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 faktori. Plej malfacile estas (per ĝis nun konataj metodoj) malkomponi 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 faktori ĝ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:

${\displaystyle 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 faktoris nombron 15.

Je flanko de komplikeco de entjera faktorada 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 problemo pri entjera faktorado. Ĝ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 primeco-testo AKS, 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 faktorado 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 primeco-testo, kiu estas la decida problemo "ĉu N estas komponita nombro?", aŭ ekvivalente: "ĉu N estas primo?", aspektas kiel multe pli simpla ol la problemo de reala trovo de faktoroj de N. Aparte, la primeco-testo povas esti plenumita en polinoma tempo de kvanto de ciferoj de la nombro per la primeco-testo AKS. Aldone, estas kelkaj probablecaj algoritmoj kiuj povas kontroli primecon tre rapide se oni konsentas akcepti malgrandan eblecon de eraro. En praktiko, primeco-testo estas krita parto de la RSA algoritmo, ĉar necesas trovi grandajn primojn por la algoritmo.

Ĝ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

Primeco-testo

Ĉi tiuj algoritmoj estas por primeco-testo, kiu ne estas fakte faktoigo.

• Primeco-testo AKS
• Probablecaj:
  • Primeco-testo de Fermat
  • Primeco-testo de Solovay-Strassen
  • Primeco-testo de Miller-Rabin