Shuf algoritmusa

A Schuf -algoritmus egy hatékony algoritmus [1] egy véges mező feletti elliptikus görbén lévő pontok számának megszámlálására . Az algoritmusnak vannak alkalmazásai az elliptikus kriptográfiában , ahol fontos tudni a pontok számát, hogy megítélhessük egy diszkrét logaritmus probléma megoldásának nehézségét egy elliptikus görbe pontcsoportján .

Az algoritmust 1985-ben publikálta René Chouf , és ez elméleti áttörést jelentett, mivel ez volt az első determinisztikus polinomiális időalgoritmus az elliptikus görbén lévő pontok számlálására . A Schuf-algoritmus előtt az elliptikus görbék pontjainak megszámlálásának megközelítései, mint például a kis és nagy lépések egyszerű algoritmusa , többnyire munkaigényesek voltak, és exponenciális futási időt igényeltek.

Ez a cikk elmagyarázza Schuf megközelítését, az algoritmus mögött meghúzódó matematikai ötletekre összpontosítva.

Bevezetés

Legyen egy véges mező felett meghatározott elliptikus görbe , ahol prím és egész szám . Egy karakterisztikus mező felett egy elliptikus görbe adható meg (röviden) a Weierstrass-egyenlettel $E$ $\mathbb {F} _{q}$ $q=p^{n}$ $p$ $n\geq 1$ $\neq 2,3$

y^{2}=x^{3}+Ax+B

-val . A pontok halmaza a görbe és a végtelenben lévő pont egyenletét kielégítő megoldásokból áll . Ha a csoporttörvényt használjuk az elliptikus görbékre ezen a halmazon, akkor láthatjuk, hogy ez a halmaz egy Abel-csoportot alkot , amelyben nulla elemként működik. Az elliptikus görbe pontjainak megszámlálásához kiszámoljuk a halmaz számosságát . A Schuf-megközelítés Hasse-féle elliptikus görbe tételét , valamint a kínai maradéktételt és az osztáspolinomokat használja a kardinalitás kiszámításához . ${\displaystyle A,B\in \mathbb {F} _{q))$ $\mathbb {F} _{q}$ ${\displaystyle (a,b)\in \mathbb {F} _{q}^{2))$ $O$ $E(\mathbb {F} _{q})$ $O$ $E(\mathbb {F} _{q})$ $\sharp E(\mathbb {F} _{q})$

Hasse tétele

Hasse tétele kimondja, hogy ha egy elliptikus görbe egy véges mező felett, akkor teljesül az egyenlőtlenség ${\displaystyle E/\mathbb {F} _{q))$ $\mathbb {F} _{q}$ $\sharp E(\mathbb {F} _{q})$

\mid q+1-\sharp E(\mathbb {F} _{q})\mid \leq 2{\sqrt {q)).

Ez az erős eredmény, amelyet Hasse 1934-ben ért el, leegyszerűsíti a feladatunkat azáltal , hogy a lehetőségek véges (bár nagy) halmazára leszűkíti. Ha meghatározzuk , hogyan és ezt az eredményt használjuk, akkor azt kapjuk, hogy a modulo teljesítmény kiszámítása , ahol , elegendő a kiszámításához , és így megkapjuk . Bár nincs hatékony módszer az általános számok közvetlen kiszámítására , egy kis prímszámra meglehetősen hatékonyan lehet számítani. Különböző prímszámok halmazaként választunk úgy, hogy . Ha mindenre adott , a kínai maradéktétel lehetővé teszi a számítást . $\sharp E(\mathbb {F} _{q})$ $t$ $q+1-\sharp E(\mathbb {F} _{q})$ $t$ $N$ $N>4{\sqrt {q))$ $t$ $\sharp E(\mathbb {F} _{q})$ $t{\pmod {N}}$ $N$ $t{\pmod {l}}$ $l$ $S=\{l_{1},l_{2},...,l_{r))\}$ $\prod l_{i}=N>4{\sqrt {q))$ ${\displaystyle t{\pmod {l_{i))))$ $l_{i}\in S$ $t{\pmod {N}}$

A prím kiszámításához a Frobenius endomorfizmus elméletét és az osztáspolinomokat használjuk . Megjegyzendő, hogy a prímszámok figyelembevétele nem okoz problémát, hiszen mindig választhatunk nagyobb prímszámot, hogy a szorzat elég nagy legyen. Mindenesetre a Schuf algoritmust használják leggyakrabban az esetre , mivel vannak hatékonyabb, úgynevezett -adic algoritmusok a kis karakterisztikájú mezőkre. $t{\pmod {l}}$ $l\neq p$ $\phi$ $l\neq p$ $q=p$ $p$

Frobenius endomorfizmus

Ha adott egy felett definiált elliptikus görbe , akkor a feletti pontokat tekintjük a mező algebrai lezárásának . Vagyis megengedjük, hogy a pontok koordinátái legyenek -ben . A Frobenius-endomorfizmus egy elliptikus görbét kiterjeszt egy leképezéssel . $E$ $\mathbb {F} _{q}$ $E$ ${\bar {\mathbb {F} }}_{q}$ $\mathbb {F} _{q}$ ${\bar {\mathbb {F} }}_{q}$ ${\bar {\mathbb {F} }}_{q}$ $\mathbb {F} _{q}$ $\phi :(x,y)\mapsto (x^{q},y^{q})$

Ez a térkép megegyezik a ponttal, és egy ponttal a végtelenig kiterjeszthető , így csoportmorfizmussá válik önmagától . $E(\mathbb {F} _{q})$ $O$ $E({\bar {\mathbb {F} _{q))})$

A Frobenius-endomorfizmus a következő tétellel teljesíti a hatványra vonatkozó másodfokú egyenletet : $E(\mathbb {F} _{q})$

Tétel: A leképezés által adott Frobenius endomorfizmus kielégíti a karakterisztikus egyenletet $\phi$

\phi ^{2}-t\phi +q=0

, ahol

t=q+1-\sharp E(\mathbb {F} _{q})

Ekkor mindenre , ahol a + egy elliptikus görbe összeadását jelenti, és a és egy -on lévő pont és egy pont skaláris szorzatát jelenti [2] . $P=(x,y)\in E$ $(x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})$ $q(x,y)$ $t(x^{q},y^{q})$ $(x,y)$ $q$ $(x^{q},y^{q})$ $t$

Megpróbálhatja ezeket a pontokat szimbolikus formában és a görbén lévő koordinátagyűrű függvényeiként kiszámítani , majd keresni egy értéket , amely kielégíti az egyenletet. A fokozatok azonban nagyon nagynak bizonyulnak, és ennek a megközelítésnek nincs gyakorlati értéke. $(x^{q^{2}},y^{q^{2}})$ $(x^{q},y^{q})$ $q(x,y)$ $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)$ $E$ $t$

Schuf ötlete az volt, hogy ilyen számításokat hajtson végre, korlátozva magát a különböző kis prímszámok pontjaira . Egy páratlan prímszám rögzítése után továbblépünk annak a feladatnak a megoldásához , hogy egy adott prímhez definiáljuk a -t . Ha a pont a -torziós alcsoportban van , akkor , ahol az egyetlen olyan egész szám, amelyre és . Jegyezzük meg ezt és azt minden olyan egész számra , amelyre . Így a sorrendje megegyezik a . Ekkor a -hoz tartozó -hoz van még if . Következésképpen a problémánkat az egyenlet megoldására redukáltuk $l$ $l$ $l$ ${\displaystyle t_{l))$ $t{\pmod {l}}$ $l\neq 2,p$ $(x, y)$ $l$ ${\displaystyle E[l]=\{P\in E({\bar {\mathbb {F} _{q))})\mid lP=O\))$ $qP={\bar {q}}P$ ${\bar {q))$ $q\equiv {\bar {q}}{\pmod {l}}$ $\mid {\bar {q}}\mid </l/2$ $\phi (O)=O$ $r$ $r\phi (P)=\phi (rP)$ $\phi (P)$ $P$ $(x, y)$ $E[l]$ $t(x^{q},y^{q})={\bar {t))(x^{q},y^{q})$ $t\equiv {\bar {t}}{\pmod {l}}$

(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)\equiv {\bar {t}}(x^{ q},y^{q}),

hol és fekszik az intervallumban . ${\bar {t))$ ${\bar {q))$ $[-(l-1)/2,(l-1)/2]$

Számítások modulo

Az l indexű osztáspolinom olyan polinom, amelynek gyökei pontosan az l rendű pontok x koordinátái. Ekkor a számításnakaz l -torziós pontokra való korlátozása ezeknek a kifejezéseknek az E koordinátagyűrű és az l -edik osztású polinom modulusának függvényében történő kiszámítását jelenti. Vagyis ben dolgozunk. Ez különösen azt jelenti, hogy az X és Y mértékenem haladja meg az 1-et az y változóhoz ésaz x változóhoz képest . $(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)$ $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$ ${\megjelenítési stílus (X(x,y),Y(x,y)):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}( x,y)}$ $(l^{2}-3)/2$

A pontszorzat elkészíthető a dupla-összeadás módszerrel , vagy a th osztásos polinommal. A második megközelítés a következőket adja: ${\bar {q}}(x,y)$ ${\bar {q))$

{\bar {q}}(x,y)=(x_{\bar {q}},y_{\bar {q}})=\left(x-{\frac {\psi _{{ \bar {q}}-1}\psi _({\bar {q}}+1}}{\psi _{\bar {q}}^{2}}},{\frac {\psi _{ 2{\bar {q}}}}{2\psi _{\bar {q}}^{4}}}\jobbra)

ahol az n- edik osztású polinom. Vegye figyelembe, hogy ez csak x függvénye, jelöljük ezt a függvényt -vel . $\psi_{{n}}$ $y_{\bar {q}}/y$ $\az adó)$

A problémát két esetre kell felosztanunk: arra az esetre, amelyben , és arra az esetre, amelyben . $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)$

1. eset: $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$

A csoport összeadási képletével a következőt kapjuk: $E(\mathbb {F} _{q})$

X(x,y)=\left({\frac {y^{q^{2}}-y_{\bar {q}}}{x^{q^{2}}-x_{\ sáv {q}}}}\jobbra)^{2}-x^{q^{2}}-x_{\sáv {q}}.

Megjegyzendő, hogy ez a számítás lehetetlen, ha az egyenlőtlenség feltételezése meghiúsul.

Az x -koordináta választását most két lehetőségre szűkíthetjük, nevezetesen a pozitív és a negatív esetekre. Az y koordináta segítségével meghatározzuk, hogy a két eset közül melyik történik. ${\bar {t))$

Először megmutatjuk, hogy X csak x függvénye . Fontolja meg . Mivel páros, a -re cserélve a kifejezést átírjuk így $(y^{q^{2}}-y_{\bar {q)))^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/é)^{2}$ $q^{2}-1$ $y^{2}$ $x^{3}+Ax+B$

(x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x))

és van

X(x)\equiv (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}- \theta (x)){\bmod {\psi }}_{l}(x).

Nos, ha -ra , akkor az egyenlőség erre igaz $X\equiv x_{\bar {t}}^{q}{\bmod {\psi }}_{l}(x)$ ${\bar {t}}\in [0,(l-1)/2]$ ${\bar {t))$

\phi ^{2}(P)\mp {\bar {t))\phi (P)+{\bar {q))P=O

a P l -torzió minden pontjára.

Ahogy korábban említettük, az Y és a segítségével most már meghatározhatjuk, hogy a két érték ( vagy ) közül melyik működik. Értelmet ad . A Schoof-algoritmus megjegyzi a változó értékeit minden egyes figyelembe vett l prímhez . $y_{\bar {t}}^{q}$ ${\bar {t))$ ${\bar {t))$ $-{\bar {t))$ $t\equiv {\bar {t}}{\pmod {l}}$ ${\bar {t}}{\pmod {l}}$ $t_{l}$

2. eset: $(x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)$

Tegyük fel, hogy . Mivel l páratlan prímszám, lehetetlen , és ezért . A karakterisztikus egyenletből az következik, hogy , tehát az . Ebből következik, hogy q négyzetmodulo l . Hadd . Számítsa ki és ellenőrizze, hogy . Ha igen, akkor az y koordinátától függően. $(x^{q^{2}},y^{q^{2}})={\bar {q}}(x,y)$ ${\bar {q}}(x,y)=-{\bar {q}}(x,y)$ ${\bar {t}}\neq 0$ ${\bar {t}}\phi (P)=2{\bar {q}}P$ ${\bar {t}}^{2}{\bar {q}}\equiv (2q)^{2}{\pmod {l}}$ $q\equiv w^{2}{\pmod {l))$ $w\phi(x,y)$ $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$ ${\bar {q}}(x,y)=w\phi (x,y)$ ${\displaystyle t_{l))$ $\pm 2w{\pmod {l}}$

Ha q nem négyzetmodulo l , vagy ha az egyenlőség meghiúsul valamilyen w és esetén, akkor a feltevésünk hibás, tehát . A karakterisztikus egyenlet ad . $-w$ $(x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=-{\bar {q}}(x,y)$ $t_{l}=0$

További eset $l=2$

Ne feledje, eredeti megállapodásaink nem veszik figyelembe az esetet . Mivel feltételeztük, hogy q páratlan, és különösen akkor és csak akkor, ha van 2. rendű eleme. Az összeadás definíciója szerint egy csoportban minden 2. rendű elemnek formájúnak kell lennie . Így akkor és csak akkor, ha a polinomnak van gyöke -ben , akkor és csak akkor, ha gcd . $l=2$ $q+1-t\equiv t{\pmod {2))$ $t_{2}\equiv 0{\pmod {2))$ $E(\mathbb {F} _{q})$ $(x_{0},0)$ $t_{2}\equiv 0{\pmod {2))$ $x^{3}+Ax+B$ $\mathbb {F} _{q}$ $(x^{q}-x,x^{3}+Ax+B)\neq 1$

Algoritmus

Bemenet: 1. Elliptikus görbe .

E=y^{2}-x^{3}-Ax-B

2. Egy q egész szám egy véges mezőhöz -val .

F_q

q=p^{b},b\geq 1

Következtetés:A feletti E pontok száma .

F_q

Kiválasztjuk a páratlan S prímek halmazát , amelyek nem tartalmazzák p -t, így elfogadjuk , ha gcd , ellenkező esetben elfogadjuk . Kiszámoljuk az osztáspolinomot .

N=\prod _{l\in S}l>4{\sqrt {q)).

t_{2}=0

(x^{q}-x,x^{3}+Ax+B)\neq 1

t_{2}=1

{\displaystyle \psi _{l))

Az alábbi ciklusban szereplő összes számítást a gyűrűben hajtjuk végre. Mert végrehajtjuk : Legyen az egyetlen olyan egész szám , amelyre és . Kiszámoljuk , és . Ha akkor Compute . for doing : if then if then ; különben . egyébként, ha q egy négyzet modulo l , akkor számítsa ki w -t a számítással , ha akkor különben, ha akkor másképp Használja a kínai maradéktételt a t modulo N kiszámításához az egyenletből, ahol .

\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).

l\in S

{\bar {q))

q\equiv {\bar {q}}{\pmod {l}}

\mid {\bar {q}}\mid </l/2

(x^{q},y^{q})

(x^{q^{2}},y^{q^{2}})

(x_{\bar {q)),y_{\bar {q)))

x^{q^{2}}\neq x_{\bar {q}}

(X,Y)

1\leq {\bar {t}}\leq (l-1)/2

X=x_{\bar {t}}^{q}

Y=y_{\bar {t}}^{q}

t_{l}={\bar {t))

t_{l}=-{\bar {t))

q\equiv w^{2}{\pmod {l))

w(x^{q},y^{q})

w(x^{q},y^{q})=(x^{q^{2}},y^{q^{2}})

t_{l}=2h

w(x^{q},y^{q})=(x^{q^{2}},-y^{q^{2}})

t_{l}=-2w

t_{l}=0

t_{l}=0

x\equiv t_{l}{\pmod {l))

l\in S

származtatjuk .

q+1-t

Nehézség

A legtöbb számítás magában foglalja a kiszámítását és minden prímszámhoz , azaz , , , minden prímszámhoz való kiszámítását . A számítások hatványozást tartalmaznak a gyűrűben , és szorzást igényelnek . Mivel a fokszám , a gyűrű minden eleme fokszámú polinom . A prímszámtétel szerint körülbelül méretű prímek vannak , ami megadja a -t , és megkapjuk . Így a gyűrűben minden szorzáshoz szorzásra van szükség -ben , ami viszont bitenkénti műveleteket igényel. Összességében az egyes prímszámokhoz tartozó bitműveletek száma . Feltételezve, hogy ezt a számítást minden prímre el kell végezni , a Schuf-algoritmus teljes összetettsége . A gyors polinomiális műveletek és az egész számok használata ezt az időt csökkenti . $\phi (P)$ $\phi ^{2}(P)$ $l$ ${\displaystyle x^{q))$ ${\displaystyle y^{q))$ $x^{q^{2))$ $y^{q^{2))$ $l$ $R=\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$ $O(\log q)$ ${\displaystyle \psi _{l))$ ${\frac {l^{2}-1}{2}}$ $O(l^{2})$ $O(\log q)$ $O(\log q)$ $l$ $O(\log q)$ $O(l^{2})=O(\log ^{2}q)$ $R$ $O(\log ^{4}q)$ $\mathbb {F} _{q}$ $O(\log ^{2}q)$ $l$ $O(\log ^{7}q)$ $O(\log q)$ $O(\log ^{8}q)$ ${\tilde {O}}(\log ^{5}q)$

A Schuf-algoritmus továbbfejlesztései

Az 1990-es években Noam Elkis , majd A. O. L. Atkin az alapvető Schuf-algoritmus továbbfejlesztésével állt elő azáltal, hogy a prímszámokat bizonyos típusú számokra korlátozta. Ezek a számok Elkis-prímként, illetve Atkin-prímként váltak ismertté. Egy prímszámot Elkis-prímnek nevezünk, ha a karakterisztikus egyenlőség felbontható felett , és az Atkin-prímek olyan prímek, amelyek nem Elkis-prímek. Atkin megmutatta, hogyan lehet kombinálni az Atkin-prímekből nyert információkat az Elkis-prímekből nyert információkkal, hogy hatékony algoritmust kapjunk, amelyet " Schoof-Elkis-Atkin Algoritmusnak neveztek . Az első feladat annak meghatározása, hogy egy adott prím Elkis- vagy Atkin-prím-e. Ennek eléréséhez moduláris polinomokat használunk, amelyek a moduláris formák tanulmányozása során keletkeznek, és a komplex számok mezője feletti elliptikus görbéket rácsként értelmezzük . Miután meghatároztuk, hogy melyik eset áll rendelkezésünkre, az osztási polinomok helyett dolgozhatunk olyan polinomokkal, amelyeknek alacsonyabb fokuk van, mint az osztási polinomoknak: helyett . A hatékony megvalósítás érdekében valószínűségi gyökérkereső algoritmusokat használnak, amelyek az algoritmust Las Vegas -i algoritmussá teszik determinisztikus algoritmus helyett. Abban a heurisztikus feltevésben, hogy a kisebb vagy egyenlő prímek körülbelül fele Elkis-prím, ez egy olyan algoritmust eredményez, amely hatékonyabb, mint a Schoof-féle algoritmus, és ennek az algoritmusnak a várható futási ideje közönséges aritmetika esetén , és . gyors aritmetika. Meg kell jegyezni, hogy ez a heurisztikus feltevés igaz a legtöbb elliptikus görbére, de általános esetben nem ismert, még akkor sem, ha az általánosított Riemann-hipotézis igaz . $S=\{l_{1},\ldots ,l_{s}\}$ $l$ $\phi ^{2}-t\phi +q=0$ ${\displaystyle \mathbb {F} _{l))$ $O(l)$ $O(l^{2})$ $O(\log q)$ $O(\log ^{6}q)$ ${\tilde {O}}(\log ^{4}q)$

Megvalósítások

Az algoritmusok egy részét Mike Scott C++ nyelven implementálta, és forráskódban is elérhetők . A megvalósítás teljesen ingyenes (feltételek, korlátozások nélkül), de a MIRACL könyvtárat használja , amely az AGPLv3 licenc alatt kerül terjesztésre .

Schuf algoritmusa az egyszerű megvalósítással . $E(\mathbb {F} _{p})$ $p$
Schuf algoritmusa a következőre való megvalósítással . $E(\mathbb {F} _{2^{m)))$

Lásd még

Elliptikus kriptográfia
Pontok számolása elliptikus görbén
osztáspolinomok
Frobenius endomorfizmus

Jegyzetek

↑ Bár az ECDSA cikke a következőket mondja: A Skoof-algoritmus a gyakorlatban meglehetősen hatástalan az igazán érdekes p értékek esetében, azaz p > 2 160 .
↑ Az mP pontot, amely megegyezik a P pont m-szeres összeadásával egy elliptikus görbe pontcsoportjában, a pont és az m szám skaláris szorzatának nevezzük , magukat az mP pontokat pedig a pont skaláris többszörösének. a lényeg ( Rybolovlev 2004 ). Tiborg könyvében ( van Tilborg 2006 ) ugyanezt a fogalmat skaláris többszörösnek nevezik.

Irodalom

R. Schoof. Elliptikus görbék véges mezők felett és a négyzetgyökök számítása mod p // Math. Összeg.. - 1985. - T. 44 , sz. 170 . – S. 483–494 .
R. Schoof. Pontok számolása véges mezők feletti elliptikus görbéken // J. Theor. Nombres Bordeaux. - 1995. - Kiadás. 7 . – S. 219–254 .
Gregg Musiker. Schoof pontszámláló algoritmusa a $E(\mathbb {F} _{q})$ . – 2005.
V. Müller. Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern . - Saarbrücken: Universität des Saarlandes, 1991. - (Mesterdiploma).
Andreas Enge. Elliptikus görbék és alkalmazásaik a kriptográfiában: Bevezetés. - Dordrecht: Kluwer Academic Publishers, 1999.
Lawrence C. Washington. Elliptikus görbék: számelmélet és kriptográfia. - New York: Chapman & Hall / CRC, 2003. - V. 50. - (Diszkrét matematika és alkalmazásai). — ISBN 978-1-4200-7146-7 .
Neal Koblitz. Számelmélet és kriptográfia tanfolyam. - Második kiadás. - Springer-Verlag, 1994. - V. 114. - (Matematika érettségi szövegek). — ISBN 0-387-94293-9 .
H. C. A. van Tilborg. A kriptológia alapjai. - Moszkva: Mir, 2006. - ISBN 5-03-003639-3 UDC 519.6.
Dmitrij Rybolovlev. Elliptikus görbe kriptográfia használata a webes biztonságban . – 2004.

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus