Eukleideen algoritmi

Euklidesin algoritmi  on tehokas algoritmi kahden kokonaisluvun suurimman yhteisen jakajan (tai kahden segmentin yhteisen suuren ) löytämiseen . Algoritmi on nimetty kreikkalaisen matemaatikon Eukleideen (3. vuosisadalla eKr.) mukaan, joka kuvaili sen ensimmäisen kerran VII [1] ja X [2] kirjoissa " Beginnings ". Se on yksi vanhimmista nykyään käytössä olevista numeerisista algoritmeista [3] .

Yksinkertaisimmillaan Euklidesin algoritmia sovelletaan positiivisten kokonaislukujen pariin ja se muodostaa uuden parin, joka koostuu pienemmästä luvusta ja suurempien ja pienempien lukujen erotuksesta . Prosessi toistetaan, kunnes luvut ovat yhtä suuret. Löytynyt luku on alkuperäisen parin suurin yhteinen jakaja. Euclid ehdotti algoritmia vain luonnollisille luvuille ja geometrisille suureille (pituudet, pinta-alat, tilavuudet). Kuitenkin 1800-luvulla se yleistettiin muun tyyppisiin matemaattisiin objekteihin , mukaan lukien Gaussin kokonaisluvut ja polynomit yhdessä muuttujassa . Tämä johti euklidisen renkaan käsitteen syntymiseen nykyaikaisessa yleisalgebrassa . Myöhemmin Euclidin algoritmi yleistettiin muihin matemaattisiin rakenteisiin , kuten solmuihin ja moniulotteisiin polynomeihin .

Tälle algoritmille on olemassa monia teoreettisia ja käytännön sovelluksia. Erityisesti se on pohjana RSA :n julkisen avaimen salausalgoritmille [4] , jota käytetään laajasti sähköisessä kaupankäynnissä . Algoritmia käytetään myös lineaaristen diofantiiniyhtälöiden ratkaisemisessa [5] , jatkuvien murtolukujen muodostamisessa [6] , Sturmin menetelmässä [7] . Euklidesin algoritmi on päätyökalu nykyaikaisen lukuteorian lauseiden todistamiseen , kuten Lagrangen neljän neliön lause [8] ja aritmeettisen peruslause [9] .

Historia

Muinaiset kreikkalaiset matemaatikot kutsuivat tätä algoritmia ἀνθυφαίρεσις tai ἀνταναίρεσις  - "keskinäinen vähennys". Eukleides ei löytänyt tätä algoritmia , koska siitä on jo maininta Aristoteleen aiheessa (4. vuosisadalla eKr.) [3] . Eukleideen "Elementeissä" se kuvataan kahdesti - Kirjassa VII kahden luonnollisen luvun suurimman yhteisen jakajan löytämiseksi [1] ja kirjassa X kahden homogeenisen suuren suurimman yhteisen suuren löytämiseksi [2] . Molemmissa tapauksissa algoritmin geometrinen kuvaus annetaan kahden segmentin "yhteisen mittauksen" löytämiseksi.

Matematiikan historioitsijat ovat ehdottaneet, että Euklidesin algoritmin (peräkkäisen keskinäisen vähennyslaskumenettelyn) avulla epäyhtenäisten suureiden (neliön sivut ja lävistäjät tai säännöllisen viisikulmion sivut ja lävistäjät ) olemassaolo löydettiin ensimmäisen kerran muinaisissa aikoina. kreikkalainen matematiikka [10] . Tälle olettamukselle ei kuitenkaan ole riittäviä asiakirjoja. Algoritmi kahden luonnollisen luvun suurimman yhteisen jakajan löytämiseksi on kuvattu myös muinaisen kiinalaisen tutkielman Mathematics yhdeksässä kirjassa I kirjassa .

Kuvaus

Euklidesin algoritmi kokonaisluvuille

Olkoon ja olla kokonaislukuja, jotka eivät ole samanaikaisesti yhtä suuria kuin nolla, ja numerosarja

määritellään sillä, että kukin on edellisen luvun jakojäännös edellisellä ja toiseksi viimeinen jaetaan viimeisellä, eli:

Tällöin gcd( a , b ), a:n ja b :n suurin yhteinen jakaja , on yhtä suuri kuin r n , tämän sekvenssin viimeinen nollasta poikkeava jäsen [11] .

Sellaisen r 1 , r 2 , …, r n , eli mahdollisuus jakaa jäännöksellä m n : llä mille tahansa kokonaisluvulle m ja kokonaisluvulle n ≠ 0 , todistetaan induktiolla m .

Tämän algoritmin oikeellisuus seuraa seuraavista kahdesta lauseesta [12] :

I. Olkoon a = b ⋅ q + r , sitten gcd (a, b) = gcd (b, r).

1. Olkoon k mikä tahansa lukujen a ja b yhteinen jakaja , ei välttämättä suurin, silloin a = t 1 ⋅ k ja b = t 2 ⋅ k , missä t 1 ja t 2 ovat määritelmän kokonaislukuja.
2. Tällöin k on myös b :n ja r : n yhteinen jakaja , koska b on jaollinen k :llä määritelmän a mukaan (suluissa oleva lauseke on kokonaisluku, joten k jakaa r :n ilman jäännöstä).
3. Päinvastoin on myös totta ja todistetaan samalla tavalla kuin kohdassa 2: mikä tahansa b :n ja r : n jakaja on myös a : n ja b :n jakaja .
4. Siksi kaikki lukuparien ( a , b ) ja ( b , r ) yhteiset jakajat ovat samat. Toisin sanoen ei ole olemassa yhteistä lukujen ( a , b ) jakajaa, joka ei olisi myös ( b , r ) jakaja ja päinvastoin.
5. Erityisesti suurin yhteinen jakaja pysyy samana, koska olettaen, että gcd ( a , b ) > gcd ( b , r ) tai gcd ( a , b ) < gcd ( b , r ) saadaan ristiriitoja, joten gcd ( a ) , b ) = gcd ( b , r ). Q.E.D.

II. gcd( r , 0) = r mille tahansa nollasta poikkeavalle r :lle (koska 0 on jaollinen millä tahansa kokonaisluvulla).

Eukleideen geometrinen algoritmi

Olkoon kaksi segmenttiä, joiden pituus on a ja b . Vähennä pienempi segmentti suuremmasta segmentistä ja korvaa suurempi segmentti saadulla erolla. Toistamme tätä toimenpidettä vähentämällä pienempi segmentti suuremmasta segmentistä, kunnes segmentit ovat yhtä suuret. Jos näin tapahtuu, alkuperäiset segmentit ovat vertailukelpoisia , ja viimeinen saatu segmentti on niiden suurin yhteinen mitta. Jos yhteistä mittaa ei ole, prosessi on ääretön. Tässä muodossa algoritmin kuvaa Euclid [2] ja se toteutetaan kompassin ja suoraviivan avulla .

Esimerkki

Havainnollistamiseksi käytetään euklidelaista algoritmia etsimään gcd a = 1071 ja b = 462. Aluksi vähennämme luvusta 1071 luvun 462 kerrannainen, kunnes saamme erotuksen, joka on pienempi kuin 462. Meidän on vähennettävä 462 kahdesti, ( q 0 = 2), jäljelle jää 147:

Sitten vähennetään luvusta 462 luvun 147 kerrannainen, kunnes ero on pienempi kuin 147. Meidän on vähennettävä 147 kolme kertaa ( q 1 = 3), jäännös 21:een:

Sitten vähennetään 21:n kerrannainen luvusta 147, kunnes ero on pienempi kuin 21. Meidän on vähennettävä 21 seitsemän kertaa ( q 2 = 7), jättämättä jäännöstä:

Näin ollen sekvenssi a > b > r 1 > r 2 > r 3 > ... > r n tässä nimenomaisessa tapauksessa näyttää tältä:

Koska viimeinen jäännös on nolla, algoritmi päättyy arvoon 21 ja gcd(1071, 462) = 21.

Taulukkomuodossa vaiheet olivat seuraavat:

Jos gcd on löydettävä useammalle kuin kahdelle luvulle, algoritmi on samanlainen, jokaisessa vaiheessa kaikki luvut pienintä lukuun ottamatta korvataan jäännöksillä modulo pienin. Nolla jäännöstä, jos sellaisia ​​on, on yliviivattu. Algoritmi päättyy, kun jäljellä on yksi nollasta poikkeava luku, tämä on GCD.

Sovellukset

Laajennettu Euclidin algoritmi ja Bezoutin relaatio

Kaavat voidaan kirjoittaa uudelleen seuraavasti:

Tässä s ja t ovat kokonaislukuja. Tätä suurimman yhteisen jakajan esitystä kutsutaan Bezout-suhteeksi ja luvut s ja t  ovat Bezout-kertoimia [13] . Bezoutin relaatio on avainasemassa Eukleideen lemman ja aritmeettisen peruslauseen todistuksessa .

Jatkuvia murtolukuja

Euklidesin algoritmi liittyy melko läheisesti jatkuviin murtolukuihin [6] . Suhde a / b voidaan esittää jatkuvana murtolukuna:

Tässä tapauksessa jatkuva murto-osa ilman viimeistä termiä on yhtä suuri kuin Bezout-kertoimien suhde t / s , otettuna miinusmerkillä:

Euklides-algoritmin määrittävä yhtäläisyyssarja voidaan kirjoittaa uudelleen muotoon:

Viimeinen termi yhtälön oikealla puolella on aina yhtä suuri kuin seuraavan yhtälön vasemman puolen käänteisluku. Siksi kaksi ensimmäistä yhtälöä voidaan yhdistää muodossa:

Kolmannella yhtälöllä voidaan korvata lausekkeen r 1 / r 0 nimittäjä , saadaan:

Jäännösten viimeinen suhde r k / r k −1 voidaan aina korvata käyttämällä sekvenssin seuraavaa yhtälöä ja niin edelleen viimeiseen yhtälöön asti. Tuloksena on jatkuva murto-osa:

Yllä olevassa esimerkissä GCD(1071, 462) laskettiin ja osamäärät q k todettiin vastaavasti 2, 3 ja 7. Siksi 1071/462 voidaan kirjoittaa seuraavasti:

Lineaariset diofantiiniyhtälöt

Diofantiiniyhtälö  on yhtälö, jossa on kokonaislukukertoimia ja yksi tai useampi muuttuja ja jonka tehtävänä on löytää vain sen kokonaislukujuuret. Tällaisella yhtälöllä voi olla ääretön määrä ratkaisuja, äärellinen määrä ratkaisuja tai ei yhtään. Yksinkertaisin diofantiiniyhtälö on lineaarinen kahden tuntemattoman kanssa:

missä a , b , c  ovat kokonaislukuja. Euklidisen algoritmin avulla voidaan löytää täydellinen ratkaisu tämän tyyppiselle yhtälölle [5] . Ensinnäkin, käyttämällä tätä algoritmia, voit määrittää d = gcd( a , b ). Sitten k ja l määritetään käyttämällä laajennettua Euklides-algoritmia siten, että:

Eli x \u003d k ja y \u003d l  on erityinen ratkaisu yhtälöön c \u003d d . Osoittautuu, että jos c = q⋅d , niin x = q⋅k , y = q⋅l  on alkuperäisen yhtälön erityinen ratkaisu, koska:

Kääntäen, jos yhtälöllä on ainakin yksi ratkaisu, niin c on d :n kerrannainen . Tämä johtuu siitä, että d jakaa sekä a :n että b :n (ja siten koko vasemman puolen), joten sen on jaettava myös c (oikea puoli). Siten lineaarisella diofantiiniyhtälöllä on ainakin yksi ratkaisu silloin ja vain, jos c on gcd( a , b ) -kerrannainen.

Muunnelmia ja yleistyksiä

Euklidinen rengas

Renkaita , joissa euklidelaista algoritmia voidaan soveltaa, kutsutaan euklidisiksi renkaiksi [14] . Näitä ovat erityisesti kokonaislukujen renkaat ja polynomien renkaat .

Yleistetty Euklidesin algoritmi polynomeille

Euklidesin algoritmi ja laajennettu Euklidesin algoritmi yleistyvät luonnollisesti polynomien renkaaseen k [ x ] yhdessä muuttujassa mielivaltaisen kentän k yli , koska tällaisille polynomeille on määritelty jako jäännöksellä. Suorittaessaan Euclid-algoritmia polynomeille, samoin kuin Euclid-algoritmia kokonaislukuille, saadaan polynomijäännössekvenssi (PRS) [15] .

Olkoon cont(f) määritelmän mukaan polynomin kertoimien gcd  polynomin sisällöstä . Osamäärää, jossa f(x) jaetaan cont(f):llä, kutsutaan polynomin f(x) primitiiviosaksi ja sitä merkitään primpart(f(x)). Näitä määritelmiä tarvitaan kahden polynomin p 1 (x) ja p 2 (x) GCD:n löytämiseksi renkaasta . Kokonaislukuja ylittäville polynomeille seuraava on totta:

NOD NÖYTÄ

NOD NÖYTÄ

Siten kahden mielivaltaisen polynomin gcd:n löytämisen ongelma on pelkistetty primitiivisten polynomien gcd:n löytämisen ongelmaksi.

Olkoon Z[x]:sta kaksi primitiivistä polynomia p 1 (x) ja p 2 (x), joiden potenssien välinen suhde täyttyy: deg(p 1 (x)) = m ja deg(p 2 (x) ) = n, m > n. Polynomien jako jäännösjäännöksellä merkitsee jaon suurimman kertoimen tarkkaa jaotettavuutta jakajan korkeimmalla kertoimella; yleensä jakoa jäännöksellä ei voida suorittaa. Tästä syystä otetaan käyttöön pseudojako-algoritmi, joka kuitenkin mahdollistaa pseudoosamäärän ja pseudojäännösosan (prem) saamisen, jotka itse kuuluvat kokonaislukujen yli olevien polynomien joukkoon.

Pseudojaolla tarkoitetaan sitä, että itse jakoa edeltää polynomin kertominen luvulla , ts.

missä ja  ovat pseudopartiaali ja pseudojäännös, vastaavasti.

Siis ja lisäksi . Sitten Euclidin algoritmi koostuu seuraavista vaiheista:

1. GCD-sisällön laskeminen:

GCD .

2. Alkuperäisten osien laskeminen:

3. Polynomitähteiden sekvenssin rakentaminen:

4. Palautustulos:

Jos , niin palauta , muuten palauta .

Algoritmin nopeutetut versiot

• Yksi menetelmistä nopeuttaa Euklidisen kokonaislukualgoritmia on käyttää symmetristä jäännöstä [16] :

• Yksi versio kiihdytetystä Euclid-algoritmista polynomeille perustuu siihen, että algoritmin väliarvot riippuvat pääasiassa suurista tehoista. " Haja ja hallitse " -strategian soveltaminen mahdollistaa algoritmin asymptoottisen monimutkaisuuden vähentämisen [16] .

Algoritmin laskennallinen monimutkaisuus

Euklidisen algoritmin laskennallinen monimutkaisuus on tutkittu täysin. [17] Tämä monimutkaisuus voidaan kuvata tulona algoritmin vaatimien jakovaiheiden lukumäärästä kertaa yhden askeleen laskennallinen monimutkaisuus. Reinnaud ehdotti ensimmäisen tunnetun Euklidesin algoritmin analyysin vuonna 1811. [18] Hän osoitti, että algoritmin vaiheiden lukumäärä lukuparille ( u , v ) on rajoitettu arvoon v . Myöhemmin hän paransi sidosta v /2 + 2:een. Émile Léger vuonna 1837 tutki pahinta tapausta, jolloin peräkkäiset Fibonacci-luvut syötetään laskemaan gcd . [19] Sitten vuonna 1841 Pierre Joseph Fink osoitti [20] , että algoritmin vaiheiden määrä ei ylitä 2 log 2  v  + 1. Siksi algoritmi toimii polynomiajassa pienemmän parin koolla. numeroista ( u , v ). [19] Gabriel Lame tarkensi Finkin analyysiä vuonna 1844. [21] Hän osoitti, että algoritmin suorittamiseen tarvittavien vaiheiden määrä on enintään viisi kertaa h  , numeroiden lukumäärä pienemmän numeroparin desimaalimuodossa ( u , v ). [22] [23]

Kun GCD lasketaan luvuille, jotka mahtuvat yhteen konesanaan , jokainen algoritmin vaihe vie vakioajan. Tässä tapauksessa Lamen analyysi viittaa siihen, että laskennallisen monimutkaisuuden arvioidaan olevan O ( h ). Laskentamallissa, joka soveltuu laskelmiin, joissa luku on suurempi kuin yksi konesana, yhden jäännöksen laskemisen monimutkaisuuden estimaatti voi kuitenkin olla O ( h 2 ). [24] Tässä tapauksessa algoritmin kaikkien vaiheiden kokonaisaika voidaan analysoida käyttämällä teleskooppisarjaa , mikä osoittaa, että se on myös O ( h 2 ). Euklides-algoritmin nopeuttamiseksi voidaan käyttää nykyaikaisia ​​Schönhage-Strassen- menetelmään perustuvia algoritmisia menetelmiä nopeaan kokonaislukukertomiseen. Tämä johtaa kvasipolynomiseen aikaan . [25]

Vaiheiden määrä

Kahden luonnollisen luvun a ja b gcd:n laskemisen vaiheiden lukumäärä merkitään T ( a ,  b ). Jos g on a :n ja b :  n suurin yhteinen jakaja , niin a  =  mg ja b  =  ng kahdelle alkulukulle m ja n . Tällöin T ( a , b ) = T ( m , n ) , mikä näkyy, jos jaamme parin ( a ,  b ) gcd:tä laskettaessa saadut yhtälöt g :llä . [26] Samalla periaatteella algoritmin vaiheiden lukumäärä pysyy muuttumattomana, jos a ja b kerrotaan yhteisellä kertoimella w , joka on ekvivalentti T ( a , b ) = T ( wa , wb ). Siksi vaiheiden määrä T voi vaihdella suuresti vierekkäisten lukuparien, kuten ( a ,  b ) ja ( a ,  b+1 ), välillä, koska tämä arvo riippuu gcd:stä.

Euklidisen algoritmin rekursiivinen luonne antaa seuraavan yhtälön T ( a , b )=1+ T ( b , r0 ) =2+ T ( r0 , r1 ) = … = N + T ( rN − 2 , r N −1 ) = N + 1 , missä T ( x , 0) = 0 oletuksena. [17]

Huonoin tapaus

Jos Euklidesin algoritmi vaatii N askelta luonnollisten lukujen parille a  >  b > 0, a:n ja b :  n pienimmät arvot, joille tämä pätee, ovat Fibonaccin luvut F N +2 ja F N +1 , vastaavasti. [27] Sitten, jos Euklidesin algoritmi vaatii N askelta lukuparille ( a , b ), missä a  >  b , seuraavat epäyhtälöt a  ≥  F N +2 ja b  ≥  F N +1 pätevät . Tämä voidaan todistaa matemaattisella induktiolla . Jos N  = 1, niin a on jaollinen b :llä ilman jäännöstä. Pienimmät luonnolliset luvut, joille tämä pitää paikkansa, ovat b  = 1 ja a  = 2, vastaavasti F 2 ja F 3 . Oletetaan nyt, että tulos pätee kaikkiin N : n arvoihin M  − 1:een asti. Euklidisen algoritmin ensimmäinen askel, jossa on M askelta , on a  =  q 0 b  +  r 0 ja euklidinen algoritmi lukuparille ( b , r 0 ), missä b  >  r 0 , vaatii M  − 1 askelta. Induktiohypoteesin mukaan meillä on b  ≥  F M +1 ja r 0  ≥  F M . Siksi a  =  q 0 b  +  r 0  ≥  b  +  r 0  ≥  F M +1  +  F M  =  F M +2 , joka on vaadittu epäyhtälö. Tämä Gabriel Lamen vuonna 1844 julkaisema todiste edustaa laskennallisen monimutkaisuuden teorian alkua [28] ja myös Fibonacci-lukujen ensimmäistä käytännön sovellusta . [27]

Lamen lause

Jakojäännösten lukumäärä Euklid-algoritmin soveltamisprosessissa ei ylitä viisi kertaa desimaalijärjestelmään kirjoitetun pienemmän luvun numeroiden lukumäärää [29] .

Keskimääräinen

Algoritmin vaiheiden keskimääräisen määrän laskemiseen on useita tapoja. Ensimmäinen laskentamenetelmä on keskimääräinen aika T ( a ), joka tarvitaan tietyn luvun a ja pienemmän luonnollisen luvun b gcd:n laskemiseen , valittuna yhtä suurella todennäköisyydellä kokonaisluvuista 0 - a  − 1. [17]

Koska T ( a , b ) kuitenkin vaihtelee paljon näiden kahden luvun gcd:n kanssa, keskiarvoistettu funktio T ( a ) on myös kohinainen. [30] Tämän kohinan vähentämiseksi otetaan toinen keskiarvo τ ( a ) kaikilta luvuilta , jotka ovat suhteellisesti alkulukuja a -arvoon .

missä φ ( a ) on Euler-funktio . Tämä keskiarvo kasvaa tasaisesti kasvaessa . [31]

Tämän kaavan vakio (Porterin vakio [32] ) on , ja ε on äärettömän pieni .

Kolmas keskiarvo Y ( n ) määritellään tarvittavien askelmien keskimääräiseksi lukumääräksi, kun a ja b valitaan satunnaisesti ( tasaisesti jakautuneina ) välillä 1 - n .

Vaiheen laskennallinen monimutkaisuus

Euklidisen algoritmin jokaisessa vaiheessa kerroin q k ja jäännös r k lasketaan tietylle kokonaislukuparille r k −2 ja r k −1 . Nämä suuret liittyvät toisiinsa seuraavalla suhteella:

r k −2 = q k r k −1 + r k

Kunkin vaiheen laskennallinen monimutkaisuus liittyy pääasiassa q k :n löytämiseen , koska loppuosa r k voidaan laskea nopeasti käyttämällä r k −2 , r k −1 ja q k

r k = r k −2 − q k r k −1

H -kokoisten bittien lukumäärän jakamisoperaation laskennallinen monimutkaisuus arvioidaan O ( h ( ℓ +1)), missä ℓ on osamäärän koko. [24]

Vertailun vuoksi, alkuperäinen Euclid-algoritmi, joka käyttää vähennyslaskua, voi olla paljon hitaampi. Useimmissa tapauksissa kerroin q k on pieni luku. Tietyn osamäärän q todennäköisyys on suunnilleen yhtä suuri kuin ln| u /( u  − 1)|, missä u  = ( q  + 1) 2 . [33] Havainnollistamiseksi, osamäärän 1, 2, 3 tai 4 todennäköisyys on noin 41,5 %, 17,0 %, 9,3 % ja 5,9 %. Koska vähentäminen on nopeampaa kuin jako, varsinkin yhtä sanaa suuremmilla luvuilla, [34] Euklidesin vähennyslaskua käyttävä algoritmi voi olla kilpailukykyisempi kuin jakoa käyttävä algoritmi. [35] Tätä käytetään binäärialgoritmissa gcd: n laskemiseen . [36]

Algoritmin monimutkaisuusestimaatti lasketaan vaiheiden lukumäärän ja yhden vaiheen suorittamiseen kuluvan ajan tulona. Se osoittaa, että Euklidesin algoritmi kasvaa neliöllisesti O ( h 2 ), missä h  on kahdessa alkuluvussa a ja b olevien numeroiden keskimääräinen lukumäärä desimaalimuodossa. Olkoon h 0 , h 1 , …, h N −1 numeroiden lukumäärä peräkkäisissä jäännöksissä r 0 ,  r 1 , …,  r N −1 . Koska vaiheiden määrä N kasvaa lineaarisesti h :n kanssa, ajoaikaa rajoittaa seuraava lauseke:

Muistiinpanot

1. ↑ 1 2 Mordukhai-Boltovskoy, 1949 , s. 11-13.
2. ↑ 1 2 3 Mordukhai-Boltovskoy, 1949 , s. 103-105.
3. ↑ 1 2 Knuth, 2001 , s. 378.
4. ↑ Menezes, 1996 , s. 286.
5. ↑ 1 2 Courant, 2001 , s. 74-76.
6. ↑ 1 2 Vinogradov, 1952 , s. 14-18.
7. ↑ Engeler, 1987 , s. 24-31.
8. ↑ Tikhomirov, 2003 , s. 11-14.
9. ↑ Kaluzhin, 1969 , s. 6-14.
10. ↑ Zeiten, 1932 , s. 112-114.
11. ↑ Vinogradov, 1952 , s. 9-10.
12. ↑ Courant, 2001 , s. 67-70.
13. ↑ Hasse, 1953 , s. 29-30.
14. ↑ Kurosh, 1973 , s. 91-92.
15. ↑ Pankratiev, 2007 , s. 54-58.
16. ↑ 12. Gathen , 2013 , s. 313-326.
17. ↑ 1 2 3 Knuth, 1997 , s. 344.
18. ↑ Shallit, 1994 , s. 414.
19. ↑ 1 2 Shallit, 1994 , s. 401-419.
20. ↑ Shallit, 1994 , s. 413.
21. ↑ Lame, 1844 , s. 867-870.
22. ↑ Grossman, 1924 , s. 443.
23. ↑ Abramov S. A. Matemaattiset rakenteet ja ohjelmointi. - M., Nauka , 1978. - Levikki 100 000 kappaletta. - c. 170
24. ↑ 1 2 Knuth, 1997 , s. 257-261.
25. ↑ Moeller, 2005 , s. yksi.
26. ↑ Malmi, 1948 , s. 45.
27. ↑ 1 2 Knuth, 1997 , s. 343.
28. ↑ LeVeque, 1996 , s. 3.
29. ↑ Abramov S. A. Matemaattiset rakenteet ja ohjelmointi. - M., Nauka, 1978. - Levikki 100 000 kappaletta. - c. 170
30. ↑ Knuth, 1997 , s. 353.
31. ↑ Tonkov, 1974 , s. 47-57.
32. ↑ Weisstein, Eric W. Porter's Constant  Wolfram MathWorld -verkkosivustolla .
33. ↑ Knuth, 1997 , s. 352.
34. ↑ Wagon, 1999 , s. 335-336.
35. ↑ Cohen, 1993 , s. neljätoista.
36. ↑ Cohen, 1993 , s. 14-15, 17-18.

Kirjallisuus

• Abramov S. A. Tunnetuin algoritmi // Kvant / toim. A. L. Semenov , A. A. Gaifullin - MIAN , 1985. - voi. 11. - S. 44-46. — ISSN 0130-2221
• Vinogradov I.M. Lukuteorian perusteet . - M. - L .: GITTL, 1952. - 180 s. - ISBN 978-5-811-40535-0 .
• Kaluzhin L. A. Aritmetiikan peruslause. — Suosittuja matematiikan luentoja . - M . : Nauka, 1969. - 33 s.
• Knut D.E. Ohjelmoinnin taito. - Williams, 2001. - T. 2. - 829 s. — ISBN 5-8459-0081-6 .
• Courant R., Robbins G. Täydennys luvulle I, § 4. // Mitä on matematiikka?  - 3. painos, Rev. ja ylimääräistä - M. , 2001. - 568 s. - ISBN 5-900916-45-6 .
• Kurosh A. G. Luentoja yleisalgebrasta / toim. O. N. Golovin - 2. painos. — M .: Nauka , 1973. — 400 s. — ISBN 978-5-8114-0617-3
• Eukleideen alku / käännetty kreikaksi. ja comm. D. D. Mordukhai-Boltovsky, toim. Vygodsky M. Ya. ja Veselovsky I. N. - GITTL, 1949. - T. 2. - 511 s.
• Pankratiev EV Tietokonealgebran elementit. - INTUIT, 2007. - 217 s. - ISBN 978-5-955-60099-4 .
• Tikhomirov VM Menneisyyden suuret matemaatikot ja heidän suuret lauseensa. — 2. painos, korjattu. - MTsNMO , 2003. - 16 s. — ISBN 5-94057-110-7 .
• Hasse G. Luentoja lukuteoriasta. - Toim. ulkomainen kirjallisuus, 1953. - 527 s.
• Zeiten GG Matematiikan historia antiikin ajalta ja keskiajalla. - GTTI, 1932. - 232 s.
• Engeler E. Alkeismatematiikan metamatematiikka. - M .: Mir, 1987. - 128 s.
• Cohen H. Laskennallisen algebrallisen lukuteorian kurssi . - Springer-Verlag, 1993. - ISBN 0-387-55640-0 .
• von zur Gathen J., Gerhard J. Modern Computer Algebra . - Cambridge University Press, 2013. - 808 s. — ISBN 978-1-107-03903-2 .
• Grossman H. Osioiden lukumäärästä GCD:n löytämisessä  //  The American Mathematical Monthly. - 1924. - Voi. 31 , iss. 9 . - s. 443 . - doi : 10.2307/2298146 . — .
• Knuth D.E. Tietokoneohjelmoinnin taito . - 3. - Addison-Wesley, 1997. - V. 2: Seminumerical Algorithms. — ISBN 0-201-89684-2 .
• Lamé G. Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers  (ranska) . Comptes Rendus Acad. Sci., 1844. - nro 19 .
• LeVeque WJ Numeroteorian perusteet  (englanti) . - Dover, 1996. - ISBN 0-486-68906-9 .
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. - CRC-Press, 1996. - 816 s. - (Diskreetti matematiikka ja sen sovellukset). - ISBN 0-8493-8523-7 .
• Moeller Niels. Laskennan matematiikka  (englanti) . – 2005.
• Ore O. Numeroteoria ja sen historia  (englanti) . - McGraw-Hill, 1948.
• Shallit J. Euklidisen algoritmin analyysin alkuperä  (englanniksi)  // Historia Math .. - 1994. - Vol. 21 . - doi : 10.1006/hmat.1994.1031 .
• Tonkov T. Äärillisten jatkuvien jakeiden keskipituudesta  (englanti)  // Acta Arithmetica. - 1974. - Voi. 26 .
• Wagon S. Mathematica toiminnassa  . - Springer-Verlag, 1999. - ISBN 0-387-98252-3 .

Linkit

• Euclid-algoritmin toteutus Pascalissa

• Euclidin algoritmi osoitteessa e-maxx.ru
• Laajennetun Euclid-algoritmin toteutus C:ssä

Sanakirjat ja tietosanakirjat	Suuri tanskalainen Hienoa norjalaista Iso venäläinen kroatialainen Britannica (verkossa) Brockhaus
Bibliografisissa luetteloissa	GND : 4659898-4