Faktorisering af heltal

Faktoriseringen af et naturligt tal er dets nedbrydning til et produkt af primfaktorer . Eksistensen og unikheden (op til rækkefølgen af faktorerne) af en sådan nedbrydning følger af aritmetikkens grundlæggende teorem .

I modsætning til problemet med at erkende et tals primeness , er faktorisering angiveligt en beregningsmæssigt vanskelig opgave. Det er i øjeblikket ukendt, om der er en effektiv ikke -kvantefaktoriseringsalgoritme for heltal. Der er dog heller intet bevis for, at der ikke er nogen løsning på dette problem i polynomisk tid.

Antagelsen om, at faktoriseringsproblemet for store tal er beregningsmæssigt vanskeligt er kernen i almindeligt anvendte algoritmer (såsom RSA ). Mange områder inden for matematik og datalogi finder anvendelse til at løse dette problem. Blandt dem: elliptiske kurver , algebraisk talteori og kvanteberegning .

Historie

Opgaven med at finde effektive måder at faktorisere heltal på har været af interesse for matematikere siden oldtiden, især specialister inden for talteori . Der er spekulationer om, at Fermat var en af de første til at foreslå en nedbrydningsmetode , som består i at repræsentere et tal som en forskel af kvadrater , og derefter ved at beregne , forsøge at finde en ikke-trivial divisor . Denne metode giver dig mulighed for at finde to divisorer af et tal, der adskiller sig lidt i størrelse hurtigere end en simpel opregning af divisorer [1] . $n=x^{2}-y^{2}$ $\gcd(n,xy)$ $n$

Yderligere fandt Legendre ud af, at med denne tilgang er det nok at opnå en sammenligning , og brugte fortsatte fraktioner til dette. Euler og Gauss foreslog også nogle måder at finde de tal, der er forbundet med denne sammenligning [1] . $x^{2}\equiv y^{2}\mod n$

Et af de vigtigste øjeblikke i udviklingen af faktorisering af heltal var skabelsen af RSA-algoritmen , som fornyede videnskabsmænds interesse i denne retning, da den havde praktiske anvendelser inden for kryptering . Denne algoritme blev foreslået i 1977 af tre videnskabsmænd Ronald Rivest , Adi Shamir og Leonard Adleman fra Massachusetts Institute of Technology og opkaldt efter de første bogstaver i forfatternes navne ved RSA-metoden. Det er baseret på ideen om offentlig nøglekryptografi , og for at bryde systemet er det nødvendigt at dekomponere antallet i prime faktorer. På tidspunktet for udgivelsen af RSA-algoritmen kendte man metoder, der gjorde det muligt at faktorisere tal, der ikke bestod af mere end 25-30 cifre, og Fermats metode var stadig den mest kendte og brugte. RSA-metoden giver dig mulighed for at faktorisere tal[ klargør ] med 100 eller flere decimaler. Skaberne lovede til gengæld for faktoriseringen af et antal på 129 decimaler et symbolsk hundrede amerikanske dollars [2] .

Populariteten af faktoriseringsproblemet blev også påvirket af Martin Gardners 1977 Scientific American publikation "A New Encryption Algorithm That Will Take Millions of Years to Break". [3] Et så storslået navn blev opfattet som en udfordring for hele det matematiske samfund. Som et resultat af denne race er der blevet foreslået adskillige nye og ikke-standardiserede faktoriseringsideer [2] .

Eposet med nedbrydningen af et 129-cifret tal sluttede i 1994, da et hold ledet af A. Lenstra , ved hjælp af 1600 computere, udarbejdede et system af lineære ligninger på 220 dage , indeholdende mere end en halv million ukendte. Løsningen af dette system med en supercomputer tog to dage. På trods af at talfeltsigtemetoderne på det tidspunkt allerede var kendte , blev dette resultat opnået ved hjælp af den kvadratiske sigtealgoritme [2] .

Faktoriseringsalgoritmer

Som regel er input af sådanne algoritmer et tal , der skal faktoriseres, bestående af tegn (hvis repræsenteret i binær form) [4] . I dette tilfælde søger algoritmen efter den første primdivisor, hvorefter det om nødvendigt er muligt at køre algoritmen igen for yderligere faktorisering. Før du begynder at faktorisere et stort tal, bør du også sikre dig, at det ikke er primetal. For at gøre dette er det nok at bestå nummertesten for enkelhedens skyld. Dette problem kan løses deterministisk i polynomiel tid [5] . $n\in \mathbb {N}$ $N=[\log _{2}n]+1$ $n$

Afhængigt af kompleksiteten kan faktoriseringsalgoritmer opdeles i to grupper. Den første gruppe er eksponentielle algoritmer, hvis kompleksitet afhænger eksponentielt af længden af inputparametrene (det vil sige længden af selve tallet i binær repræsentation). Den anden gruppe er subeksponentielle algoritmer. $N$

Spørgsmålet om eksistensen af en faktoriseringsalgoritme med polynomisk kompleksitet på en klassisk computer er et af de vigtige åbne problemer i moderne talteori . Samtidig er faktorisering med polynomisk kompleksitet mulig på en kvantecomputer ved hjælp af Shor-algoritmen ( BQP-klasse ) [6] .

Eksponentielle algoritmer

Optælling af mulige divisorer

Sværhedsgrad eller . $O({\sqrt {n}}\log ^{2}n)$ $O({\sqrt {n}}\log n)$

En af de enkleste og mest oplagte faktoriseringsalgoritmer, som består i sekventielt at dividere det faktoriserbare tal med naturlige tal fra til . Formelt er det nok kun at dividere med primtal i dette interval, men for dette er det nødvendigt at kende deres sæt. I praksis kompileres en tabel med primtal, og små tal kontrolleres (f.eks. op til ). For meget store tal bruges algoritmen ikke på grund af den lave arbejdshastighed [7] . $n$ $2$ $\lfloor {\sqrt {n}}\rfloor$ $2^{16}$

Algoritmeeksempel [8]

Trin 1. Indledende installation. Tildel (Under udførelsen af algoritmen er variablerne underlagt følgende betingelser: og har ingen primfaktorer mindre end ) $t=0,k=0,n=N$ $t,k,n$ $n=N/p_{1}...p_{t}$ $n$ $d_{k}$

Trin 2. Hvis , slutter algoritmen. $n=1?$ $n=1$

Trin 3. Del. Tildel (Her og henholdsvis kvotienten og resten af at dividere tallet med .) $q=\lgulv n/d_{k}\rgulv ,r=n\mod d_{k}.$ $q$ $r$ $n$ $d_{k}$

Trin 4. Er resten nul? Hvis , så gå til trin 6. $r\neq 0$

Trin 5. Multiplikatoren er fundet. Zoom ind og tildel . Vend tilbage til trin 2. $t$ $en$ $p_{t}=d_{k},n=q$

Trin 6. Privat lille? Hvis , øg med 1 og vend tilbage til trin 3. $q>d_{k}$ $k$

Trin 7. n er et primtal. Forøg med , tildel og afslut algoritmen. $t$ $en$ $p_{t}=n$

Fermats faktoriseringsmetode

Sværhedsgrad eller . $På)$ $O(exp(N))$

Ideen med algoritmen er at søge efter tal og sådan, at det faktoriserbare tal n kan repræsenteres som: . Ligesom prøvedelingsmetoden bruges den normalt ikke i praksis til faktorisering af store tal, da den har eksponentiel kompleksitet. Metoden implementeres uden divisionsoperationen, men kun med additions- og subtraktionsoperationer [9] . Hvis , forudsat at og er primtal, der ikke afviger meget i størrelse, så faktoriserer Fermats metode n ret hurtigt [10] . $EN$ $B$ $n=A^{2}-B^{2}=(AB)(A+B)$ $n=pq$ $s$ $q$

Et eksempel på modifikation af algoritmen [11]

Trin 1. Indledende installation. Tildel (Under udførelsen af denne algoritme svarer værdierne x, y, r til henholdsvis værdierne i ligningen . Betingelsen skal være opfyldt .) $x=2\lgulv {\sqrt {N}}\rgulv +1,y=1,r=\lgulv {\sqrt {N}}\rgulv ^{2}-N.$ $2x+1,2y+1,x^{2}-y^{2}-N$ $N=uv=x^{2}-y^{2}(x={\dfrac {u+v}{2)),y={\dfrac {uv}{2)))$ $|r|<x,y<x$

Trin 2: Færdig? Hvis , afsluttes algoritmen. Vi har $r=0$

N={\frac {xy}{2}}\cdot {\frac {x+y-2}{2}}

Trin 3. Træd på x. Tildel og . $r=r+x$ $x=x+2$

Trin 4. Trin for y. Tildel og . $r=ry$ $y=y+2$

Trin 5. Tjek r. Hvis , så vend tilbage til trin 4, ellers vend tilbage til trin 2. $r>0$

Pollards ρ-algoritme

Kompleksitet . $O(n^{{1/4}})$

Pollards algoritme er en probabilistisk algoritme til at finde divisoren af et sammensat tal , der arbejder med kompleksitet, der kun afhænger af værdien af divisoren, men ikke af værdien af det faktoriserede tal . Dette medfører bekvemmeligheden af anvendeligheden af denne algoritme i tilfælde, hvor andre algoritmer, hvis kompleksitet afhænger af , bliver ineffektive [12] . Det er også bemærkelsesværdigt, at der er en variant af implementeringen af en sådan algoritme, hvor det er nok kun at gemme 3 heltal i hukommelsen [13] . $n$ $n$ $n$

Algoritmeeksempel [14]

Trin 1. Vi vælger et lille tal og bygger en talfølge , der definerer hvert af følgende ved hjælp af formlen: $x_{0}$ ${x_{k)),k=0,1,2,...,$ $x_{{k+1}}$ $x_{k+1}=x_{k}^{2}-1\mod n$

Trin 2. Samtidig beregner vi på hvert trin GCD af antallet og alle mulige forskelle , hvor . $jeg$ $d$ $n$ $|x_{i}-x_{j}|$ $j<i$

Trin 3. Når der findes en GCD , der er forskellig fra , slutter beregningen. Fundet er en divisor . Hvis det ikke er et primtal, så kan proceduren fortsættes ved at tage tallet i stedet for . $d=$ $(n,|x_{i}-x_{j}|)$ $en$ $d$ $n$ $n/d$ $n$ $n/d$

Lenstras algoritme

Kompleksitet . $O(n^{{1/3}}\log ^{2}n)$

På trods af den relativt gode effektivitet blandt eksponentielle algoritmer, er der i Lenstras algoritme behov for gentagne gange at beregne kvadratroden i et af algoritmens trin, hvilket er mere tidskrævende end addition eller subtraktion [15] .

Eksempel på algoritmeændring [16]

Lad være naturlige tal, der opfylder betingelserne $r,s,n$ $1\leq r<s<n;\;n^{{1/3}}<s;\;\gcd(r,s)=1$

Trin 1. Brug den generaliserede euklidiske algoritme til at finde . Find noget der . $r^{*}\in \mathbb{N} ,rr^{*}\equiv 1\mod s$ $r'$ $r'\equiv r^{*}n\mod s,0\leq r'<s$

Trin 2. For den næste værdi skal du finde tal i henhold til følgende regler: $i=0,1,2,...$ $a_{i},b_{i},c_{i}$

a_{0}=s,\;b_{0}=0,\;c_{0}=0

a_{1}=rr'\mod s,0<a_{1}\leq s,\;b_{1}=1,\;c_{1}\equiv {\frac {n-rr'}{s} }r^{*}(\mods)

kl .: $i\geq 2$

a_{i}=a_{{i-2}}-q_{i}a_{{i-1}},\;\;b_{i}=b_{{i-2}}-q_{i}b_ {{i-1}},\;\;c_{i}=c_{{i-2}}-q_{i}c_{{i-1}}(\mod s)

$q_{i}$ er kvotienten af division med , bortset fra det tilfælde, hvor den er ulige og resten af divisionen er nul. $a_{{i-2}}$ $a_{i-1}$ $jeg$

Trin 3. For det næste valg, find alle heltal , der opfylder betingelserne $a_{i},b_{i},c_{i}$ $c$

$c=c_{i}\mod s$ ,

$|c|<s,\;\;\;\;\;\;$ hvis endda, $jeg$

$2a_{i}b_{i}\leq c\leq {\frac {n}{s^{2}}}+a_{i}b_{i},\;\;$ hvis ulige. $jeg$

Trin 4. For hver c fra trin 3 løses ligningssystemet i heltal

$\venstre\{{\begin{array}{rcl}xa_{i}+yb_{i}\;\;\;\;\;\;&=&c\\(xs+r)(ys+r') &=&n\\\end{array}}\right.$

Hvis og viser sig at være ikke-negative heltal, så tilføj $x$ $y$ $xs+r$

Trin 5. Hvis , så afsluttes algoritmen. Ellers vender vi tilbage til trin 2 til næste værdi . $a_{i}=0$ $jeg$

Pollard-Strassen algoritme

Kompleksitet . $O(n^{{1/4}}\log ^{4}n)$

Denne algoritme har et kompleksitetsestimat svarende til Shanks kvadratiske formmetode (som er den bedste blandt deterministiske faktoriseringsalgoritmer), men kræver hukommelsesallokering. Den kan bruges direkte til faktorisering af ikke særlig store heltal, samt en hjælpealgoritme i Dixons subeksponentielle metode [17] og til at fremskynde beregningerne af anden fase af faktoriseringsmetoden ved hjælp af elliptiske kurver . [atten] $O(n^{1/4}\log n)$

Kort beskrivelse af algoritmen [15]

Sætning. Lad . Så for ethvert naturligt tal kan den mindste prim-divisor af tallet findes i aritmetiske operationer. $z\in \mathbb{N} ,y=z^{2}$ $t$ $\gcd(n,y!)$ $O(z\log ^{2}z\log ^{2}t)$

Algoritme. Lad . Dernæst finder vi ved hjælp af sætningens algoritme den mindste primtalsdivisor af tallet . Da det er deleligt med tallets mindste primtal , vil algoritmen producere præcis dette tal . $z=[n^{{1/4}}]+1,y=z^{2}>n^{{1/2}},t=n$ $\gcd(n,y!)$ $y!$ $s$ $n(p\leq n^{{1/2}}<y)$ $s$

Shanks' metode til kvadratiske former

Garanteret kompleksitet og hvis Riemann-hypotesen er sand . $O(n^{1/4+\varepsilon })$ $O(n^{1/5+\varepsilon })$

I modsætning til Pollard-Strassen-algoritmen kræver den ikke tildeling af store mængder hukommelse, desuden har den ret simple beregningsformler [19] .

Pollards P-1 algoritme

Kompleksitet [20] . $O(n^{{1/2}}\log ^{c}n)$

På trods af det eksponentielle kompleksitetsestimat finder algoritmen hurtigt små primdivisorer i alle tilfælde , fordi de er effektglatte for en lille grænse for glathed . I praktiske problemer bruges denne algoritme sædvanligvis før anvendelse af subeksponentielle faktoriseringsalgoritmer til at adskille små primdivisorer af et tal [20] . $n$ $B$ $n$

Estimering af kompleksitet efter stadier [21]

Sværhedsgrad af den første fase. , hvor går grænsen [22] $O(B_{1}\log B_{1}\log ^{2}N)$ $B_1$

Kompleksiteten af anden fase. , hvor går den nye grænse. [23] $O(\log ^{2}B_{2})+O(\log q_{{\pi (B_{1}))))+2(\pi (B_{2})-\pi (B_{1 }))$ $B_{2}$ $B_{2}>>B_{1}$

Lehmanns metode

Kompleksitet . $O(n^{{1/3}})$

På nuværende tidspunkt er algoritmen af mere historisk end praktisk interesse, da denne algoritme var den første deterministiske algoritme med eksekveringskompleksitet hurtigere end . $O(\sqrt{n})$

Et eksempel på modifikation af algoritmen [24]

Trin 1. For alt fra at gøre: $s$ $2$ $\lceil {\sqrt[{3}]{m}}\rceil$

Hvis , så returner tallet m som en divisor og fuldfør algoritmen. $m\equiv 0\mod s$ $s$

Trin 2. For alt fra at gøre: $b$ $en$ $\lceil {\sqrt[{3}]{m}}\rceil$

Trin 2.1 Bestem og

k = 0

D=\venstre\lgulv {\frac {\sqrt[{6}]{m)){4{\sqrt {b))))\right\rgulv +1

Trin 2.2 Bestem og

x=\lgulv {\sqrt {4bm}}\rgulv +k

v=x^{2}-4bm

Trin 2.3 Hvis er et perfekt kvadrat, så definer og afslut algoritmen.

v

p=\gcd(m,x\pm v)

Trin 2.4 Definer .

k=k+1

Trin 2.5 Hvis , så beregn den nye værdi af , ellers gå tilbage til trin 2.2

k\geq D

d

Trin 3. Kør algoritmen med besked om, at det tal, der faktoriseres , er primtal. $m$

Subeksponentielle algoritmer

L-notationen [4] er vedtaget for at betegne kompleksiteten :

L_{n}(\alpha ,\;c):=O(\exp((c+o(1))(\log n)^{\alpha }(\log \log n)^{1 -\alpha })))

hvor er tallet, der skal faktoriseres, og er nogle konstanter. $n$ $0<\alfa<1$ $c$

Dixons algoritme

Kompleksitet . $L_{n}(1/2,\;2{\sqrt {2)))$

Algoritmeeksempel [25]

Trin 1. Vælg en tilfældig , og beregn . $b,1<b<n$ $b^{2}\mod m$

Trin 2. Forsøgsdelinger forsøger at dekomponere til primfaktorer fra faktorbasen. $b^{2}\mod m$

Trin 3. Hvis er et -tal, dvs.

b

B

b^{2}\mod n=\prod \limits _{{p\in B}}p^{{\alpha _{p}(b)))

, så husk og . Gentag talgenereringsproceduren, indtil -numre er fundet .

{\vec {\alpha }}(b)

{\vec {\varepsilon }}(b)

b

m=h+1

B

b_{1},...,b_{m}

Trin 4. Find (for eksempel ved at løse et homogent system af lineære ligninger med hensyn til ukendte ved hjælp af Gauss sekventielle eliminering af ukendte ) den lineære afhængighedsrelation $x_{1}{\vec {\varepsilon }}(b_{1})\oplus ...\oplus x_{m}{\vec {\varepsilon }}(b_{m})={\vec {0} }$ $(x_{1},...,x_{m})$

{\vec {\varepsilon }}(b_{{i_{1}}})\oplus ...\oplus {\vec {\varepsilon }}(b_{{i_{t}}})={\vec { 0}},\;\;\;\;\;\;1<t\leq m.

Sætte

x=b_{{i_{1}}}...b_{{i_{t}}},\;\;\;\;\;\;y=\prod \limits _{{p\in B} }p^{{{\frac {1}{2}}({\vec {\alpha _{p}}}(b_{{i_{1}}})+...+{\vec {\alpha _{p}}}(b_{{i_{t}}})))}}

Trin 5. Tjek . Hvis det er tilfældet, så gentag genereringsproceduren. Hvis ikke, så findes en ikke-triviel nedbrydning $x\equiv \pm y(\mod n)$

n=u\cdot v,\;\;\;\;\;\;u=(x+y,n),\;\;\;\;\;\;v=(xy,n)

. Faktorisering ved fortsatte brøker

Kompleksitet [26] . $L_{n}(1/2,\;{\sqrt {2)))$

Kvadratisk sigtemetode

Kompleksitet [26] . $L_{n}(1/2,\;1)$

Denne metode ved hjælp af flere polynomier er effektiv og ret nem at implementere på en computer. Der er grund til at tro, at det er den bedst kendte faktoriseringsalgoritme for (bortset fra den elliptiske kurvefaktoriseringsmetode , som i nogle tilfælde kan være hurtigere. For tal vil talfeltssigte-algoritmerne arbejde hurtigere end den kvadratiske sigtemetode [27] . $n<10^{{110}}$ $n>10^{{110}}$

Lenstra-faktorisering ved hjælp af elliptiske kurver

Kompleksitet , hvor er det mindste primtal, der deler sig [28] . $L_p(1/2,\;\sqrt{2})$ $s$ $n$

Parametrene er valgt tilfældigt. Værdier bør vælges empirisk under hensyntagen til nogle serier af stigende værdier [28] . I praksis er givet algoritmen at udføre algoritmen med en enkelt kurve. Dette gentages, indtil det faktoriseres, eller indtil den tid, der er tildelt til algoritmen, løber ud. $a,x,y$ $w,v$ $n,v,w$ $n$

Der er modifikationer af algoritmen, der giver dig mulighed for at arbejde med flere kurver samtidigt [28] .

Beskrivelse af algoritmen [28]

Algoritmens input er det tal , der skal faktoriseres, parametrene afhængig af , derudover indstilles således, at og for betingelsen er opfyldt . Algoritmen finder den naturlige divisor af tallet . $n$ $v,w\in \mathbb{N}$ $n$ $a,x,y\in \mathbb{Z } /n\mathbb{Z }$ $P=(x:y:1)\in {\mathbb {V}}_{n}$ $b\equiv y^{2}-x^{3}-ax\mod n$ $6(4a^{3}+27b^{2})\in (\mathbb{Z} /n\mathbb{Z} )^{*}$ $d$ $n,1<d<n$

For alle , stoler $r\in \mathbb{N} ,2\leq r\leq w$

e(r)=max\{m|m\in Z_{{\geq 0)),r^{m}\leq v+2{\sqrt {v))+1\}

Såvel som

k=\prod \limits _{{2\leq r\leq w}}r^{{e(r)}}

, er enkle.

r

Lad . Ligger derefter på en elliptisk kurve over defineret af ligningen . Det er nødvendigt at beregne punktet i henhold til regnereglerne over elliptiske kurver. Hvis der under beregningen findes en divisor af tallet , så dekomponeres den i faktorer. Hvis den er fundet, men divisoren ikke findes, afsluttes algoritmen og sender en besked om et mislykket faktoriseringsforsøg. $P=(x:y:1\in {\mathbb {V}}_{n})$ $P$ $E_{{a,b}}$ $\mathbb{Z } /n\mathbb{Z }$ $Y^{2}=X^{3}+aX+b$ $kP$ $d$ $n$ $n$ $kP$ $d$

Nummerfeltsigte

I øjeblikket er de mest effektive faktoriseringsalgoritmer variationer af talfeltsigten [29] :

En speciel sigtemetode til et talfelt med kompleksitet [30] (metoden er kun anvendelig til faktorisering af tal af en speciel type); $L_{n}(1/3,\;(32/9)^{{{\frac {1}{3)))))$
Den generelle sigtemetode for et talfelt med kompleksitet [30] (metoden gælder for alle tal). $L_{n}(1/3,\;(64/9)^{{{\frac {1}{3)))))$

Programmer i kryptografi

Den formodede store beregningsmæssige kompleksitet af faktoriseringsproblemet ligger til grund for den kryptografiske styrke af nogle offentlige nøglekrypteringsalgoritmer , såsom RSA . Desuden, hvis mindst én af RSA-nøgleparametrene er kendt, så er systemet utvetydigt hacket, derudover er der mange algoritmer til at gendanne alle nøgler i systemet med nogle data [31] .

Nuværende tilstand

I marts 1994, ved at bruge en dobbelt variation af det multiple polynomium QS , faktorerede et hold matematikere ledet af Lenstra et 129-bit (428-bit) tal. Beregningerne er foretaget af frivillige på internettet - 600 mennesker og 1.600 computere arbejdede i otte måneder. Computerne blev forbundet via e-mail og sendte deres resultater til et centralt depot, hvor den endelige analyse blev udført. Disse beregninger brugte QS og teorien fra fem år siden, NFS kunne fremskynde beregningerne. En gruppe videnskabsmænd konkluderede, at udbredte 512-bit RSA-moduler kunne knækkes af en organisation, der er villig til at bruge flere millioner dollars og vente flere måneder [32] .

For at fremme faktoriseringens kunst har RSA Data Security, Inc. i marts 1991 annoncerede RSA Factoring Challenge-programmet (RSA factoring konkurrence). Konkurrencen består i at faktorisere en række svære tal, som hver er produktet af to primtal af omtrent samme størrelse. Hvert primtal blev valgt til at være kongruent med 2 modulo 3. I alt 42 tal blev foreslået, et hver i intervallet fra 100 til 500 cifre i 10-cifrede intervaller (plus et yderligere, 129-bit tal. Læs mere: RSA Factoring Udfordring [ 32] .

Noter

↑ 1 2 Yashchenko, 1999 , s. 107.
↑ 1 2 3 Ishmukhametov, 2011 , s. 7-8.
↑ Gardner M. En ny slags chiffer, der ville tage millioner af år at bryde // Sci . amer. - NYC : NPG , 1977. - Vol. 237, Iss. 2. - S. 120-124. — ISSN 0036-8733 ; 1946-7087 - doi:10.1038/SCIENTIFICAMERICAN0877-120
↑ 1 2 Vasilenko, 2003 , s. 9.
↑ Vasilenko, 2003 , s. 48.
↑ Ishmukhametov, 2011 , s. 52.
↑ Nesterenko, 2012 , s. 142-143.
↑ Knuth, 2007 , s. 424.
↑ Ishmukhametov, 2011 , s. 52-54.
↑ Vasilenko, 2003 , s. 57.
↑ Knuth, 2007 , s. 431.
↑ Ishmukhametov, 2011 , s. 64.
↑ Ishmukhametov, 2011 , s. 63.
↑ Ishmukhametov, 2011 , s. 62.
↑ 1 2 Vasilenko, 2003 , s. 73.
↑ Vasilenko, 2003 , s. 69.
↑ Vasilenko, 2003 , s. 73-74.
↑ 20 år med ECM .
↑ JASON E. GOWER OG SAMUEL S. WAGSTAFF, JR. KVADRATFORM FAKTORISERING // BEREGNINGSMATEMATIK. Arkiveret fra originalen den 24. august 2017.
↑ 1 2 Vasilenko, 2003 , s. 62.
↑ Ishmukhametov, 2011 , s. 57.
↑ Ishmukhametov, 2011 , s. 55.
↑ Ishmukhametov, 2011 , s. 56.
↑ Nesterenko, 2012 , s. 151.
↑ Cheremushkin, 2002 , s. 78.
↑ 1 2 Vasilenko, 2003 , s. 87.
↑ Vasilenko, 2003 , s. 92.
↑ 1 2 3 4 Vasilenko, 2003 , s. 113.
↑ Schneier, 2002 , 11.4.
↑ 1 2 Vasilenko, 2003 , s. 93.
↑ Cheremushkin, 2002 , s. 87.
↑ 1 2 Schneier, 2002 , par.11.4.

Litteratur

på russisk

Koblitz N. Kursus i talteori og kryptografi - 2. udgave - M .: Videnskabeligt forlag TVP , 2001. - 254 s. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5
Cheremushkin A. V. Forelæsninger om aritmetiske algoritmer i kryptografi - M .: MTsNMO , 2002. - 104 s. — ISBN 978-5-94057-060-8
Vasilenko O. N. Talteoretiske algoritmer i kryptografi - M. : MTsNMO , 2003. - 328 s. — ISBN 978-5-94057-103-2
Ishmukhametov Sh. T. Faktoriseringsmetoder for naturlige tal : lærebog - Kazan : Kazan University , 2011. - 190 s.
Nesterenko A. Yu. Talteoretiske metoder i kryptografi - Moskva : Moscow State Institute of Electronics and Mathematics , 2012. - 224 s. — ISBN 978-5-94506-320-4
Knuth, D. Kunsten at programmere computer. - Moskva: Williams, 2007. - T. 2. - 832 s. - ISBN 978-5-8459-0081-4 .
Introduktion til kryptografi / Yashchenko, V.V. - Moskva: MTsNMO , 1999. - 272 s. - ISBN 5-900916-40-5 .
Schneier, B. Anvendt Kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protocols, Algoritms and Source Code in C. - Moscow: Triumph, 2002. - 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .

på engelsk

Bressoud, DM Faktorisering og Primalitetstest. - N. Y. : Springer-Verlag, 1989. - 260 s. - ISBN 0-387-97040-1 .
Mahoney, MS Pierre de Fermats matematiske karriere . - 2. - Princeton: Princeton Univercity Press, 1994. - S. 324 -332. — 438 s. - ISBN 0-691-03666-7 .

Tal efter delelighedskarakteristika
Generel information	Faktorisering af heltal Delbarhed enhedsdeler Divisor funktion primtal Grundlæggende sætning for aritmetik Aritmetisk tal
Faktoriseringsformer	primtal Komposit nummer Semiprime rektangulært tal Sphenisk tal Kvadratløst tal Fuld multiple Perfekt grad Achilles nummer glat nummer Almindelig nummer groft tal usædvanligt antal
Med begrænsede divisorer	perfekt tal Lidt utilstrækkelige tal Lidt overflødige tal Multiperfekt tal Hemiperfekte tal hyperperfekt tal super perfekt nummer enhedsprimtal semiperfekt tal pararytmisk tal Erdős-Nicolas nummer
Tal med mange divisorer	Overskydende tal Primitive overskydende tal Meget overflødige tal Super redundante numre Enormt overflødige tal supersammensat tal Et meget supersammensat tal mærkeligt nummer
Relateret til aliquot -sekvenser	helligt tal venlige tal offentlige numre Kvasivenlige tal
Andet	Ikke nok tal ven tal sublimerede tal Malmtal ydmygt nummer Lige cifre ekstravagant nummer