Faktorado de entjero

En nombroteorio, faktorado de entjero estas tiaj proceduro kaj la rezulto de malkomponado de pozitiva komponita nombro en netrivialajn pozitivajn divizorojn, ke la produto de tiuj divizoroj estas egala al la origina entjero. Netriviala estas divizoro, kiu egalas nek al 1, nek al la origina entjero.

Prima malkompondo

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

Per donita algoritmo por entjera faktorado, oni povas faktori ĉiun entjeron al ĝiaj 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 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:

$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.

Praktikaj aplikoj

La malfacileco de ĉi tiu problemo estas krita supozo de kelkaj gravaj ĉifrikaj sistemoj. Ekzisto de rapida entjera faktorada 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 faktorada algoritmo; sed se entjera faktorado estas malfacila, tiam ili estas fortaj. En kontrasto, povas okazi ke ekzistas atako al RSA pli kompetenta ol entjera faktorado, kvankam neniu estas nun publikigita.

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

Entjera faktorsdo havas ankaŭ multajn pozitivajn aplikojn en algoritmoj. Ekzemple, se entjero n estas skribita en ĝia prima faktora 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 rekordon por faktorado 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 faktoradon de RSA-200, 663-bita nombro (200 dekumaj ciferoj). La sukcesa faktorado prenis dek ok monatojn kaj uzis pli ol duon-jarcenton da komputila tempo per la ĝenerala nombra kampa kribrilo.

La sama teamo poste anoncis faktoradon de RSA-640, pli malgranda 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

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

Vidu ankaŭ

• Algoritmoj de multiplikado

Eksteraj ligiloj

• [1] Richard P. Brent, "Lastatempa progreso en entjeraj faktoradaj 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 faktorada programo por Vindozo. Ĝi pretendas prilabori 80-ciferajn nombrojn. Vidu ankaŭ la retpaĝaron por ĉi tiu programo MIRACL
• [3] - entjera faktorada Java apleto, kiu uzas la elipso-kurban metodon kaj meminiciatigatan 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 faktorado. Ĝi enhavas kelkajn faktoradajn 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: Faktorado 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.