Modulo-käänteisnumero

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

Käänteinen modulo an kokonaisluku a on kokonaisluku x siten, että tulo ax on kongruentti 1 modulo m :n kanssa [1] . Tavallisessa modulaarisessa aritmeettisessa merkinnässä tämä vastaavuus kirjoitetaan seuraavasti:

ax\equiv 1{\pmod {m)),

joka on lyhennetty tapa sanoa, että m jakaa (ilman jäännösjäännöstä) arvon ax − 1 , tai toisin sanoen, jäännös, kun ax jaetaan kokonaisluvulla m , on 1. Jos a :lla on käänteismoduuli m , sitten tälle ekvivalenssille on ääretön määrä ratkaisuja, jotka muodostavat tämän moduulin jäännösluokan . Lisäksi millä tahansa kokonaisluvulla, joka on ekvivalentti a :lla (eli ekvivalenssiluokasta a ), on mikä tahansa ekvivalenssiluokan x elementti käänteisenä. Muistimerkin käyttö $\overline {w}$ ekvivalenssiluokalle, joka sisältää , yllä oleva lauseke voidaan kirjoittaa seuraavasti: käänteiselementti modulo ekvivalenssiluokka on ekvivalenssiluokka siten, että $w$ ${\overline {a}}$ $\overline{x}$

{\overline {a}}\cdot _{m}{\overline {x}}={\overline {1)),

missä symboli tarkoittaa ekvivalenssiluokkien kertolaskua modulo m [2] . Tällainen merkintätapa edustaa analogia tavanomaiselle käänteisluvun käsitteelle rationaalisten tai reaalilukujen joukossa , jos korvaamme luvut ekvivalenssiluokilla ja määrittelemme oikein binäärioperaatiot . $\cdot _{m}$

Tämän operaation peruskäyttö on ratkaista muodon lineaarinen vastaavuus:

ax\equiv b{\pmod {m)).

Modulaarisen käänteisen löytämisellä on käytännön sovelluksia kryptografian alalla , kuten julkisen avaimen salausjärjestelmä ja RSA-algoritmi [3] [4] [5] . Näiden sovellusten toteutuksen etuna on, että on olemassa erittäin nopea algoritmi ( Extended Euclid's algoritm ), jolla voidaan laskea modulaarisia käänteisarvoja.

Modulaarinen aritmetiikka

Tietylle positiiviselle luvulle m kahden kokonaisluvun a ja b sanotaan olevan kongruentteja modulo m , jos m jakaa niiden eron. Tämä binäärisuhde on merkitty nimellä

a\equiv b{\pmod {m)).

Tämä on kokonaislukujoukon ekvivalenssirelaatio , ja ekvivalenssiluokkia kutsutaan jäännösluokiksi modulo m . Merkitään ekvivalenssiluokkaa, joka sisältää kokonaisluvun a [6] , niin $\mathbb {Z}$ ${\overline {a}}$

{\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.

Lineaarinen vertailu on muodon modulovertailu

ax\equiv b{\pmod {m)).

Toisin kuin lineaariset yhtälöt kokonaislukuina , lineaarisella vertailulla voi olla nolla, yksi tai useampi ratkaisu. Jos x on ratkaisu lineaariseen vertailuun, niin mikä tahansa elementti on myös ratkaisu, joten kun puhumme lineaarisen vertailun ratkaisujen määrästä, tarkoitamme näiden ratkaisujen sisältämien eri ekvivalenssiluokkien määrää. $\overline{x}$

Jos d on a:n ja m :n suurin yhteinen jakaja , niin lineaarisella vertailulla on ratkaisut silloin ja vain, jos d jakaa b :n . Jos d jakaa b , niin ratkaisuja on täsmälleen d [7] . $ax\equiv b{\pmod {m))$

Kokonaisluvun a modulo m on ratkaisu lineaariseen vertailuun

ax\equiv 1{\pmod {m)).

Aikaisemmin sanottiin, että ratkaisu on olemassa, jos ja vain jos a:n ja m:n suurin yhteinen jakaja on 1 , eli a :n ja m :n on oltava suhteellisen alkulukuja . Lisäksi, jos tämä ehto täyttyy, on olemassa täsmälleen yksi ratkaisu, eli jos ratkaisu on olemassa, modulaarinen käänteisarvo on ainutlaatuinen [8] .

Jos sillä on ratkaisu, se merkitään usein seuraavasti $ax\equiv 1{\pmod {m))$

x\equiv a^{-1}{\pmod {m)),

tätä voidaan kuitenkin pitää -arvon väärinkäytönä , koska se voidaan tulkita väärin normaaliksi käänteisluvuksi (joka, toisin kuin moduuliresiprokaali, ei ole kokonaisluku paitsi silloin, kun a on 1 tai -1). Merkintä olisi hyväksyttävä, jos a tulkittaisiin jäännösluokan merkinnäksi , koska jäännösluokan käänteisalkio on jälleen jäännösluokka, jonka kertolasku on määritelty seuraavassa osiossa. $a$ ${\overline {a}}$

Kokonaisluvut modulo m

Ekvivalenssirelaatio modulo m jakaa kokonaislukujoukon m ekvivalenssiluokkaan. Näille objekteille voidaan määrittää yhteen- ja kertolaskuoperaatiot seuraavasti: ekvivalenssiluokkien yhteen- tai kertolaskua varten valitaan ensin näiden luokkien edustajat millä tahansa tavalla, sitten suoritetaan tavallinen toimenpide valituille kokonaisluvuille ja lopuksi tulos. operaatiosta on jäännösluokassa, joka on luokkien operaation tulos. Symbolisessa muodossa, jäännösluokkien operaatioiden kanssa ja edustaa niitä, nämä määritelmät voidaan kirjoittaa muodossa ${\näyttötyyli +_{m))$ $\cdot _{m}$

{\overline {a}}+_{m}{\overline {b}}={\overline {a+b}}

{\overline {a}}\cdot _{m}{\overline {b}}={\overline {ab}}.

Nämä toiminnot ovat hyvin määriteltyjä (mikä tarkoittaa, että lopputulos ei riipu edustajien valinnasta).

Näillä kahdella operaatiolla jäännösluokat modulo m muodostavat renkaan , jota kutsutaan kokonaislukujen renkaaksi modulo m . Näille algebrallisille kokonaisuuksille käytetään useita merkintöjä, joista yleisimmin käytetty on tai , kuitenkin joissakin perusoppikirjoissa ja sovelluksissa käytetään yksinkertaistettua merkintää , ellei se ole ristiriidassa muiden algebrallisten entiteettien kanssa. $\mathbb{Z}/m\mathbb{Z}$ $\mathbb {Z} /m$ $\mathbb {Z} _{m}$

Kokonaislukujen modulo m jäännösluokat tunnettiin perinteisesti jäännösluokina mod m , mikä kuvastaa sitä tosiasiaa, että kaikilla ekvivalenssiluokan elementeillä on sama jäännös, kun ne jaetaan m :llä . Mitä tahansa m kokonaislukujen joukkoa, joka on valittu eri jäännösluokista modulo m , kutsutaan täydelliseksi jäännösten järjestelmäksi modulo m [9] . Jakaminen sarakkeella osoittaa, että kokonaislukujen joukko {0, 1, 2, ..., m − 1} muodostaa täydellisen jäännösjärjestelmän modulo m , joka tunnetaan pienimpänä jäännösjärjestelmänä modulo m . Aritmeettisten tehtävien kanssa työskennellessä on toisinaan kätevämpää työskennellä koko jäännösjärjestelmän kanssa ja käyttää ekvivalenssikieltä, kun taas toisissa tapauksissa on kätevämpää tarkastella rengasekvivalenssiluokkia [10] . $\mathbb{Z}/m\mathbb{Z}$

Jäännösrenkaan kertova ryhmä

Kaikilla kokonaisen jäännösjärjestelmän modulo m elementillä ei ole käänteisalkiota, esimerkiksi nollalla ei ole käänteistä. Sen jälkeen kun on poistettu kokonaisen jäännösjärjestelmän elementit, jotka eivät ole suhteellisen prime-arvoja m :lle, jäljellä olevilla elementeillä, joita kutsutaan pelkistetyksi jäännösjärjestelmäksi, on kaikilla käänteisarvot. Alkioiden lukumäärä pelkistetyssä jäännösjärjestelmässä on , jossa on Euler-funktio , eli m:n suhteellisesti alkulukujen lukumäärä pienempiä kuin m positiivisia kokonaislukuja . ${\näyttötyyli \phi (m)}$ $\phi$

Renkaassa , jossa on yleinen yksikkö, jokaisella elementillä ei ole käänteisarvoa , ja niitä, joilla on, kutsutaan käänteisiksi . Koska käännettävien alkuaineiden tulo on käännettävä, renkaan käännettävät elementit muodostavat ryhmän , renkaan käännettävien elementtien ryhmän , ja tätä ryhmää merkitään usein ikään kuin R olisi renkaan nimi. Kokonaislukurenkaan modulo m käännettävien elementtien ryhmää kutsutaan kokonaislukujen multiplikatiiviseksi ryhmäksi modulo m , ja se on isomorfinen pelkistetyn jäännösjärjestelmän kanssa. Erityisesti sen järjestys (koko) on . $R^{\times }$ ${\näyttötyyli \phi (m)}$

Kun m on alkuluku , sanotaan p , niin kaikilla nollasta poikkeavilla elementeillä on käänteisarvot ja ne ovat silloin äärellinen kenttä . Tässä tapauksessa kokonaislukujen kertova ryhmä modulo p muodostaa syklisen ryhmän kertalukua p − 1 . $\phi (p)=p-1$ $\mathbb{Z}/p\mathbb{Z}$ $\mathbb{Z}/p\mathbb{Z}$

Esimerkki

Havainnollistaaksesi yllä olevia määritelmiä, harkitse esimerkkiä numeroista modulo 10.

Kaksi lukua vastaavat lukua 10, jos ja vain jos niiden ero on jaollinen esimerkiksi 10:llä

32\equiv 12{\pmod {10}}

koska 10 jakaa 32 − 12 = 20,

111\equiv 1{\pmod {10}}

koska 10 jakaa 111 − 1 = 110.

Jotkut tämän moduulin jäännösluokista ovat:

{\displaystyle {\overline {0}}=\{\cdots ,-20,-10,0,10,20,\cdots \))

{\displaystyle {\overline {1}}=\{\cdots ,-19,-9,1,11,21,\cdots \))

{\displaystyle {\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \))

{\overline {9}}=\{\cdots ,-11,-1,9,19,29,\cdots \}.

Lineaarisella vertailulla ei ole ratkaisua, koska luvun 5 kanssa kongruentit kokonaisluvut (eli luvussa ) ovat kaikki parittomat, kun taas 4x ovat kaikki parillisia. Lineaarisessa vertailussa on kuitenkin kaksi ratkaisua, nimittäin ja . gcd(4, 10) = 2 ja 2 ei jaa 5:tä, mutta jakaa 6:n. $4x\equiv 5{\pmod {10}}$ ${\overline {5}}$ $4x\equiv 6{\pmod {10}}$ $x=4$ $x=9$

Koska gcd(3, 10) = 1, lineaarisella vertailulla on ratkaisuja, eli 3:n modulo käänteisluku on olemassa. 7 täyttää tämän yhtälön (21 − 1 = 20). Kuitenkin myös muut kokonaisluvut täyttävät tämän yhtälön, kuten 17 ja −3 (koska 3(17) − 1 = 50 ja 3(−3) − 1 = −10). Erityisesti mikä tahansa kokonaisluku arvosta täyttää yhtälön, koska nämä luvut ovat muotoa 7 + 10 r jollekin r :lle ja on selvää, että $3x\equiv 1{\pmod {10}}$ ${\overline {7))$

3(7+10r)-1=21+30r-1=20+30r=10(2+3r),

on jaollinen 10:llä. Tässä yhtälössä on vain yksi jäännösluokka ratkaisuina. Ratkaisu voidaan tässä tapauksessa saada yksinkertaisesti luettelemalla mahdollisia luokkia, mutta suurille moduuleille ratkaisun saamiseksi tarvitaan systemaattisia algoritmeja, jotka esitellään seuraavissa osioissa.

Jäännösluokkien tulo ja voidaan saada valitsemalla alkio esimerkiksi arvosta 25 ja alkio esimerkiksi arvosta −2, ja niiden tulo (25)(−2) = −50 on ekvivalenssiluokassa . Siten ,. Lisäys määritellään samalla tavalla. Kymmenen jäännösluokkaa yhdessä näiden jäännösluokkien yhteen- ja kertolaskuoperaatioiden kanssa muodostavat kokonaislukujen renkaan modulo 10, eli . ${\overline {5}}$ ${\overline {8}}$ ${\overline {5}}$ ${\overline {8}}$ $\overline {0}$ ${\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}$ $\mathbb {Z} /10\mathbb {Z}$

Täydellinen jäännösjärjestelmän modulo 10 voi olla joukko {10, −9, 2, 13, 24, −15, 26, 37, 8, 9}, jossa jokainen kokonaisluku kuuluu omaan jäännösluokkaansa modulo 10. Minimijäännösjärjestelmä modulo 10 toimii 0, 1, 2, ..., 9}. Jäännösten pelkistetty järjestelmä modulo 10 voi olla {1, 3, 7, 9}. Minkä tahansa näiden lukujen edustaman kahden jäännösluokan tulo on jälleen yksi näistä neljästä luokasta. Tästä seuraa, että nämä neljä jäännösluokkaa muodostavat ryhmän, tässä tapauksessa syklisen luokan 4, jonka generaattorina on 3 tai 7. Esitetyt jäännösluokat muodostavat renkaan käännettävien elementtien ryhmän . Nämä jäännösluokat ovat juuri niitä, joilla on modulo-käänteisluvut. $\mathbb {Z} /10\mathbb {Z}$

Laskenta

Laajennettu Euklidesin algoritmi

Modulo m : n käänteismoduuli voidaan löytää käyttämällä laajennettua euklidista algoritmia.

Euklidesin algoritmi määrittää kahden kokonaisluvun, esimerkiksi a ja m , suurimman yhteisen jakajan (gcd) . Jos a :lla on käänteismoduuli m , tämän gcd:n on oltava yhtä suuri kuin 1. Muutama viimeinen algoritmin toiminnan aikana saatu yhtälö voidaan ratkaista gcd:n löytämiseksi. Sitten "käänteisen substituution" menetelmää käyttämällä voidaan saada lauseke, joka yhdistää alkuperäiset parametrit ja GCD:n. Toisin sanoen voidaan löytää kokonaisluvut x ja y , jotka täyttävät Bézoutin yhtälön ,

ax+my={\text{gcd }}(a,m)=1.

Kirjoitetaan se uudelleen seuraavasti

ax-1=(-y)m,

tuo on,

ax\equiv 1{\pmod {m)),

ja a :n modulokäänteisluku lasketaan. Tehokkaampi versio on laajennettu Euclid-algoritmi, joka vähentää kaksi algoritmin läpikulkua (takaisinkorvaus voidaan ajatella kulkevan algoritmin läpi käänteisessä järjestyksessä) yhdeksi käyttämällä lisäyhtälöitä.

Isolla O-merkinnällä tämä algoritmi toimii ajassa olettaen, että , ja sitä pidetään erittäin nopeana. Se on yleensä tehokkaampi kuin vaihtoehtoinen eksponentiaalinen algoritmi. $O(\log(m)^{2})$ $|a|<m$

Käyttämällä Eulerin lausetta

Vaihtoehtona laajennetulle euklidiselle algoritmille modulaarisen käänteiselementin laskentaan voidaan harkita Eulerin lauseen [11] käyttöä .

Eulerin lauseen mukaan , jos a on suhteellisen alkuluku m : lle , eli gcd( a , m ) = 1, niin

a^{\phi (m)}\equiv 1{\pmod {m)),

missä on Euler-funktio . Tämä johtuu siitä tosiasiasta, että a kuuluu kertovaan ryhmään silloin ja vain, jos a on suhteellisen alkuluku m :lle . Joten modulaarinen käänteinen löytyy suoraan: $\phi$ ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times ))$

a^{\phi (m)-1}\equiv a^{-1}{\pmod {m)).

Erikoistapauksessa, jossa m on alkuluku ja modulaarinen käänteisarvo on annettu ${\näyttötyyli \phi (m)=m-1}$

a^{-1}\equiv a^{m-2}{\pmod {m)).

Tämä menetelmä on yleensä hitaampi kuin laajennettu Euclid-algoritmi, mutta sitä käytetään joskus, jos modulaarisen eksponentioinnin toteutus on jo saatavilla. Tämän menetelmän haitat:

Arvo on tiedettävä ja tehokkain laskentatapa vaatii m laajennusta . Hajoaminen tunnetaan hyvin ongelmana, jossa laskenta vie suurimman osan ratkaisun monimutkaisuudesta. Se voidaan kuitenkin laskea suoraan, jos luvun m hajoaminen alkutekijöiksi tunnetaan . ${\näyttötyyli \phi (m)}$ ${\näyttötyyli \phi (m)}$
Suhteellisen korkeat eksponentiokustannukset. Vaikka tämä voidaan tehdä tehokkaammin modulaarisella rakenteella , suurille m : n arvoille Montgomeryn algoritmimenetelmä on tehokkain . Tämä algoritmi itsessään vaatii käänteismoduulin m laskemisen . Ilman Montgomeryn algoritmia standardi binäärinen eksponentioalgoritmi , joka vaatii modulo m jokaisessa vaiheessa, on hidas operaatio suurelle m :lle .

Tämän tekniikan merkittävä etu on, että siinä ei ole ehdollisia haaroja, jotka riippuvat a:n arvosta , ja siksi a : n arvo , joka voi olla tärkeä salaisuus julkisen avaimen salausjärjestelmissä , voidaan suojata sivukanavahyökkäyksiltä . Tästä syystä Curve25519 :n standarditoteutus käyttää käänteiselementtilaskentatekniikkaa.

Useiden käänteisten laskenta

On mahdollista laskea useiden lukujen käänteiset modulo m käyttämällä yhtä Euklid-algoritmin läpimenoa ja kolmea kertolaskua jokaiselle lisätuloluvulle [12] . Perusajatuksena on muodostaa kaikki , kääntää se ja sitten kertoa kaikille :lla, jolloin jää vain . $a_{i}$ $a_{i}$ $a_{j}$ $j\neq i$ ${\displaystyle a_{i}^{-1))$

Algoritmi (kaikki aritmetiikka tehdään modulo m ):

Laske etuliitetuotteet kaikille . ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1))$ $i\leqslant n$
Laske millä tahansa käytettävissä olevalla algoritmilla. ${\displaystyle b_{n}^{-1))$
Laskemme i : lle n :stä 2:een
- ${\displaystyle a_{i}^{-1}=b_{i}^{-1}b_{i-1))$ ja
- ${\displaystyle b_{i-1}^{-1}=b_{i}^{-1}a_{i))$ .
Lopuksi ,. ${\displaystyle a_{1}^{-1}=b_{1}^{-1))$

Kertominen on mahdollista toteuttaa puurakenteen muodossa lineaarisen sijaan, jotta voidaan varmistaa laskelmien yhdensuuntaisuus .

Sovellukset

Modulaarisen käänteisen etsimisellä on monia sovelluksia modulaarisen aritmeettisen teoriaan perustuvissa algoritmeissa. Esimerkiksi kryptografiassa modulaarisen aritmeettisen tekniikan käyttö mahdollistaa joidenkin toimintojen suorittamisen nopeammin ja pienemmillä muistivaatimuksilla, kun taas toisten operaatioiden suorittaminen on vaikeampaa [13] . Molempia ominaisuuksia voidaan käyttää hyväksi. Erityisesti RSA -algoritmissa salaus ja käänteinen kommunikaatio tapahtuu käyttämällä toistensa suhteen käänteistä numeroparia jossain huolellisesti valitussa modulossa. Toinen näistä numeroista julkistetaan ja sitä voidaan käyttää nopeassa salausmenettelyssä, kun taas toista numeroa käytetään salauksenpurkumenettelyssä, eikä sitä julkisteta. Julkisen piilotetun avaimen määrittämistä pidetään mahdottomana tehtävänä, koska sen ratkaisu vaatii enemmän laskentatehoa kuin maapallolla on, mikä suojaa luvattomalta käytöltä [14] .

Toisena käyttötarkoituksena toisessa kontekstissa harkitse tarkkaa jakoongelmaa tietokoneissa, jossa sinulle annetaan luettelo tietokoneen sanan kokoisista parittomista luvuista, joista jokainen on jaollinen k :llä ja sinun on jaettava ne k :llä . Yksi ratkaisu on seuraava:

Käytämme laajennettua euklidista algoritmia laskeaksemme , modulaarisen käänteisluvun , jossa w on yhtä suuri kuin sanan bittien lukumäärä. Tämä on päinvastainen, koska kaikki luvut ovat parittomia ja jäännöksiä pidetään moduloina, joilla ei ole parittomia jakajia. $k^{{-1}}$ ${\displaystyle k{\pmod {2^{w))))$
Kerromme jokaisen luettelon luvun ja valitsemme tuloksen vähiten merkitsevät bitit (eli hylkäämme kaikki tietokonesanan ulkopuoliset bitit). $k^{{-1}}$

Monissa koneissa, erityisesti niillä, joissa ei ole laitteistotukea jakoa varten, jako on hitaampi toimenpide kuin kertolasku, joten tämä lähestymistapa voi johtaa huomattavaan nopeuden kasvuun. Ensimmäinen vaihe on suhteellisen hidas, mutta se tarvitsee tehdä vain kerran.

Modulaarisia käänteisiä käytetään ratkaisun saamiseksi lineaarisen vertailun järjestelmään, jonka takaa kiinalainen jäännöslause .

Esimerkiksi järjestelmä

{\begin{cases}X\equiv 4{\pmod {5}}\\X\equiv 4{\pmod {7}}\\X\equiv 6{\pmod {11}}\\\end {tapaukset}}

on yleinen ratkaisu, koska 5, 7 ja 11 ovat pareittain koprime . Ratkaisu annetaan kaavalla

X=t_{1}(7\kertaa 11)\kertaa 4+t_{2}(5\kertaa 11)\kertaa 4+t_{3}(5\kertaa 7)\kertaa 6

missä

t_{1}=3

modulaarinen peruutus ,

7\times 11{\pmod {5}}

t_{2}=6

modulaarinen peruutus ,

5\times 11{\pmod {7}}

t_{3}=6

modulaarinen käänteinen .

5\times 7{\pmod {11}}

Sitten,

X=3\times (7\kertaa 11)\kertaa 4+6\kertaa (5\kertaa 11)\kertaa 4+6\kertaa (5\kertaa 7)\kertaa 6=3504

ja annetussa muodossa

X\equiv 3504\equiv 39{\pmod {385}}

koska 385 on lukujen 5, 7 ja 11 pienin yhteinen kerrannainen .

Modulaarinen käänteiskappale on näkyvästi Kloostermanin summien määritelmässä .

Katso myös

Käänteinen kongruentiomenetelmä on algoritmi pseudosatunnaislukujen generoimiseksi, joka käyttää modulo-käänteislukuja.
Rationaaliluvun palautus modulo it

Muistiinpanot

↑ Rosen, 1993 , s. 132.
↑ Schumacher, 1996 , s. 88.
↑ Stinson, 1995 , s. 124-128.
↑ Trappe, Washington, 2006 , s. 164-169.
↑ Moriarty, K.; Kaliski, B.; Jonsson, J.; Rusch, A. PKCS #1: RSA Cryptography Specifications Versio 2.2 . Internet Engineering Task Force RFC 8017 . Internet Engineering Task Force (2016). Haettu 21. tammikuuta 2017. Arkistoitu alkuperäisestä 12. joulukuuta 2018. (määrätön)
↑ Muita merkintöjä käytetään usein, mukaan lukien [ a ] ja [ a ] m .
↑ Irlanti, Rosen, 1990 , s. 32.
↑ Shoup, 2005 , s. 15 Lause 2.4.
↑ Rosen, 1993 , s. 121.
↑ Irlanti, Rosen, 1990 , s. 31.
↑ Koshy, 2007 , s. 346.
↑ Brent, Zimmermann, 2010 , s. 67–68.
↑ Trappe, Washington, 2006 , s. 167.
↑ Trappe, Washington, 2006 , s. 165.

Kirjallisuus

Douglas R. Stinson. Kryptografia / Teoria ja käytäntö. - CRC Press, 1995. - ISBN 0-8493-8521-0 .
Victor kauppa. Laskennallinen johdatus lukuteoriaan ja algebraan . - Cambridge University Press, 2005. - ISBN 9780521851541 .
Thomas Koshy. Alkeislukuteoria sovelluksilla . – 2. painos. - Academic Press, 2007. - ISBN 978-0-12-372487-8 .
Richard P. Brent , Paul Zimmermann . §2.5.1 Useita inversioita kerralla // Alkuperäinen lukuteoria sovelluksilla. Nykyaikainen tietokonearitmetiikka . - Cambridge University Press, 2010. - V. 18. - (Cambridge Monographs on Computational and Applied Mathematics). — ISBN 978-0-521-19469-3 .

Kenneth Irlanti, Michael Rosen. Klassinen johdatus nykyaikaiseen lukuteoriaan. – 2. - Springer-Verlag, 1990. - ISBN 0-387-97329-X .
- C. Ireland, M. Rosen. Klassinen johdatus nykyaikaiseen lukuteoriaan / Kääntäjä englannista S. P. Demushkin. - Moskova: Mir, 1987.

Kenneth H. Rosen. Peruslukuteoria ja sen sovellukset. – 3. - Addison-Wesley, 1993. - ISBN 978-0-201-57889-8 .
Carol Schumacher. Luku 0: Abstraktin matematiikan peruskäsitteet . - Addison-Wesley, 1996. - ISBN 0-201-82653-4 .
Wade Trappe, Lawrence C. Washington. Johdatus kryptografiaan koodausteorialla. – 2. - Prentice-Hall, 2006. - ISBN 978-0-13-186239-5 .

Linkit

Weisstein, Eric W. Modular Inverse (englanniksi) Wolfram MathWorld -verkkosivustolla .
Guevara Vasquez, Fernando tarjoaa esimerkin käänteisen modulon ratkaisemisesta euklidisen algoritmin avulla.