Shufin algoritmi

Schufin algoritmi on tehokas algoritmi [1] pistemäärän laskemiseen elliptisellä käyrällä äärellisen kentän yli . Algoritmilla on sovelluksia elliptisessä kryptografiassa , jossa on tärkeää tietää pisteiden lukumäärä, jotta voidaan arvioida diskreetin logaritmiongelman ratkaisemisen vaikeus pisteryhmässä elliptisellä käyrällä.

Algoritmin julkaisi vuonna 1985 René Chouf ja se oli teoreettinen läpimurto, koska se oli ensimmäinen deterministinen polynomiaikaalgoritmi pisteiden laskemiseen elliptisellä käyrällä . Ennen Schufin algoritmia lähestymistavat pisteiden laskemiseen elliptisillä käyrillä, kuten yksinkertainen pienten ja suurten askelten algoritmi , olivat suurimmaksi osaksi työlästä ja vaativat eksponentiaalista ajoaikaa.

Tämä artikkeli selittää Schufin lähestymistavan keskittyen algoritmin takana oleviin matemaattisiin ideoihin.

Johdanto

Antaa olla elliptinen käyrä , joka on määritelty äärellisen kentän yli , missä alkuluku ja kokonaisluku . Ominaisen kentän yli elliptinen käyrä voidaan antaa (lyhyesti) Weierstrassin yhtälöllä $E$ $\mathbb {F} _{q}$ $q=p^{n}$ $s$ $n\geq 1$ $\neq 2,3$

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

kanssa . Yli määritelty pistejoukko koostuu ratkaisuista, jotka täyttävät käyrän ja äärettömän pisteen yhtälön . Jos tässä joukossa käytetään elliptisten käyrien ryhmälakia, voidaan nähdä, että tämä joukko muodostaa Abelin ryhmän , jossa se toimii nollaelementtinä. Laskeaksemme pisteitä elliptisellä käyrällä, laskemme joukon kardinaalisuuden . Schuf-lähestymistapa käyttää Hassen elliptisen käyrän lausetta yhdessä kiinalaisen jäännöslauseen ja jakopolynomien kardinaalisuuden laskemiseen . ${\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})$

Hassen lause

Hassen lause sanoo, että jos on elliptinen käyrä äärellisen kentän päällä, niin se täyttää epäyhtälön ${\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)).

Tämä vahva tulos, jonka Hasse sai vuonna 1934, yksinkertaistaa tehtäväämme rajaamalla sen rajallisiin (vaikkakin suuriin) mahdollisuuksiin. Jos määritämme kuinka ja käytämme tätä tulosta, saadaan, että tehomoduulin laskenta , jossa , riittää laskemaan ja siten saamaan . Vaikka ei olekaan tehokasta tapaa laskea suoraan yleisiä lukuja, on mahdollista laskea pieni alkuluku varsin tehokkaasti. Valitsemme joukoksi erilaisia alkulukuja siten, että . Jos kiinalainen jäännöslause annetaan kaikille , voit laskea . $\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}}$

Alkuluvun laskemiseen käytämme Frobeniuksen endomorfismiteoriaa ja jakopolynomeja [ . Huomaa, että alkulukujen huomioiminen ei aiheuta ongelmia, koska voimme aina valita suuremman alkuluvun varmistaaksemme, että tulo on riittävän suuri. Joka tapauksessa tapaukseen käytetään useimmiten Schuf-algoritmia , koska on olemassa tehokkaampia, ns. -adic-algoritmeja kentille, joilla on pieni ominaisuus. $t{\pmod {l}}$ $l\neq p$ $\phi$ $l\neq p$ $q=p$ $s$

Frobenius endomorfismi

Kun elliptinen käyrä on määritelty yli , katsotaan pisteet yli , kentän algebrallinen sulkeutuminen . Eli sallimme pisteiden olla koordinaatteja . Frobeniuksen endomorfismi laajentaa elliptistä käyrää kartoituksella . $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})$

Tämä kartta on identtinen ja sitä voidaan laajentaa pisteellä äärettömään , mikä tekee siitä ryhmämorfismin itseensä . $E(\mathbb {F} _{q})$ $O$ $E({\bar {\mathbb {F} _{q))})$

Frobeniuksen endomorfismi täyttää potenssiin liittyvän toisen asteen yhtälön seuraavalla lauseella: $E(\mathbb {F} _{q})$

Lause: Kartoituksen antama Frobenius-endomorfismi täyttää ominaisyhtälön $\phi$

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

, missä

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

Sitten kaikki meillä on , jossa + tarkoittaa elliptisen käyrän lisäystä ja ja tarkoittaa pisteen skalaarituloa ja pisteen skalaarituloa [ 2 ] . $P=(x,y)\in E$ ${\näyttötyyli (x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})}$ ${\näyttötyyli q(x,y)}$ $t(x^{q},y^{q})$ $(x,y)$ $q$ ${\näyttötyyli (x^{q},y^{q})}$ $t$

Voit yrittää laskea nämä pisteet symbolisessa muodossa ja käyrän koordinaattirenkaan funktioina ja etsiä sitten yhtälön täyttävän arvon. Tutkinnot osoittautuvat kuitenkin erittäin suuriksi, eikä tällä lähestymistavalla ole käytännön arvoa. $(x^{q^{2}},y^{q^{2}})$ ${\näyttötyyli (x^{q},y^{q})}$ ${\näyttötyyli q(x,y)}$ $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)$ $E$ $t$

Schufin ideana oli tehdä tällaisia laskelmia rajoittuen tilaamaan pisteitä erilaisille pienille alkuluvuille . Korjaamme parittoman alkuluvun, siirrymme ratkaisemaan ongelman määrittämisessä , määriteltynä , tietylle alkuluvulle . Jos piste on -torsion aliryhmässä , Sitten , Jossa on ainoa kokonaisluku sellainen, että ja . Huomaa, että ja että mille tahansa kokonaisluvulle meillä on . Siten sillä on sama järjestys kuin . Sitten , joka kuuluu , meillä on myös jos . Näin ollen olemme vähentäneet ongelmamme yhtälön ratkaisemiseksi $l$ $l$ $l$ ${\näyttötyyli 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)$ ${\näyttötyyli \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}),

missä ja välissä . ${\näyttötyyli {\bar {t))}$ ${\bar {q))$ $[-(l-1)/2,(l-1)/2]$

Laskelmat modulo

Jakopolynomi , jonka indeksi on l , on polynomi siten, että sen juuret ovat täsmälleen kertaluvun l pisteiden x - koordinaatit. Tällöin laskennan rajoittaminenl -vääntöpisteisiin tarkoittaa näiden lausekkeiden laskemista koordinaattirenkaan E ja l :nnen jakopolynomin moduulin. Eli työskentelemme. Tämä tarkoittaa erityisesti sitä, että X :n ja Y :nei ylitä 1:tä muuttujan y suhteen ja muuttujanx suhteen . $(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)$ $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$ ${\näyttötyyli (X(x,y),Y(x,y)):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}( x,y)}$ $(l^{2}-3)/2$

Pistetulo voidaan tehdä tupla-ja-lisää- menetelmällä tai jakopolynomilla. Toinen lähestymistapa antaa: ${\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}}}\oikea)

missä on n :s jakopolynomi . Huomaa, että se on vain x :n funktio, merkitään tämä funktio : lla . $\psi_{{n}}$ $y_{\bar {q}}/y$ $\theta (x)$

Meidän on jaettava ongelma kahteen tapaukseen: tapaukseen, jossa , ja tapaukseen, jossa . $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)$

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

Käyttämällä ryhmän lisäyskaavaa saamme: $E(\mathbb {F} _{q})$

X(x,y)=\left({\frac {y^{q^{2}}-y_{\bar {q}}}{x^{q^{2}}-x_{\ palkki {q}}}}\oikea)^{2}-x^{q^{2}}-x_{\bar {q}}.

Huomaa, että tämä laskenta on mahdotonta, jos epäyhtälö-oletus epäonnistuu.

Voimme nyt kaventaa x -koordinaatin valintaa kahdelle mahdollisuudelle, nimittäin positiiviselle ja negatiiviselle tapaukselle. Y -koordinaatin avulla määritämme kumpi näistä kahdesta tapauksesta tapahtuu. ${\näyttötyyli {\bar {t))}$

Osoitamme ensin, että X on vain x :n funktio . Harkitse . Koska se on parillinen , korvaamalla lausekkeen kirjoitamme uudelleen muotoon $(y^{q^{2}}-y_{\bar {q)))^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/v)^{2}$ $q^{2}-1$ $y^{2}$ $x^{3}+Ax+B$

{\näyttötyyli (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x)) }

ja meillä on

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

Nyt, jos , niin tasa-arvo on totta $X\equiv x_{\bar {t}}^{q}{\bmod {\psi }}_{l}(x)$ ${\bar {t}}\in [0,(l-1)/2]$ ${\näyttötyyli {\bar {t))}$

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

kaikille P l -vääntöpisteille.

Kuten aiemmin mainittiin, käyttämällä Y ja , voimme nyt määrittää, kumpi kahdesta arvosta ( tai ) toimii. Se antaa merkityksen . Schoofin algoritmi muistaa muuttujan arvot jokaiselle tarkastelulle alkuluvulle l . $y_{\bar {t}}^{q}$ ${\näyttötyyli {\bar {t))}$ ${\näyttötyyli {\bar {t))}$ $-{\bar {t))$ $t\equiv {\bar {t}}{\pmod {l}}$ ${\bar {t}}{\pmod {l}}$ $t_{l}$

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

Oletetaan, että . Koska l on pariton alkuluku, se on mahdotonta , ja siksi . Ominaisuusyhtälöstä seuraa, että , ja siksi se . Tästä seuraa, että q on neliömoduuli l . Anna . Laske sisään ja tarkista onko . Jos on, niin on y-koordinaatista riippuen. $(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)$ ${\näyttötyyli t_{l))$ $\pm 2w{\pmod {l))$

Jos q ei ole neliömodulo l , tai jos yhtäläisyys epäonnistuu joillekin w ja , oletuksemme on väärä, joten . Ominaisuusyhtälö antaa . $-w$ $(x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=-{\bar {q}}(x,y)$ $t_{l}=0$

Lisätapaus $l=2$

Muista, että alkuperäisissä sopimuksissamme ei oteta huomioon tapausta . Koska oletimme, että q on pariton, ja erityisesti jos ja vain jos sillä on 2:n kertaluvun elementti. Ryhmän summauksen määritelmän mukaan minkä tahansa kertaluvun 2 elementin tulee olla muotoa . Siten jos ja vain jos polynomin juuri on , jos ja vain jos gcd . $l=2$ $q+1-t\equiv t{\pmod {2}}$ $t_{2}\equiv 0{\pmod {2))$ $E(\mathbb {F} _{q})$ ${\näyttötyyli (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$

Algoritmi

Syöte: 1. Elliptinen käyrä .

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

2. Kokonaisluku q äärelliselle kenttään , jossa on .

F_q

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

Johtopäätös:E - pisteiden määrä yli .

F_q

Valitsemme joukon parittomia alkulukuja S , jotka eivät sisällä p :tä siten, että Hyväksymme jos gcd , muuten hyväksymme . Laskemme jakopolynomin .

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))

Kaikki alla olevan silmukan laskutoimitukset suoritetaan renkaassa Sillä suoritamme : Antaa olla ainoa kokonaisluku sellainen, että ja . Laskemme ja . _ Jos sitten Laske . tekemiseen : jos sitten jos sitten ; _ muuten . muuten, jos q on neliömoduuli l , laske w ja laske jos sitten toisin jos sitten toisin Laske kiinalaisen jäännöslauseen avulla t modulo N yhtälöstä jossa .

\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

{\näyttötyyli (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}=2w

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

Me johdamme .

q+1-t

Vaikeus

Useimmissa laskelmissa lasketaan ja kullekin alkuluvulle eli lasketaan , , , jokaiselle alkuluvulle . Laskelmat sisältävät eksponentioimisen renkaassa ja vaativat kertolaskuja. Koska aste on , jokainen renkaan alkio on astepolynomi . Alkulukulauseen mukaan on noin alkulukuja koon , joka antaa for , ja saamme . Siten jokainen kertolasku renkaassa vaatii kertolaskuja in , mikä puolestaan vaatii bittikohtaisia operaatioita. Yhteensä kunkin alkuluvun bittioperaatioiden määrä on . Olettaen, että tämä laskenta on tehtävä jokaiselle alkuluvulle, Schufin algoritmin kokonaismonimutkaisuus tulee . Nopeiden polynomioperaatioiden ja kokonaislukuaritmetiikka lyhentää tämän ajan arvoon . ${\näyttötyyli \phi (P)}$ $\phi ^{2}(P)$ $l$ ${\näyttötyyli 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)$

Parannuksia Schuf-algoritmiin

1990-luvulla Noam Elkis ja sitten A. O. L. Atkin keksivät parannuksia Schufin perusalgoritmiin rajoittamalla alkulukujoukon tietyntyyppisiin lukuihin. Nämä luvut tunnettiin vastaavasti Elkiksen ja Atkinin alkulukuina. Alkulukua kutsutaan Elkis-alkuluvuksi, jos karakteristinen yhtälö on hajotettava yli ja Atkin-alkuluvut ovat alkulukuja, jotka eivät ole Elkis-alkulukuja. Atkin osoitti kuinka yhdistää Atkin-alkuluvuista saatua tietoa Elkis-alkuluvuista saatuun tietoon tehokkaan algoritmin saamiseksi, jota kutsuttiin " Schoof-Elkis-Atkin-algoritmiksi . Ensimmäinen tehtävä on määrittää, onko tietty alkuluku Elkis- vai Atkin-alkuluku. Tämän saavuttamiseksi käytämme modulaarisia polynomeja, jotka syntyvät tutkittaessa modulaarisia muotoja ja tulkittaessa elliptisiä käyriä kompleksilukukentän hilaksi. Kun olemme määrittäneet, mikä tapaus meillä on, sen sijaan, että käyttäisimme jakopolynomeja , voimme työskennellä polynomien kanssa, joilla on pienempi aste kuin jakopolynomeilla: sijasta . Tehokkaan toteutuksen varmistamiseksi käytetään todennäköisyyspohjaisia juurihakualgoritmeja, mikä tekee algoritmista Las Vegasin algoritmin deterministisen algoritmin sijaan. Heuristisella oletuksella, että noin puolet alkuluvuista, jotka ovat pienempiä tai yhtä suuria kuin ovat Elkis-alkulukuja, saadaan algoritmi, joka on tehokkaampi kuin Schoofin algoritmi, ja tämän algoritmin odotettu ajoaika on , jos käytetään tavallista aritmetiikkaa, ja , jos käytetään nopea aritmetiikka. On huomattava, että tämä heuristinen oletus pätee useimpiin elliptisiin käyriin, mutta sitä ei tunneta yleisessä tapauksessa, vaikka yleistetty Riemannin hypoteesi olisikin totta . $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)$

Toteutukset

Mike Scott on toteuttanut osan algoritmeista C++ :ssa ja ne ovat saatavilla lähdekoodina . Toteutus on täysin ilmainen (ei ehtoja, ei rajoituksia), mutta käyttää MIRACL- kirjastoa , jota jaetaan AGPLv3 -lisenssillä .

Schufin algoritmi toteutuksella yksinkertaisella . $E(\mathbb {F} _{p})$ $s$
Schufin algoritmi toteutuksella . $E(\mathbb {F} _{2^{m)))$

Katso myös

Elliptinen kryptografia
Pisteiden laskeminen elliptisellä käyrällä
jakopolynomit
Frobeniuksen endomorfismi

Muistiinpanot

↑ Tosin ECDSA :n artikkelissa sanotaan seuraavaa: Skoofin algoritmi on käytännössä varsin tehoton p -arvoille , jotka ovat todella kiinnostavia, eli p > 2 160 .
↑ Pistettä mP, joka on yhtä suuri kuin pisteen P m-kertainen summa elliptisen käyrän additiivinen pisteryhmässä, kutsutaan pisteen ja luvun m skalaarituloksi , ja itse pisteitä mP kutsutaan skalaarikerroiksi. kohta ( Rybolovlev 2004 ). Tiborgin kirjassa ( van Tilborg 2006 ) samaa käsitettä kutsutaan skalaarikertoimeksi.

Kirjallisuus

R. Schoof. Elliptiset käyrät äärellisten kenttien yli ja neliöjuurten laskeminen mod p // Math. Comp.. - 1985. - T. 44 , no. 170 . — S. 483–494 .
R. Schoof. Pisteiden laskenta elliptisillä käyrillä äärellisten kenttien yli // J. Theor. Nombres Bordeaux. - 1995. - Numero. 7 . — S. 219–254 .
Gregg Musiker. Schoofin algoritmi pisteiden laskemiseksi $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. - (Pro gradu).
Andreas Enge. Elliptiset käyrät ja niiden sovellukset kryptografiaan: Johdanto. - Dordrecht: Kluwer Academic Publishers, 1999.
Lawrence C. Washington. Elliptiset käyrät: lukuteoria ja kryptografia. - New York: Chapman & Hall / CRC, 2003. - V. 50. - (Diskreetti matematiikka ja sen sovellukset). — ISBN 978-1-4200-7146-7 .
Neal Koblitz. Lukuteorian ja kryptografian kurssi. - Toinen painos. - Springer-Verlag, 1994. - V. 114. - (Matematiikan tutkinnon tekstit). — ISBN 0-387-94293-9 .
H. C. A. van Tilborg. Kryptologian perusteet. - Moskova: Mir, 2006. - ISBN 5-03-003639-3 UDC 519.6.
Dmitri Rybolovlev. Elliptisen käyrän salaustekniikan käyttäminen WEB Securityssa . – 2004.

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