Fermats faktoriseringsmetode

Fermats faktoriseringsmetode er en algoritme til faktorisering (faktorering) af et ulige heltal , foreslået af Pierre Fermat ( 1601-1665 ) i 1643 . $n$

Metoden er baseret på at søge efter sådanne heltal og som opfylder relationen , hvilket fører til en nedbrydning af . $x$ $y$ $x^{2}-y^{2}=n$ $n=(xy)\cdot (x+y)$

Historie

I begyndelsen af det 17. århundrede i Frankrig begyndte matematiske ideer aktivt at spredes blandt videnskabsmænd gennem korrespondance. I 1638 sluttede Pierre Fermat sig til kredsen af korrespondentforskere . Korrespondance var en bekvem måde at kommunikere på, da Fermat boede i Toulouse , og mange af hans bekendte videnskabsmænd boede i Paris . En af disse videnskabsmænd var Maren Mersenne , som var engageret i uddeling af breve, videresendelse og kommunikation af mange videnskabsmænd indbyrdes. Den 26. december 1638 nævnte Fermat i et brev til Mersenne , at han havde fundet en metode, hvorved man kunne finde divisorer af positive tal, men han udelod alle detaljer og en beskrivelse af metoden. På det tidspunkt korresponderede Mersenne også med den franske matematiker Bernard Frenicle de Bessy , der ligesom Fermat var engageret i talteori , især divisorer af naturlige tal og perfekte tal . I begyndelsen af 1640 , efter at have erfaret, at Fermat havde modtaget en metode til at finde divisorer, skrev Frenicle til Mersenne, som videresendte Fermats brev. Mersenne var i lang tid bindeleddet mellem de to matematikere i deres korrespondance. Det var i brevene til Frenicle, at Fermat var i stand til at bevise rigtigheden af faktoriseringsmetoden, samt for første gang at formulere og begrunde hovedbestemmelserne i sætningen, som senere blev kaldt Fermats lille sætning [1] [2 ] .

Begrundelse

Fermats metode er baseret på sætningen om repræsentationen af et tal som forskellen mellem to kvadrater :

Hvis ulige, så er der en en-til-en overensstemmelse mellem faktoriseringen og repræsentationen som en forskel af kvadrater med , givet af formlerne $n>1$ $n=a\cdot b$ $n=x^{2}-y^{2}$ $x>y>0$ $x=(a+b)/2,$ $y=(ab)/2,$ $a=x+y$ $b=xy.$

Bevis

Hvis faktoriseringen er givet , så gælder forholdet: . Således opnås en repræsentation i form af en forskel på to kvadrater. $n=a\cdot b$ $n=a\cdot b=\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {ab}{2}}\right)^ {2}$

Omvendt, hvis givet det , så kan højre side faktoriseres: [3] . $n=x^{2}-y^{2}$ $(xy)(x+y)$

Beskrivelse af algoritmen

For at faktorisere et ulige tal søges der efter et talpar, således at , eller . I dette tilfælde er tallene og divisorer , muligvis trivielle (det vil sige, en af dem er lig med 1, og den anden er lig ). $n$ $(x, y)$ $x^2 - y^2 = n$ $(xy)\cdot (x+y)=n$ $(x+y)$ $(xy)$ $n$ $n$

I det ikke-trivielle tilfælde svarer lighed til , altså til hvad der er en firkant . $x^2 - y^2 = n$ $x^{2}-n=y^{2}$ $x^{2}-n$

Søgningen efter et kvadrat af denne art begynder med - det mindste tal, for hvilket forskellen er ikke-negativ. $x=\left\lceil {\sqrt {n))\right\rceil$ $x^{2}-n$

For hver værdi, der starter fra , skal du beregne og kontrollere, om dette tal ikke er et nøjagtigt kvadrat. Hvis ikke, så øg med én og gå til næste iteration. $k\in {\mathbb {N}),$ $k=1$ $\left(\left\lceil {\sqrt {n))\right\rceil +k\right)^{2}-n$ $k$

Hvis er et nøjagtigt kvadrat, det vil sige, så opnås udvidelsen: $\left(\left\lceil {\sqrt {n))\right\rceil +k\right)^{2}-n$ $x^{2}-n=\left(\left\lceil {\sqrt {n))\right\rceil +k\right)^{2}-n=y^{2},$

n=x^{2}-y^{2}=(x+y)(xy)=a\cdot b,

hvori $x=\left\lceil {\sqrt {n))\right\rceil +k.$

Hvis det er trivielt og unikt, så er det enkelt. $n$

I praksis beregnes værdien af udtrykket på -th trin under hensyntagen til værdien på -th step: $(k+1)$ $k$

(s+1)^{2}-n=s^{2}+2s+1-n,

hvor $s=\left\lceil {\sqrt {n))\right\rceil +k.$

Eksempler

Eksempel på lav iteration

Lad os tage et nummer . Beregn For vil vi beregne værdierne af funktionen . For yderligere enkelhed vil vi konstruere en tabel, der vil indeholde værdierne og ved hvert iterationstrin. Vi får: $n=10873$ $s=\venstre\lceil {\sqrt {n}}\right\rceil =105.$ $k=0,1,2,...$ $s+k$ $y=(s+k)^{2}-n$ ${\sqrt {y}}$

$k$	$y$	${\sqrt {y}}$
en	363	19.052
2	576	24

Som det kan ses af tabellen, blev der allerede ved det andet iterationstrin opnået en heltalsværdi . ${\sqrt {y}}$

Således finder følgende udtryk sted: . Derfor følger det $(105+2)^{2}-n=24^{2}$ $n=107^{2}-24^{2}=131\cdot 83=10873.$

Et eksempel med et stort antal iterationer

Lad Så eller $n=89755.$ ${\sqrt {n}}\ca. 299.591$ $s=\venstre\lceil {\sqrt {n}}\right\rceil =300.$

$k$	$y$	${\sqrt {y}}$
77	52374	228.854
78	53129	230,497
79	53886	232.134
80	54645	233.763
81	55406	235.385
82	56169	237

{\sqrt {y}}=237

a=s+k+{\sqrt {y}}=300+82+237=619

b=s+k-{\sqrt {y}}=300+82-237=145

Denne udvidelse er ikke endelig, da tallet naturligvis ikke er primtal: $145$ $145=29\cdot 5.$

Som et resultat, den endelige nedbrydning af det oprindelige tal til produktet af prime faktorer $n$ $89755=5\cdot 29\cdot 619.$

Præstationsevaluering

Den største effektivitet af beregningen ved Fermat-faktoriseringsmetoden opnås, når faktorerne for tallet er omtrent lig med hinanden. Dette giver en relativt kort sekvenssøgning [4] $n$

s^{2}-n,\ (s+1)^{2}-n,\ (s+2)^{2}-n,\ \dots \ (s+k)^{2} -n.

I værste fald, når for eksempel tæt på a er tæt på 1, klarer Fermats algoritme dårligere end divisor-søgemetoden . Antal iterationer for en given sag $-en$ $n,$ $b$

\operatorname {Iter} (n)={\frac {a+b}{2}}-\left\lceil n^{1/2}\right\rceil \approx {\frac {n}{2 }}-\left\lceil n^{1/2}\right\rceil ,

det vil sige, at det er åbenlyst, at det har orden $På).$

Fermats faktoriseringsmetode vil fungere lige så godt som divisoropregningsmetoden, hvis det er muligt at få et estimat for en større divisor herfra . Derfor har Fermats metode et eksponentielt estimat og er som forsøgsdelingsmetode ikke egnet til at nedbryde store tal . Du kan forbedre effektiviteten, hvis du først prøver at dividere et tal med tal fra 2 til en konstant B og derefter søge efter divisorer ved hjælp af Fermats metode. En sådan kampagne hjælper med at slippe af med små divisorer af tallet [5] . $\operatorname {Iter} (n)<n^{1/2},$ $a<4n^{1/2}.$ $n$ $n$

Divisor optimering

Antag, at vi forsøger at faktorisere tallet n = 2345678917 ved hjælp af Fermats metode, men udover b beregner vi også a − b . Startende med kan man skrive: ${\sqrt {n}}$

-en	48 433	48 434	48 435	48 436
b 2	76 572	173 439	270 308	367 179
b	276,7	416,5	519,9	605,9
a - b	48.156,3	48.017,5	47.915,1	47.830,1

Hvis vi nu begyndte at bruge divisor-optællingsmetoden til at dekomponere et tal , så ville det give mening kun at kontrollere divisorer op til 47.830, og ikke op til 48.432, da hvis der var en større divisor, så ville den blive fundet ved Fermats metode . Så i kun fire trin kontrollerede Fermats metode alle divisorer fra 47.830 til 48.432. $n$ $n$ $n$

Det er således muligt at kombinere Fermats metode med divisor optællingsmetoden. Det er nok at vælge et tal og bruge Fermat-metoden til at kontrollere divisorerne mellem og , og de resterende divisorer kan kontrolleres ved at optælle divisorerne, og divisorer skal kun kontrolleres op til tallet [6] . $c>{\sqrt {n))$ $c$ ${\sqrt {n}}$ $c-{\sqrt {c^{2}-n))$

I eksemplet ovenfor, når , skal divisorerne itereres op til tallet 47830. Du kan også f.eks. vælge det tal , der giver grænsen 28937. $c=48436$ $c=55000$

Kombinationen af metoder er god, for med en tilstrækkelig forskel mellem divisorerne af et tal er metoden til opregning af divisorer mere effektiv end Fermats metode [5] . Dette illustreres af følgende eksempel: $n$

-en	60 001	60 002
b 2	1 254 441 084	1 254 561 087
b	35.418,1	35.419,8
a - b	24.582,9	24.582,2

Sigtemetode

Når du leder efter kvadratet af et naturligt tal i en talfølge, behøver du ikke at beregne kvadratroden af hver værdi i den rækkefølge, eller endda kontrollere alle mulige værdier for en . Overvej for eksempel et tal : $a^{2}-n$ $n=2345678917$

-en	48 433	48 434	48 435	48 436
b 2	76 572	173 439	270 308	367 179
b	276,7	416,5	519,9	605,9

Du kan med det samme, uden at beregne kvadratroden, sige, at ingen af værdierne i tabellen er en kvadrat. Det er f.eks. tilstrækkeligt at bruge det faktum, at alle kvadrater af naturlige tal taget modulo 20 er lig med en af følgende værdier: 0, 1, 4, 5, 9, 16. Disse værdier gentages for hver stigning i a med 10. I modulo-eksemplet 20 får vi derfor ved at trække 17 fra (eller lægge 3 sammen), at tallet modulo 20 er lig med en af følgende: 3, 4, 7, 8, 12, 19. Men da er et naturligt tal, herfra får vi at modulo 20 kun kan være lig med 4. Derfor modulo 20 og eller modulo 10. Du kan altså tjekke roden af udtrykket ikke for alle , men kun for dem der ender på 1 eller 9 [6] . $b^{2}$ $n=17$ $b^{2}$ $b$ $b^{2}$ $a^{2}=1$ $a=1$ $a=9$ $a^{2}-n$ $-en$

På samme måde kan enhver potens af forskellige primtal bruges som modul. For eksempel, hvis vi tager det samme tal , finder vi $n=2345678917$

Modul 16:	kvadrater er lige store	0, 1, 4 eller 9
	n mod 16 er lig	5
	derfor lig $a^2$	9
	og en er	3, 5, 11 eller 13 modulo 16
Modul 9:	kvadrater er lige store	0, 1, 4 eller 7
	n mod 9 er lig med	7
	derfor lig $a^2$	7
	og en er	4 eller 5 modulo 9

Multiplikatoroptimering

Fermats metode fungerer godt, når tallet har en faktor, der er omtrent lig med kvadratroden af [5] . $n$ $n$

Hvis du kender det omtrentlige forhold mellem tallets faktorer , kan du vælge et rationelt tal , der er omtrent lig med dette forhold. Så kan vi skrive følgende lighed: , hvor faktorerne og er tæt på grund af de antagelser, der er lavet. Ved at anvende Fermats metode til at udvide antallet kan de derfor hurtigt findes. Yderligere, for at finde og, kan du bruge lighederne og (i tilfælde af, at det ikke er deleligt med og ikke er deleligt med ). $d/c$ $n$ $u/v$ $nuv=cv\cdot du$ $cv$ $du$ $nuv$ $c$ $d$ $\gcd(n,cv)=c$ $\gcd(n,du)=d$ $u$ $c$ $v$ $d$

Generelt, når forholdet mellem faktorerne ikke er kendt, kan man prøve at bruge forskellige forhold og forsøge at udvide det resulterende tal . En algoritme baseret på denne metode blev først foreslået af den amerikanske matematiker Sherman Lehman i 1974 [7] og kaldes Lehman-metoden . Algoritmen faktoriserer deterministisk et givet naturligt tal i aritmetiske operationer [8] , men i øjeblikket er den kun af historisk interesse og bruges næsten aldrig i praksis [9] . $n$ $u/v$ $nuv$ $n$ $O(n^{{1/3}})$

Krajczyk-gårdmetoden

En generalisering af Fermats metode blev foreslået af Maurice Krajczyk i 1926. Han foreslog at overveje i stedet for par af tal , der opfylder relationen , se efter par af tal, der opfylder en mere generel sammenligning. En sådan sammenligning kan findes ved at gange flere sammenligninger af formen , hvor er små tal, hvis produkter vil være en firkant. For at gøre dette kan vi overveje par af tal , hvor er et heltal lidt større end , og . Krajczyk bemærkede, at mange af tallene opnået på denne måde er opdelt i små primfaktorer, det vil sige, at tallene er jævne [10] . $(x,y),$ $x^{2}-y^{2}=n,$ $x^{2}\equiv y^{2}{\pmod {n}}.$ ${\displaystyle u_{i}^{2}\equiv v_{i))$ $v_{i}$ $(u_{i},v_{i})$ $u_{i}$ ${\sqrt n}$ $v_{i}=u_{i}^{2}-n$ $v_{i}$ $v_{i}$

Rækkefølgen af handlinger ifølge Krajcik [11]

Find det sæt af par , der opfylder relationen $(x,y),$ $x\equiv y{\pmod {n)).$
Bestem den fulde eller delvise nedbrydning af tal og faktorer for hvert par $x$ $y$ $(x,y).$
Vælg par, hvis produkt vil tilfredsstille forholdet $(x,y),$ $x^{2}\equiv y^{2}{\pmod {n}}.$
Faktoriser et tal . $n$

Eksempel [12]

Ved hjælp af Krajczyk-Farm-metoden dekomponerer vi tallet Tallet er det første, hvis kvadrat er større end tallet : $n=2041.$ $46$ $n$ $46^{2}=2116.$

Beregn værdien af funktionen for alle Vi får $v(u)=u^{2}-n$ $u=46,47,\dots$ $75,168,263,360,459,560,\dots$

Ifølge Fermats metode ville det være nødvendigt at fortsætte beregningerne, indtil kvadratet af et hvilket som helst tal blev fundet. Ifølge Krajczyk-Fermat-metoden, så er det nødvendigt successivt at søge efter dem , som derefter $u_{k}$ $v(u_{1})v(u_{2})\dots v(u_{k})=y^{2},u_{1}u_{2}\dots u_{k}=x.$

x^{2}=u_{1}^{2}u_{2}^{2}\dots u_{k}^{2}\equiv (u_{1}^{2}-n)\ cdot (u_{2}^{2}-n)\cdots (u_{k}^{2}-n)=v(u_{1})\cdot v(u_{2})\dots v(u_{ k})=y^{2}{\pmod {n}}.

Det følger af Krajczyk-Fermat-algoritmen, at alle de resulterende tal let kan faktoriseres. $(u_{k}^{2}-n)$

Virkelig: $75=3\cdot 5^{2},\ 168=2^{3}\cdot 3\cdot 7,\ 360=2^{3}\cdot 3^{2}\cdot 5,\ 560 =2^{4}\cdot 5\cdot 7.$

Det er klart, at produktet af de opnåede fire tal vil være et kvadrat: Så kan vi nu regne $2^{{10}}\cdot 3^{4}\cdot 5^{4}\cdot 7^{2}.$ $(x,y):$

x=46\cdot 47\cdot 49\cdot 51\equiv 311{\pmod {2041)),

y=2^{5}\cdot 3^{2}\cdot 5^{2}\cdot 7\equiv 1416{\pmod {2041)).

Dernæst finder vi ved hjælp af Euclid-algoritmen . $\gcd(1416-311,2041)=13$

På denne måde $2041=13\cdot 157.$

Dixons algoritme

I 1981 udgav matematikeren John Dixon fra Carleton University sin egen faktoriseringsmetode baseret på Krajczyks ideer [13] [14] [15] [16] .

Dixons algoritme er baseret på begrebet faktorbaser og er en generalisering af Fermats faktoriseringsalgoritme. I algoritmen søges der i stedet for talpar, der opfylder ligningen, efter talpar , der opfylder en mere generel ligning , for hvilken løsning Krajczyk bemærkede flere nyttige fakta. Beregningsmæssig kompleksitet af algoritmen [17] $x^2 - y^2 = n$ $x^2 \equiv y^2\pmod{n}$

T=O\left({L\left({n}\right)}^{2}\right),

hvor $L\left({n}\right)=\exp {\left({\sqrt {\ln {n}\cdot \ln {\ln {n))))\right)}.$

Andre forbedringer

Ideen med Fermats faktoriseringsmetode ligger til grund for nogle af de hurtigste algoritmer til faktorisering af store semiprimtal - den kvadratiske sigtemetode og den generelle talfeltsigtemetode . Den væsentligste forskel mellem den kvadratiske sigtemetode og Fermats metode er, at i stedet for at søge efter et kvadrat, indeholder sekvensen par af sådanne tal, hvis kvadrater er lige store i absolut værdi (hvert af disse par kan være en dekomponering af et tal ). Derefter søges der blandt de fundne talpar efter parret, hvilket er udvidelsen af tallet . [atten] $a^{2}-n$ $n$ $n$ $n$

En udvikling af Fermats faktoriseringsmetode er Shanks' metode til kvadratiske former (også kendt som SQUFOF), baseret på anvendelsen af kvadratiske former . Interessant nok er algoritmer baseret på denne metode de ubestridte førende blandt faktoriseringsalgoritmer for tal fra til [19] for 32-bit computere . $10^{{10}}$ $10^{18}$

Ansøgning

Fermats faktoriseringsalgoritme kan anvendes til RSA-kryptanalyse . Hvis tilfældige tal, hvis produkt er lig med, er tæt på hinanden, så kan de findes ved Fermats faktoriseringsmetode. Så kan du finde den hemmelige eksponent , og dermed knække RSA [20] [21] . På tidspunktet for offentliggørelsen af RSA-algoritmen var der kun kendt et lille antal faktoriseringsalgoritmer, hvoraf den mest berømte var Fermats metode. $p,q$ $n$ $d$

Interessante fakta

Den kendte engelske økonom og logistiker W. S. Jevons gjorde følgende antagelse i sin bog The Principles of Science ( 1874 ) [22] :

Givet to tal, kan du finde deres produkt på en enkel og pålidelig måde, men det er en helt anden sag, når du skal finde dets faktorer for et stort antal. Kan du se, hvilke to tal der ganges til 8616460799 ? Jeg tror ikke, at andre end mig ved det.

Interessant nok kan det tal, der er angivet af Jevons, dekomponeres manuelt ved Fermats metode ved hjælp af sigtemetoden på cirka 10 minutter. Faktisk ,. Ved hjælp af sigtemetoden kan man hurtigt komme frem til forholdet $\left\lceil {\sqrt {n}}\right\rceil =92\,825$

92\,880^{2}-n=10\,233\,601=3199^{2}.

Således har nedbrydningen til prime faktorer formen . $8\,616\,460\,799=89\,681\cdot 96\,079$

Jevons hovedidé om kompleksiteten i at nedbryde tal i primfaktorer i sammenligning med deres multiplikation er gyldig, men kun når det kommer til produktet af tal, der ikke er så tæt på hinanden [23] .

Se også

Noter

↑ Fletcher, Colin R. En rekonstruktion af Frenicle-Fermat korrespondancen fra 1640 // Historia Mathematica : journal. - 1991. - Bd. 18 , nr. 4 . - S. 311-410 . (utilgængeligt link)
↑ Pierre de Fermat; Paul Garveri; Charles Henry; Apollonius, af Perga.; Jacques de Billy. 2 // Œuvres de Fermat . - Paris: Gauthier-Villars et fils, 1894.
↑ Koblitz, 2001 , s. 161.
↑ David Bishop. Introduktion til kryptografi med Java -applets . - Jones og Bartlett Inc., 2003. - S. 224. - 384 s. — ISBN 0-7637-2207-3 .
↑ 1 2 3 Ishmukhametov, 2011 , s. 54.
↑ 12 McKee , James . Speeding Fermats factoring-metode (1991).
↑ Lehman, R. Sherman. Faktorering af store heltal // Beregningsmatematik. - 1974. - T. 28 , nr. 126 . - S. 637-646 . - doi : 10.2307/2005940 .
↑ Lehman, R. Sherman. Faktorering af store heltal (ubestemt) // Beregningsmatematik. - 1974. - T. 28 , nr. 126 . - S. 637-646 . - doi : 10.2307/2005940 .
↑ Nesterenko, 2011 , s. 140.
↑ Ishmukhametov, 2011 , s. 115.
↑ Nesterenko, 2011 , s. 164.
↑ Carl Pomerance. A Tale of Two Sieves // Bemærker Amer. Matematik. soc. - 1996. - Bd. 43 , nr. 12 . - S. 1473-1485 .
↑ Dixon, J.D.Asymptotisk hurtig faktorisering af heltal // Matematik . Comp. : journal. - 1981. - Bd. 36 , nr. 153 . - S. 255-260 . - doi : 10.1090/S0025-5718-1981-0595059-1 . — .
↑ Ishmukhametov, 2011 , s. 117.
↑ Cheremushkin, 2002 , s. 75-77.
↑ Vasilenko, 2003 , s. 57-60.
↑ Cheremushkin, 2002 , s. 79-80.
↑ Pomerance, Carl . A Tale of Two Sieves (december 1996), s. 1473–1485. Arkiveret 11. november 2020. Hentet 18. november 2012.
↑ Yike Guo, 2002 , High Performance Data Mining: Scaling Algorithms, Applications and Systems..
↑ Benne de Weger. Gensyn med Fermats faktorisering for RSA-modulet // Appl . Algebra Eng. commun. Comput. : journal. - 2002. - T. 13 , nr. 1 . - S. 17-28 . - doi : 10.1007/s002000100088 .
↑ Sounak Gupta, Goutam Paul. Revisiting Fermat's Factorization for the RSA Modulus (engelsk) // CoRR : journal. - 2009. - T. abs / 0910.4179 .
↑ Principles of Science , Macmillan & Co., 1874, s. 141.
↑ Knuth, 2007 , s. 435.

Litteratur

på russisk

Vasilenko O. N. Talteoretiske algoritmer i kryptografi . - M .: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Arkiveret 27. januar 2007 på Wayback Machine
Ishmukhametov Sh. T. Faktoriseringsmetoder for naturlige tal: en tutorial . - Kazan: Kazan. un., 2011. - 190 s.
Koblitz N. Et kursus i talteori og kryptografi . - 2. - M . : Videnskabeligt forlag TVP, 2001. - 254 s. — ISBN 5-94057-103-4 .
Nesterenko A. Introduktion til moderne kryptografi Talteoretiske algoritmer . - 2011. - 190 s.
Cheremushkin AV Forelæsninger om aritmetiske algoritmer i kryptografi . - M .: MTSNMO , 2002. - 104 s. — ISBN 5-94057-060-7 . Arkiveret 31. maj 2013 på Wayback Machine
Donald Knuth . The Art of Computer Programming, bind 2. Afledte metoder = The Art of Computer Programming, vol.2. Seminumeriske algoritmer. - 3. udg. - M . : "Williams" , 2007. - 832 s. — ISBN 5-8459-0081-6 .

på engelsk

Bressoud DM Faktorisering og Primality Testing . - New York: Springer-Verlag, 1989. - 260 s. - ISBN 0-387-97040-1 . (utilgængeligt link)

Mahoney MS Pierre de Fermats matematiske karriere . - 2. - Paris: Princeton Univ. Presse, 1994. - S. 324-332. — 438 s. - ISBN 0-691-03666-7 .

Yike Guo, R.L. Grossman. High Performance Data Mining: Skaleringsalgoritmer, applikationer og systemer . - 2. - 2002. - 112 s. — ISBN 978-0792377450 .

på fransk

Kraitchik M. Faktorisering og primalitetstestning . - Paris: Gauthier-Villars, 1926. - T. 2. - S. 195-208. — 251 s. - ISBN 0-387-97040-1 .

Links

Online lommeregner baseret på Fermats faktoriseringsmetode

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme