Fermats faktoriseringsmetod

Fermats faktoriseringsmetod är en algoritm för att faktorisera (faktorera) ett udda heltal , föreslagen av Pierre Fermat ( 1601 - 1665 ) 1643 . $n$

Metoden bygger på att söka efter sådana heltal och som uppfyller relationen , vilket leder till en nedbrytning av . $x$ $y$ $x^{2}-y^{2}=n$ $n=(xy)\cdot (x+y)$

Historik

I början av 1600-talet i Frankrike började matematiska idéer aktivt spridas bland vetenskapsmän genom korrespondens. 1638 gick Pierre Fermat med i kretsen av korrespondentforskare . Korrespondens var ett bekvämt sätt att kommunicera, eftersom Fermat bodde i Toulouse och många av hans bekanta forskare bodde i Paris . En av dessa forskare var Maren Mersenne , som var engagerad i distribution av brev, vidarebefordran och kommunikation av många forskare sinsemellan. Den 26 december 1638 nämnde Fermat i ett brev till Mersenne att han hade hittat en metod med vilken man kunde hitta delare av positiva tal, men han utelämnade alla detaljer och en beskrivning av metoden. Vid den tiden korresponderade Mersenne också med den franske matematikern Bernard Frenicle de Bessy , som, liksom Fermat, var engagerad i talteori , i synnerhet delare av naturliga tal och perfekta tal . I början av 1640 , efter att ha fått veta att Fermat hade fått en metod för att hitta divisorer, skrev Frenicle till Mersenne, som vidarebefordrade Fermats brev. Mersenne var under lång tid länken mellan de två matematikerna i deras korrespondens. Det var i breven till Frenicle som Fermat kunde bevisa riktigheten av faktoriseringsmetoden, samt för första gången formulera och motivera huvudbestämmelserna i satsen, som senare kallades Fermats lilla sats [1] [2 ] .

Motivering

Fermats metod är baserad på satsen om representationen av ett tal som skillnaden mellan två kvadrater :

Om det är udda, så finns det en en-till-en-överensstämmelse mellan faktoriseringen och representationen som en skillnad av kvadrater med , givet av formlerna $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

Om faktoriseringen ges , så gäller förhållandet: . Således erhålls en representation i form av en skillnad på två kvadrater. $n=a\cdot b$ $n=a\cdot b=\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {ab}{2}}\right)^ {2}$

Omvänt, om givet att , då kan höger sida faktoriseras: [3] . $n=x^{2}-y^{2}$ $(xy)(x+y)$

Beskrivning av algoritmen

För att faktorisera ett udda tal, söks efter ett par tal så att , eller . I det här fallet är siffrorna och divisorer , möjligen triviala (det vill säga en av dem är lika med 1 och den andra är lika med ). $n$ $(x, y)$ $x^2 - y^2 = n$ $(xy)\cdot (x+y)=n$ $(x+y)$ $(xy)$ $n$ $n$

I det icke-triviala fallet är likhet likvärdig med , det vill säga vad som är en kvadrat . $x^2 - y^2 = n$ $x^{2}-n=y^{2}$ $x^{2}-n$

Sökandet efter en kvadrat av detta slag börjar med - det minsta talet för vilket skillnaden är icke-negativ. $x=\left\lceil {\sqrt {n))\right\rceil$ $x^{2}-n$

För varje värde som börjar från , beräkna och kontrollera om detta tal inte är en exakt kvadrat. Om inte, öka med en och gå till nästa iteration. $k\in {\mathbb {N}),$ $k=1$ $\left(\left\lceil {\sqrt {n))\right\rceil +k\right)^{2}-n$ $k$

Om är en exakt kvadrat, det vill säga så erhålls expansionen: $\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,

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

Om det är trivialt och unikt, så är det enkelt. $n$

I praktiken beräknas uttryckets värde i det -th steget med hänsyn till värdet i det -th steget: $(k+1)$ $k$

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

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

Exempel

Exempel på låg iteration

Låt oss ta ett nummer . Beräkna för vi kommer att beräkna värdena för funktionen . För ytterligare enkelhet kommer vi att konstruera en tabell som innehåller värdena och vid varje iterationssteg. Vi får: $n=10873$ $s=\left\lceil {\sqrt {n}}\right\rceil =105.$ $k=0,1,2,...$ $s+k$ $y=(s+k)^{2}-n$ ${\sqrt {y}}$

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

Som framgår av tabellen erhölls redan vid det andra iterationssteget ett heltalsvärde . ${\sqrt {y}}$

Följande uttryck äger alltså rum: . Därav följer det $(105+2)^{2}-n=24^{2}$ $n=107^{2}-24^{2}=131\cdot 83=10873.$

Ett exempel med ett stort antal iterationer

Låt Då eller $n=89755.$ ${\sqrt {n}}\approx 299.591$ $s=\left\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

Denna expansion är inte ändlig, eftersom talet uppenbarligen inte är primtal: $145$ $145=29\cdot 5.$

Som ett resultat, den slutliga nedbrytningen av det ursprungliga numret till produkten av primtalsfaktorer $n$ $89755=5\cdot 29\cdot 619.$

Prestandautvärdering

Den största effektiviteten av beräkningen med Fermat-faktoriseringsmetoden uppnås när talets faktorer är ungefär lika med varandra. Detta ger en relativt kort sekvenssökning [4] $n$

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

I värsta fall, när till exempel nära a är nära 1, presterar Fermats algoritm sämre än divisorsökmetoden . Antal iterationer för ett givet fall $a$ $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 vill säga det är uppenbart att den har ordningen $På).$

Fermats faktoriseringsmetod kommer att fungera lika bra som divisoruppräkningsmetoden om det är möjligt att få en uppskattning för en större divisor härifrån.Därför har Fermats metod en exponentiell skattning och är som en försöksdivisionsmetod inte lämplig för att bryta ner stora tal . Du kan förbättra effektiviteten om du först försöker dividera ett tal med tal från 2 till någon konstant B och sedan söka efter divisorer med Fermats metod. En sådan kampanj hjälper till att bli av med små delare av antalet [5] . $\operatorname {Iter} (n)<n^{1/2},$ $a<4n^{1/2}.$ $n$ $n$

Divisoroptimering

Anta att vi försöker faktorisera talet n = 2345678917 med Fermats metod, men förutom b beräknar vi även a − b . Börjar med kan man skriva: ${\sqrt {n}}$

a	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

Om vi nu började använda divisoruppräkningsmetoden för att dekomponera ett tal , då skulle det vara vettigt att kontrollera divisorer endast upp till 47 830, och inte upp till 48 432, eftersom om det fanns en större divisor, så skulle den hittas med Fermats metod . Så, i bara fyra steg, kontrollerade Fermats metod alla divisorer från 47 830 till 48 432. $n$ $n$ $n$

Det är alltså möjligt att kombinera Fermats metod med divisoruppräkningsmetoden. Det räcker med att välja ett tal och använda Fermat-metoden för att kontrollera divisorerna mellan och , och de återstående divisorerna kan kontrolleras genom att räkna upp divisorerna, och divisorer behöver endast kontrolleras upp till talet [6] . $c>{\sqrt {n))$ $c$ ${\sqrt {n}}$ $c-{\sqrt {c^{2}-n))$

I exemplet ovan, när , måste divisorerna itereras upp till talet 47830. Du kan också till exempel välja talet som ger gränsen 28937. $c=48436$ $c=55000$

Kombinationen av metoder är bra, för med en tillräcklig skillnad mellan ett tals divisorer är metoden för uppräkning av divisorer mer effektiv än Fermats metod [5] . Detta illustreras av följande exempel: $n$

a	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

Siktmetod

När du letar efter kvadraten av ett naturligt tal i en talföljd behöver du inte beräkna kvadratroten av varje värde i den sekvensen, eller ens kontrollera alla möjliga värden för en . Tänk till exempel på ett nummer : $a^{2}-n$ $n=2345678917$

a	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 omedelbart, utan att beräkna kvadratroten, säga att inget av värdena i tabellen är en kvadrat. Det räcker till exempel att använda det faktum att alla kvadrater av naturliga tal tagna modulo 20 är lika med ett av följande värden: 0, 1, 4, 5, 9, 16. Dessa värden upprepas för varje ökning av a med 10. I moduloexemplet 20 får vi därför, genom att subtrahera 17 (eller lägga till 3), att talet modulo 20 är lika med något av följande: 3, 4, 7, 8, 12, 19. Men eftersom är ett naturligt tal, härifrån får vi att modulo 20 bara kan vara lika med 4. Därför modulo 20 och eller modulo 10. Du kan alltså kontrollera roten av uttrycket inte för alla utan bara för de som slutar på 1 eller 9 [6] . $b^{2}$ $n=17$ $b^{2}$ $b$ $b^{2}$ $a^{2}=1$ $a=1$ $a=9$ $a^{2}-n$ $a$

På liknande sätt kan alla potenser av olika primtal användas som modul. Om vi till exempel tar samma nummer hittar vi $n=2345678917$

Modulo 16:	rutor är lika	0, 1, 4 eller 9
	n mod 16 är lika med	5
	därför lika $a^2$	9
	och ett är	3, 5, 11 eller 13 modulo 16
Modul 9:	rutor är lika	0, 1, 4 eller 7
	n mod 9 är lika med	7
	därför lika $a^2$	7
	och ett är	4 eller 5 modulo 9

Multiplikatoroptimering

Fermats metod fungerar bra när talet har en faktor som är ungefär lika med kvadratroten av [5] . $n$ $n$

Om du känner till det ungefärliga förhållandet mellan talets faktorer kan du välja ett rationellt tal som är ungefär lika med detta förhållande. Då kan vi skriva följande likhet: , där faktorerna och är nära på grund av de antaganden som gjorts. Därför kan de snabbt hittas genom att använda Fermats metod för att utöka antalet . Vidare, för att hitta och, kan du använda likheterna och (om det inte är delbart med och inte är delbart 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$

I allmänhet, när förhållandet mellan faktorerna inte är känt, kan man försöka använda olika förhållanden och försöka utöka det resulterande talet . En algoritm baserad på denna metod föreslogs först av den amerikanske matematikern Sherman Lehman 1974 [7] och kallas Lehman-metoden . Algoritmen faktoriserar deterministiskt ett givet naturligt tal i aritmetiska operationer [8] , men för närvarande är den endast av historiskt intresse och används nästan aldrig i praktiken [9] . $n$ $u/v$ $nuv$ $n$ $O(n^{{1/3}})$

Krajczyk-gårdsmetoden

En generalisering av Fermats metod föreslogs av Maurice Krajczyk 1926. Han föreslog att istället för par av nummer som uppfyller relationen , leta efter par av nummer som uppfyller en mer allmän jämförelse. En sådan jämförelse kan hittas genom att multiplicera flera jämförelser av formen , där är små tal, vars produkter kommer att vara en kvadrat. För att göra detta kan vi överväga par av nummer , där är ett heltal något större än , och . Krajczyk märkte att många av de siffror som erhålls på detta sätt bryts ner i små primtalsfaktorer, det vill säga talen är jämna [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}$

Handlingssekvensen enligt Krajcik [11]

Hitta den uppsättning par som uppfyller relationen $(x,y),$ $x\equiv y{\pmod {n)).$
Bestäm den fullständiga eller partiella nedbrytningen av tal och faktorer för varje par $x$ $y$ $(x,y).$
Välj par vars produkt kommer att uppfylla förhållandet $(x,y),$ $x^{2}\equiv y^{2}{\pmod {n}}.$
Faktorisera ett tal . $n$

Exempel [12]

Med Krajczyk-Farm-metoden bryter vi ner talet. Talet är det första vars kvadrat är större än talet : $n=2041.$ $46$ $n$ $46^{2}=2116.$

Beräkna värdet på funktionen för alla Vi får $v(u)=u^{2}-n$ $u=46,47,\dots$ $75,168,263,360,459,560,\dots$

Enligt Fermats metod skulle det vara nödvändigt att fortsätta beräkningarna tills kvadraten på något tal hittades. Enligt Krajczyk-Fermat-metoden, då är det nödvändigt att successivt söka efter de som Då $Storbritannien}$ $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öljer av Krajczyk-Fermat-algoritmen att alla resulterande siffror lätt kan faktoriseras. $(u_{k}^{2}-n)$

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

Uppenbarligen kommer produkten av de fyra erhållna talen att vara en kvadrat: Då kan vi nu räkna $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)).

Därefter, med hjälp av Euklids algoritm, hittar vi . $\gcd(1416-311,2041)=13$

På det här sättet, $2041=13\cdot 157.$

Dixons algoritm

År 1981 publicerade matematikern John Dixon från Carleton University sin egen faktoriseringsmetod baserad på Krajczyks idéer [13] [14] [15] [16] .

Dixons algoritm bygger på konceptet faktorbaser och är en generalisering av Fermats faktoriseringsalgoritm. I algoritmen, istället för par av siffror som uppfyller ekvationen, söks efter siffror som uppfyller en mer allmän ekvation , för vilken lösning Krajczyk märkte flera användbara fakta. Algoritmens beräkningskomplexitet [17] $x^2 - y^2 = n$ $x^2 \equiv y^2\pmod{n}$

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

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

Andra förbättringar

Idén med Fermats faktoriseringsmetod ligger till grund för några av de snabbaste algoritmerna för faktorisering av stora semiprimtal - den kvadratiska siktmetoden och den allmänna talfältssiktmetoden . Den största skillnaden mellan den kvadratiska sållmetoden och Fermats metod är att istället för att söka efter en kvadrat innehåller sekvensen par av sådana tal vars kvadrater är lika i absolut värde (vart och ett av dessa par kan vara en nedbrytning av ett tal ). Sedan, bland de hittade nummerparen, söks paret efter, vilket är expansionen av talet . [arton] $a^{2}-n$ $n$ $n$ $n$

En utveckling av Fermats faktoriseringsmetod är Shanks metod för kvadratiska former (även känd som SQUFOF), baserad på tillämpningen av kvadratiska former . Intressant nog, för 32-bitars datorer, är algoritmer baserade på denna metod de obestridda ledarna bland faktoriseringsalgoritmer för tal från till [19] . $10^{{10}}$ $10^{18}$

Applikation

Fermats faktoriseringsalgoritm kan tillämpas på RSA-krypteringsanalys . Om slumptal vars produkt är lika med ligger nära varandra, så kan de hittas med Fermats faktoriseringsmetod. Sedan kan du hitta den hemliga exponenten och därmed knäcka RSA [20] [21] . Vid tidpunkten för publiceringen av RSA-algoritmen var endast ett litet antal faktoriseringsalgoritmer kända, varav den mest kända var Fermats metod. $p,q$ $n$ $d$

Intressanta fakta

Den välkände engelske ekonomen och logistikern W. S. Jevons gjorde följande antagande i sin bok The Principles of Science ( 1874 ) [22] :

Med två siffror kan du hitta deras produkt på ett enkelt och tillförlitligt sätt, men det är en helt annan sak när du behöver hitta dess faktorer för ett stort antal. Kan du säga vilka två tal som multipliceras för att göra 8616460799 ? Jag tror inte att någon annan än jag vet detta.

Intressant nog kan siffran som anges av Jevons dekomponeras manuellt med Fermats metod med siktmetoden på cirka 10 minuter. Verkligen ,. Med hjälp av silmetoden kan man snabbt komma fram till relationen $\left\lceil {\sqrt {n}}\right\rceil =92\,825$

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

Sålunda har nedbrytningen till primtalsfaktorer formen . $8\,616\,460\,799=89\,681\cdot 96\,079$

Jevons huvudidé om komplexiteten i att sönderdela tal i primtal i jämförelse med deras multiplikation är giltig, men bara när det kommer till produkten av tal som inte är så nära varandra [23] .

Se även

Anteckningar

↑ Fletcher, Colin R. En rekonstruktion av Frenicle-Fermat-korrespondensen från 1640 // Historia Mathematica : journal. - 1991. - Vol. 18 , nr. 4 . - s. 311-410 . (inte tillgänglig länk)
↑ Pierre de Fermat; Paul Garveri; Charles Henry; Apollonius, av Perga.; Jacques de Billy. 2 // Œuvres de Fermat . - Paris: Gauthier-Villars et fils, 1894.
↑ Koblitz, 2001 , sid. 161.
↑ David Bishop. Introduktion till kryptografi med Java -applets . - Jones and Bartlett Inc., 2003. - S. 224. - 384 sid. — ISBN 0-7637-2207-3 .
↑ 1 2 3 Ishmukhametov, 2011 , sid. 54.
↑ 12 McKee , James . Speeding Fermats factoringmetod (1991).
↑ Lehman, R. Sherman. Factoring stora heltal // Mathematics of Computing. - 1974. - T. 28 , nr 126 . - S. 637-646 . - doi : 10.2307/2005940 .
↑ Lehman, R. Sherman. Factoring stora heltal (obestämd) // Mathematics of Computing. - 1974. - T. 28 , nr 126 . - S. 637-646 . - doi : 10.2307/2005940 .
↑ Nesterenko, 2011 , sid. 140.
↑ Ishmukhametov, 2011 , sid. 115.
↑ Nesterenko, 2011 , sid. 164.
↑ Carl Pomerance. A Tale of Two Sieves // Notices Amer. Matematik. soc. - 1996. - Vol. 43 , nr. 12 . - P. 1473-1485 .
↑ Dixon, J.D.Asymptotiskt snabb faktorisering av heltal // Math . Comp. : journal. - 1981. - Vol. 36 , nr. 153 . - S. 255-260 . - doi : 10.1090/S0025-5718-1981-0595059-1 . — .
↑ Ishmukhametov, 2011 , sid. 117.
↑ Cheremushkin, 2002 , sid. 75-77.
↑ Vasilenko, 2003 , sid. 57-60.
↑ Cheremushkin, 2002 , sid. 79-80.
↑ Pomerance, Carl . A Tale of Two Sieves (december 1996), s. 1473–1485. Arkiverad 11 november 2020. Hämtad 18 november 2012.
↑ Yike Guo, 2002 , High Performance Data Mining: Scaling Algorithms, Applications and Systems..
↑ Benne de Weger. Återbesök Fermats faktorisering för RSA -modulen // Appl . Algebra Eng. kommun. 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 (engelska) // CoRR : journal. - 2009. - T. abs / 0910.4179 .
↑ Principles of Science , Macmillan & Co., 1874, sid. 141.
↑ Knuth, 2007 , sid. 435.

Litteratur

på ryska

Vasilenko O. N. Talteoretiska algoritmer i kryptografi . - M. : MTSNMO , 2003. - 328 sid. — ISBN 5-94057-103-4 . Arkiverad 27 januari 2007 på Wayback Machine
Ishmukhametov Sh. T. Faktoriseringsmetoder för naturliga tal: en handledning . - Kazan: Kazan. un., 2011. - 190 sid.
Koblitz N. En kurs i talteori och kryptografi . - 2:a. - M . : Vetenskapligt förlag TVP, 2001. - 254 sid. — ISBN 5-94057-103-4 .
Nesterenko A. Introduktion till modern kryptografi Talteoretiska algoritmer . - 2011. - 190 sid.
Cheremushkin AV Föreläsningar om aritmetiska algoritmer i kryptografi . - M. : MTSNMO , 2002. - 104 sid. — ISBN 5-94057-060-7 . Arkiverad 31 maj 2013 på Wayback Machine
Donald Knuth . The Art of Computer Programming, Volym 2. Härledda metoder = The Art of Computer Programming, vol.2. Seminumeriska algoritmer. - 3:e uppl. - M . : "Williams" , 2007. - 832 sid. — ISBN 5-8459-0081-6 .

på engelska

Bressoud DM Faktorisering och Primalitetstestning . - New York: Springer-Verlag, 1989. - 260 sid. - ISBN 0-387-97040-1 . (inte tillgänglig länk)

Mahoney MS Pierre de Fermats matematiska karriär . - 2. - Paris: Princeton Univ. Press, 1994. - S. 324-332. — 438 sid. - ISBN 0-691-03666-7 .

Yike Guo, R.L. Grossman. High Performance Data Mining: Skalningsalgoritmer, applikationer och system . - 2. - 2002. - 112 sid. — ISBN 978-0792377450 .

på franska

Kraitchik M. Faktorisering och Primalitetstestning . - Paris: Gauthier-Villars, 1926. - T. 2. - S. 195-208. — 251 sid. - ISBN 0-387-97040-1 .

Länkar

Onlineräknare baserad på Fermats faktoriseringsmetod

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm