Toom-Cook-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21. helmikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 7 muokkausta .

Toom-Cook- algoritmi , jota joskus kutsutaan nimellä Toom-3 ja joka on nimetty Andrey Leonovich Toomin mukaan, joka ehdotti uutta algoritmia, jonka monimutkaisuus on vähäistä, ja Stephen Cook , joka kuvaili algoritmia selkeämmin, on algoritmi suurten lukujen kertomiseen. .

Kun on annettu kaksi suurta lukua a ja b , Toom-Cook-algoritmin mukaan sinun on jaettava a ja b k pienempään osaan, joiden pituus on l , ja suoritettava osille operaatioita. Kun k kasvaa , on mahdollista yhdistää joitain osion osien kertomisoperaatioita, mikä vähentää algoritmin yleistä monimutkaisuutta. Osion osien tulo voidaan sitten laskea käyttämällä samaa Toom-Cook-algoritmia rekursiivisesti. Termejä "Toom-3-algoritmi" ja "Toom-Cook-algoritmi" käytetään joskus virheellisesti keskenään, vaikka Toom-3 on vain erikoistapaus Toom-Cook-algoritmista k = 3:lle.

Toom-3 vähentää monimutkaisuutta 9 kertolaskusta viiteen ja toimii ajoissa . Yleensä Toomk toimii ajassa , jossa , on osaosien kertomiseen käytetty aika ja c on aika, joka kuluu yhteen- ja kertolaskuihin pienillä vakioilla [1] . Karatsuba-algoritmi on Toom-Cook-algoritmin erikoistapaus, jossa luku on jaettu kahteen osaan. Se vähentää monimutkaisuutta 4 kertolaskusta 3:een ja toimii siksi ajassa . Normaali kertolasku sarakkeella vastaa Toom-1:tä monimutkaisuudella . $\Theta (n^{\log(5)/\log(3)})\approx \Theta (n^{1{,}46})$ $\Theta (c(k)n^{e})$ ${\displaystyle e=\log {(2k-1)}/\log {(k)))$ $n^{e}$ $\Theta (n^{\log(3)/\log(2)})\approx \Theta (n^{1{,}58})$ $\Theta (n^{2})$

Vaikka e :n potenssi voidaan asettaa mahdollisimman lähelle 1:tä lisäämällä k , funktio c kasvaa valitettavasti hyvin nopeasti [1] [2] . Toom-Cook-sekajärjestelmien kasvuvauhti pysyi avoimena ongelmana vuoteen 2005 mennessä [3] . Donald Knuthin kuvaama toteutus on monimutkainen [4] . $\Theta (n2^{\sqrt {2\log n))\log n)$

Ylimääräisistä luvuista johtuen Toom-Cook-algoritmi pienille luvuille on hitaampi kuin kertominen sarakkeella, ja siksi sitä käytettiin yleensä keskikokoisille tekijöille, kunnes asymptoottisesti nopeampi Schönhage-Strassen-algoritmi (monimutkaisuus . $\Theta (n\log n\log {\log n))$

Toom kuvaili algoritmiaan vuonna 1963 , ja Cook julkaisi parannetun (asymptoottisesti vastaavan) algoritmin väitöskirjassaan vuonna 1966 [ 5] .

Tiedot

Tämä osa käsittelee Toomk- algoritmin toimintaa mille tahansa k :n arvolle ja tarjoaa yksinkertaistetun kuvauksen polynomien Toom-Cookin kertolaskusta Marco Bodraton [6] kuvaamalla tavalla . Algoritmissa on viisi päävaihetta:

jakaminen
Pisteiden laskeminen
Pisteinen kertolasku
Interpolointi
Uudelleenkokoonpano

Tyypillisessä suurten lukujen tulkinnassa jokainen kokonaisluku esitetään numerosarjana paikkalukujärjestelmässä , jossa lukukanta on jokin (yleensä suuri) arvo b . Esimerkissämme käytämme , jolloin jokainen numero vastaa neljän desimaalinumeron ryhmää (tietokonetoteutuksessa b on yleensä kahden potenssi). Oletetaan, että meidän täytyy kertoa kaksi numeroa $b=10000$

m	=	12	3456	7890	1234	5678	9012
n	=	9	8765	4321	9876	5432	1098.

Ne ovat paljon pienempiä kuin tavallisesti Toom-Cook-algoritmin käsittelemät, mutta ne kuvaavat algoritmia tässä.

Erittely

Ensimmäinen askel on valita kanta siten, että sekä m :n että n :n numeroiden määrä B -kannassa ei ylitä k :a (esimerkiksi Toom-3:ssa 3). Yleensä olen antanut $B=b^{i}$

i=\max \left\{\left\lfloor {\frac {\left\lfloor \log _{b}m\right\rfloor }{k))\right\rfloor ,\left\lfloor {\ frac {\left\lfloor \log _{b}n\right\rfloor }{k}}\right\rfloor \right\}+1.

Esimerkissämme käytämme Toom-3:a, joten valitsemme . Nyt jaetaan m ja n niiden kantaluvulla B numeroiksi : $B=b^{2}=10^{8}$ $m_{i},n_{i}$

{\begin{aligned}m_{2}&{}=123456\\m_{1}&{}=78901234\\m_{0}&{}=56789012\\n_{2}&{}= 98765\\n_{1}&{}=43219876\\n_{0}&{}=54321098\end{aligned}}

Käytämme näitä lukuja kertoimina polynomeissa p ja q asteen ( k − 1) ominaisuuksilla ja : $p(B)=m$ $q(B)=n$

p(x)=m_{2}x^{2}+m_{1}x+m_{0}=123456x^{2}+78901234x+56789012\,

q(x)=n_{2}x^{2}+n_{1}x+n_{0}=98765x^{2}+43219876x+54321098\,

Näiden polynomien käyttöönoton jälkeen saamme, että jos laskemme tulon , niin vastaus ongelmaan on . $r(x)=p(x)q(x)$ $r(B)=m\times n$

Siinä tapauksessa, että kerrotut luvut ovat erikokoisia, on hyödyllistä käyttää eri arvoja k :lle m ja n , joita merkitsemme ja . Esimerkiksi "Toom-2.5"-algoritmi viittaa Toom-Cook-algoritmiin ja . Tässä tapauksessa i in valitaan yleensä lausekkeella $k_m$ $k_n$ $k_{m}=3$ $k_{n}=2$ $B=b^{'}i$

i=\max \left\{\left\lfloor {\frac {\left\lceil \log _{b}m\right\rceil }{k_{m))}\right\rfloor ,\left\ lfloor {\frac {\left\lceil \log _{b}n\right\rceil }{k_{n))}\right\rfloor \right\}.

Laskenta pisteissä

Toom-Cookin lähestymistapa polynomien tulon laskemiseen on yleinen. Huomaa, että d -asteen polynomi määritellään yksiselitteisesti pisteillä (esimerkiksi suora on 1-asteinen polynomi ja sen määrittelee kaksi pistettä). Ajatuksena on laskea p (•) ja q (•) eri pisteissä. Sitten näiden pisteiden arvojen tulo suoritetaan polynomien tulon arvojen saamiseksi. Lopuksi interpoloimme saadut arvot polynomin kertoimien saamiseksi. $p(x)q(x)$ $d+1$

Koska , tarvitsemme pisteitä saadaksemme lopullisen tuloksen. Kutsutaan sitä d :ksi . Toom-3:n tapauksessa . Algoritmi toimii riippumatta siitä, mitkä pisteet valitaan (muutamalla pienellä poikkeuksella - katso vaatimus, että matriisi on käännettävä Interpolointi -osiossa ), mutta algoritmin yksinkertaistamiseksi on parempi käyttää pieniä arvoja, kuten 0, 1, -1 ja -2. $\deg(pq)=\deg(p)+\deg(q)$ $\deg(p)+\deg(q)+1=k_{m}+k_{n}-1$ $d=5$

Yksi epätavallinen piste, jota usein käytetään, on äärettömyys, eli . Polynomin p "laskemiseksi" äärettömässä ottamalla raja , koska x pyrkii äärettömään. Siksi se on aina yhtä suuri kuin johtavan kertoimen arvo (edellä olevassa esimerkissä kerroin ). $\infty$ ${\displaystyle p(x)/x^{\deg p))$ $p(\infty )$ $m_2$

Toom-3-esimerkissämme käytämme pisteitä 0, 1, −1, −2 ja . Tämä valinta yksinkertaistaa pistelaskentaa ja antaa kaavat: $\infty$

{\begin{array}{lrlrl}p(0)&=&m_{0}+m_{1}(0)+m_{2}(0)^{2}&=&m_{0}\\ p(1)&=&m_{0}+m_{1}(1)+m_{2}(1)^{2}&=&m_{0}+m_{1}+m_{2}\\p( -1)&=&m_{0}+m_{1}(-1)+m_{2}(-1)^{2}&=&m_{0}-m_{1}+m_{2}\\p (-2)&=&m_{0}+m_{1}(-2)+m_{2}(-2)^{2}&=&m_{0}-2m_{1}+4 m_{2}\\ p(\infty )&=&m_{2}&&\end{array}}

Ja samoin q :lle . Esimerkissämme saamamme arvot ovat:

$p(0)$	=	$m_{0}$	=	56789012	=	56789012
$p(1)$	=	${\displaystyle m_{0}+m_{1}+m_{2))$	=	$56789012+78901234+123456$	=	135813702
$p(-1)$	=	${\displaystyle m_{0}-m_{1}+m_{2))$	=	$56789012-78901234+123456$	=	−21988766
$p(-2)$	=	$m_{0}-2m_{1}+4m_{2}$	=	$56789012-2\times 78901234+4\times 123456$	=	−100519632
$p(\infty )$	=	$m_2$	=	123456	=	123456
$q(0)$	=	$n_{0}$	=	54321098	=	54321098
$q(1)$	=	${\displaystyle n_{0}+n_{1}+n_{2))$	=	$54321098+43219876+98765$	=	97639739
$q(-1)$	=	${\displaystyle n_{0}-n_{1}+n_{2))$	=	$54321098-43219876+98765$	=	11199987
$q(-2)$	=	${\displaystyle n_{0}-2n_{1}+4n_{2))$	=	$54321098-2\times 43219876+4\times 98765$	=	−31723594
$q(\infty )$	=	$n_{2}$	=	98765	=	98765.

Kuten näet, nämä arvot voivat olla negatiivisia.

Lisäselvitystä varten on hyödyllistä ajatella tätä pistelaskentaprosessia matriisin kertomisena oikealla olevalla vektorilla, jossa jokainen matriisin rivi sisältää yhden valitun pisteen potenssit ja vektori sisältää kertoimet polynomi:

\left({\begin{matrix}p(0)\\p(1)\\p(-1)\\p(-2)\\p(\infty )\end{matrix}}\ right)=\left({\begin{matrix}0^{0}&0^{1}&0^{2}\\1^{0}&1^{1}&1^{2}\\(-1) ^{0}&(-1)^{1}&(-1)^{2}\\(-2)^{0}&(-2)^{1}&(-2)^{2} \\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right)=\left( {\begin{matrix}1&0&0\\1&1&1\\1&-1&1\\1&-2&4\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1 }\\m_{2}\end{matrix}}\right).

Matriisien mitat ovat yhtä suuret p :lle ja q : lle . Äärettömän rivillä on nolla arvoa paitsi viimeisessä sarakkeessa, jossa on 1. ${\displaystyle d\times k_{m))$ ${\displaystyle d\times k_{n))$

Nopeampi arvojen laskeminen

Pistearvot voidaan laskea nopeammin kuin yllä olevissa kaavoissa on ilmoitettu. Alkeisoperaatioiden (lisäys/vähennys) määrää voidaan vähentää. Bodraton [6] Toom-3:lle suunnittelema operaatiosarja näytetään tässä ensimmäiselle operandille (polynomi p ):

$p_{0}$	$\vasen nuoli$	${\displaystyle m_{0}+m_{2))$	=	56789012 + 123456	=	56912468
$p(0)$	=	$m_{0}$	=	56789012	=	56789012
$p(1)$	=	$p_{0}+m_{1}$	=	56912468 + 78901234	=	135813702
$p(-1)$	=	${\displaystyle p_{0}-m_{1))$	=	56912468 − 78901234	=	−21988766
$p(-2)$	=	${\näyttötyyli (p(-1)+m_{2})\times 2-m_{0))$	=	$(-21988766+123456)\times 2-56789012$	=	− 100519632
$p(\infty )$	=	$m_2$	=	123456	=	123456.

Tämä sarja vaatii viisi yhteen-/vähennysoperaatiota, yksi vähemmän kuin suora laskutoimitus. Lisäksi meidän ei tarvitse kertoa 4:llä, kun lasketaan p (−2).

Pistekerto

Toisin kuin polynomien p (•) ja q (•) kertolasku, laskettujen arvojen p ( a ) ja q ( a ) kertominen yksinkertaisesti pelkistyy kokonaislukujen kertolaskuksi, mikä on alkuperäisen ongelman yksinkertaisempi versio. Käytämme rekursiivisesti kertolaskumenettelyämme laskeaksemme jokaisen pistearvoparin. Käytännön toteutuksissa, kun operandit pienenevät, algoritmi pelkistyy kertolaskuksi sarakkeessa . Jos r on polynomien tulo, esimerkissämme on:

$r(0)$	=	$p(0)q(0)$	=	$56789012\times 54321098$	=	3084841486175176
$r(1)$	=	$p(1)q(1)$	=	$135813702\times 97639739$	=	13260814415903778
$r(-1)$	=	$p(-1)q(-1)$	=	$-21988766\times 11199987$	=	−246273893346042
$r(-2$ )	=	$p(-2)q(-2)$	=	$-100519632\times -31723594$	=	3188843994597408
$r(\infty )$	=	$p(\infty )q(\infty )$	=	$123456\times 98765$	=	12193131840.

Kuten näet, nämä arvot voivat olla negatiivisia. Riittävän suurille luvuille tämä on kallein askel, ainoa askel, joka ei riipu lineaarisesti koosta m ja n .

Interpolointi

Tämä on vaikein vaihe, pistelaskennan käänteinen vaihe - kun otetaan huomioon polynomien r (•) tulon d -pisteemme , meidän on laskettava sen kertoimet. Toisin sanoen meidän on ratkaistava matriisiyhtälö, jonka oikealla puolella on vektori:

{\begin{aligned}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\ end{matrix}}\right)&{}=\left({\begin{matrix}0^{0}&0^{1}&0^{2}&0^{3}&0^{4}\\1^ {0}&1^{1}&1^{2}&1^{3}&1^{4}\\(-1)^{0}&(-1)^{1}&(-1)^{2 }&(-1)^{3}&(-1)^{4}\\(-2)^{0}&(-2)^{1}&(-2)^{2}&(- 2)^{3}&(-2)^{4}\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{ 2}\\r_{3}\\r_{4}\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\ \1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\ \r_{4}\end{matrix}}\right).\end{aligned}}

Tämä matriisi rakennetaan samalla tavalla kuin pisteiden polynomiarvojen laskentavaiheessa, paitsi että matriisin koko on d × d . Voimme ratkaista tämän yhtälön Gaussin menetelmällä (poissulkemismenetelmä), mutta se tulee olemaan erittäin kallista. Sen sijaan käytämme sitä, että arvojen laskemiseen käytetyt pisteet valitaan erityisellä tavalla, jolloin käänteismatriisin laskeminen on helppoa (katso myös Vandermonde-matriisi ), ja sitten

{\begin{aligned}\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix }}\right)&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)^{ -1}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matriisi))\ right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{3}}&-1&{\tfrac {1} {6}}&-2\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&-1\\-{\tfrac {1}{2}}&{ \tfrac {1}{6}}&{\tfrac {1}{2}}&-{\tfrac {1}{6}}&2\\0&0&0&0&1\end{matrix}}\right)\left({\ alkaa{matriisi}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matriisi}}\oikea).\loppu{tasattu} }

Nyt jää vain laskea matriisin ja vektorin tulo. Vaikka matriisi sisältää murto-osia, saadut kertoimet ovat kokonaislukuja, joten laskelmia voidaan tehdä kokonaislukuaritmeettisesti lisäämällä, vähentämällä ja kertomalla/jakamalla pienillä vakioilla. Tässä päätehtävänä on löytää tehokas operaatiosarja, jonka avulla voidaan laskea matriisin ja vektorin tulo. Yhden tällaisen sekvenssin antoi Bodrato [6] Toom-3:lle, ja meidän esimerkissämme se on seuraava:

$r_{0}$	$\vasen nuoli$	$r(0)$	=	3084841486175176
$r_4$	$\vasen nuoli$	$r(\infty )$	=	12193131840
$r_3$	$\vasen nuoli$	$(r(-2)-r(1))/3$	=	(3188843994597408 − 13260814415903778)/3
			=	−3357323473768790
$r_{1}$	$\vasen nuoli$	$(r(1)-r(-1))/2$	=	$(13260814415903778-(-246273893346042))/2$
			=	6753544154624910
$r_{2}$	$\vasen nuoli$	$r(-1)-r(0)$	=	$-246273893346042-3084841486175176$
			=	−3331115379521218
$r_3$	$\vasen nuoli$	$(r_{2}-r_{3})/2+2r(\infty )$	=	$(-3331115379521218-(-3357323473768790))/2+2\times 12193131840$
			=	13128433387466
$r_{2}$	$\vasen nuoli$	$r_{2}+r_{1}-r_{4}$	=	−3331115379521218 + 6753544154624910 − 12193131840
			=	3422416581971852
$r_{1}$	$\vasen nuoli$	${\displaystyle r_{1}-r_{3))$	=	6753544154624910 − 13128433387466
			=	6740415721237444.

Tiedämme nyt polynomidemme tulon r :

{\begin{array}{rrr}r(x)=&{}&3084841486175176\\&+&6740415721237444x\\&+&3422416581971852x^{2}\\&+&3422416581971852x^{2}\\&+4}6&1&1&3&1&3\1&2}3 4}\end{array}}

Jos käyttäisimme muita tai valitsisimme muita pisteitä arvojen laskemiseen, matriisi ja sitten interpolointistrategia muuttuisivat, mutta tämä ei riipu syöttötiedoista, ja siksi algoritmi voidaan johdottaa mille tahansa parametrille. ${\displaystyle k_{m},k_{n))$

Uudelleenkokoonpano

Lopuksi lasketaan r(B), jotta saadaan lopputulos. Tämä tehdään suoraan, koska B on b :n potenssi, ja siksi kertominen B:n potenssilla on kokonaisluvun siirtoa kannan b numeroiden kokonaisluvulla . Esimerkissämme ja _ $b=10^{4}$ $B=b^{2}=10^{8}$

								3084	8414	8617	5176
						6740	4157	2123	7444
				3422	4165	8197	1852
		13	1284	3338	7466
+	121	9313	1840

	121	9326	3124	6761	1632	4937	6009	5208	5858	8617	5176

Tuloksena on 1234567890123456789012 ja 987654321987654321098 tulo.

Interpolaatiomatriisit eri k :n arvoille

Tässä esittelemme interpolointimatriisit useille eri pienille arvoille ja . $k_m$ $k_n$

Toom −1

Toom-1 ( ) vaatii laskutoimituksen yhdessä pisteessä, tässä valitaan 0. Algoritmi muuttuu sarakkeen kertolaskuksi identiteettiinterpolaatiomatriisilla: $k_{m}=k_{n}=1$

\left({\begin{matrix}1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1\end{matrix}}\right).

Toom-1.5

Toom-1.5 ( ) vaatii kaksi pistettä, tässä 0 ja valitaan . Interpolaatiomatriisi on tällöin yhtä suuri kuin identiteettimatriisi: $k_{m}=2,k_{n}=1$ $\infty$

\left({\begin{matrix}1&0\\0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0\\0&1\end{matrix}} \oikea).

Algoritmi myös rappeutuu kertolaskuksi sarakkeessa - yhden tekijän molemmat kertoimet kerrotaan toisen tekijän yhdellä kertoimella.

Toom-2

Toom-2 ( ) vaatii kolme pistettä, 0, 1 ja ne valitaan tästä . Algoritmi on sama kuin Karatsuba-algoritmi interpolointimatriisilla $k_{m}=2,k_{n}=2$ $\infty$

\left({\begin{matrix}1&0&0\\1&1&1\\0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0\\-1&1&-1 \\0&0&1\end{matrix}}\right).

Toom-2.5

Toom-2.5 ( vaatii 4 pistettä, tässä 0, 1, −1 ja valitaan . Algoritmilla on sitten interpolointimatriisi: $k_{m}=3,k_{n}=2)$ $\infty$

\left({\begin{matrix}1&0&0&0\\1&1&1&1\\1&-1&1&1&-1\\0&0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix} 1&0&0&0\\0&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&-1\\-1&{\tfrac {1}{2}}&{\tfrac {1} {2}}&0\\0&0&0&1\end{matrix}}\oikea).

Muistiinpanot

↑ 1 2 Knuth, 1997 , s. 296.
↑ Crandall, Pomerance, 2005 , s. 474.
↑ Crandall, Pomerance, 2005 , s. 536.
↑ Knuth, 1997 , s. 302.
↑ Positiiviset tulokset arkistoitu 6. tammikuuta 2013 Wayback Machinessa , Stephen A. Cook: On the Minimum Computation Time of Functions , luku III .
↑ 1 2 3 Bodrato, 2007 , s. 116-133.

Kirjallisuus

D. Knuth. Osa 4.3.3.A: Digitaaliset menetelmät // Tietokoneohjelmoinnin taito . – Kolmas painos. - Addison-Wesley, 1997. - T. 2. - S. 294.
Knut D.E. Ohjelmoinnin taito. Tuloksena olevat algoritmit. - 2019. - Osa 2. - ISBN 978-5-907144-15-6 .
R. Crandall, C. Pomerance. Osa 9.5.1: Karatsuba ja Toom–Cook -menetelmät // Alkuluvut – Laskennallinen näkökulma . - Toinen painos. - Springer, 2005. - S. 473 .
- Richard Crandall, Carl Pomerance. Yksinkertaiset numerot. Kryptografiset ja laskennalliset näkökohdat. - Moskova: Librocom, 2011. - ISBN 978-5-397-02060-2 .
M. Bodrato. Kohti optimaalista Toom–Cookin kertolaskua yksimuuttuja- ja monimuuttujapolynomeille ominaisuudessa 2 ja 0 // Äärillisten kenttien aritmetiikka . - Springer, 2007. - T. 4547. - (LNCS).

Linkit

Toom-Cook 3-suuntainen kertolasku GMP-dokumentaatiosta

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi