Euklids algoritme

Euklids algoritme  er en effektiv algoritme til at finde den største fælles divisor af to heltal (eller det fælles mål for to segmenter ). Algoritmen er opkaldt efter den græske matematiker Euklid (3. århundrede f.Kr.), som først beskrev den i VII [1] og X [2] bøgerne " Begyndelser ". Det er en af ​​de ældste numeriske algoritmer i brug i dag [3] .

Euklids algoritme anvendes på sit enkleste til et par positive heltal og genererer et nyt par, der består af det mindre tal og forskellen mellem de større og mindre tal. Processen gentages, indtil tallene er ens. Det fundne tal er den største fælles divisor af det oprindelige par. Euclid foreslog kun en algoritme for naturlige tal og geometriske størrelser (længder, arealer, volumener). Men i det 19. århundrede blev det generaliseret til andre typer matematiske objekter , herunder Gaussiske heltal og polynomier i én variabel . Dette førte til fremkomsten af ​​begrebet den euklidiske ring i moderne algebra . Senere blev Euklids algoritme generaliseret til andre matematiske strukturer såsom knob og multidimensionelle polynomier .

Der er mange teoretiske og praktiske anvendelser for denne algoritme. Det er især grundlaget for RSA public key kryptografiske algoritme [4] , som er meget brugt i e-handel . Algoritmen bruges også til løsning af lineære diofantiske ligninger [5] , ved konstruktion af fortsatte brøker [6] , i Sturm-metoden [7] . Euklids algoritme er det vigtigste værktøj til at bevise sætninger i moderne talteori , såsom Lagranges fire-kvadrat-sætning [8] og aritmetikkens grundsætning [9] .

Historie

Gamle græske matematikere kaldte denne algoritme ἀνθυφαίρεσις eller ἀνταναίρεσις  - "gensidig subtraktion". Denne algoritme blev ikke opdaget af Euklid , da der allerede er en omtale af den i emnet Aristoteles (4. århundrede f.Kr.) [3] . I Euklids "Elementer" er det beskrevet to gange - i Bog VII for at finde den største fælles divisor af to naturlige tal [1] og i Bog X for at finde det største fælles mål for to homogene størrelser [2] . I begge tilfælde gives en geometrisk beskrivelse af algoritmen for at finde det "fælles mål" for to segmenter.

Matematikhistorikere har antydet, at det var ved hjælp af Euklids algoritme (proceduren for successiv gensidig subtraktion), at eksistensen af ​​incommensurable størrelser (sider og diagonaler af en firkant eller sider og diagonaler af en regulær femkant ) først blev opdaget i oldtiden. Græsk matematik [10] . Denne antagelse har imidlertid ikke tilstrækkelig dokumentation. En algoritme til at finde den største fælles divisor af to naturlige tal er også beskrevet i bog I af den gamle kinesiske afhandling Mathematics i ni bøger .

Beskrivelse

Euklids algoritme for heltal

Lad og være heltal, der ikke samtidigt er lig med nul, og en talfølge

er defineret ved, at hver er resten af ​​at dividere det forrige tal med det foregående, og det næstsidste er divideret med det sidste, dvs.

Så er gcd( a , b ), den største fælles divisor af a og b , lig med r n , det sidste ikke-nul-medlem af denne sekvens [11] .

Eksistensen af ​​sådanne r 1 , r 2 , …, r n , det vil sige muligheden for division med resten m med n for et hvilket som helst heltal m og heltal n ≠ 0, bevises ved induktion på m .

Rigtigheden af ​​denne algoritme følger af følgende to udsagn [12] :

I. Lad a = b ⋅ q + r , så gcd (a, b) = gcd (b, r).

1. Lad k være enhver fælles divisor for tallene a og b , ikke nødvendigvis den største, så a = t 1 ⋅ k og b = t 2 ⋅ k , hvor t 1 og t 2 er heltal fra definitionen.
2. Så er k også en fælles divisor for b og r , da b er delelig med k per definition, a (udtrykket i parentes er et helt tal, så k deler r uden en rest).
3. Det omvendte er også sandt og bevises på samme måde som punkt 2: enhver divisor af b og r er også en divisor af a og b .
4. Derfor er alle fælles divisorer for talparrene ( a , b ) og ( b , r ) de samme. Der er med andre ord ingen fælles divisor af tal ( a , b ), der ikke også er en divisor af ( b , r ), og omvendt.
5. Især den største fælles divisor forbliver den samme, da det antages, at gcd ( a , b ) > gcd ( b , r ) eller gcd ( a , b ) < gcd ( b , r ) modsigelser opnås, derfor opnås gcd ( a ) , b ) = gcd ( b , r ). Q.E.D.

II. gcd( r , 0) = r for enhver ikke-nul r (fordi 0 er delelig med et hvilket som helst heltal).

Euklids geometriske algoritme

Lad to segmenter af længden a og b være givet . Træk det mindre segment fra det større segment og erstat det større segment med den resulterende forskel. Vi gentager denne operation, idet vi trækker det mindre segment fra det større segment, indtil segmenterne bliver lige store. Hvis dette sker, er de oprindelige segmenter kommensurable , og det sidst opnåede segment er deres største fælles mål. Hvis der ikke er nogen fælles målestok, så er processen uendelig. I denne form er algoritmen beskrevet af Euclid [2] og implementeres ved hjælp af et kompas og en straightedge .

Eksempel

For at illustrere vil den euklidiske algoritme blive brugt til at finde gcd a = 1071 og b = 462. Til at begynde med trækker vi et multiplum af 462 fra 1071, indtil vi får en forskel mindre end 462. Vi skal trække 462 fra to gange, ( q 0 = 2), tilbage med en rest på 147:

Derefter trækker vi et multiplum af 147 fra 462, indtil vi får en forskel på mindre end 147. Vi skal trække 147 fra tre gange ( q 1 = 3), der er tilbage med en rest på 21:

Derefter trækker vi et multiplum af 21 fra 147, indtil vi får en forskel mindre end 21. Vi skal trække 21 fra syv gange ( q 2 = 7), uden at efterlade nogen rest:

Således vil sekvensen a > b > r 1 > r 2 > r 3 > ... > r n i dette særlige tilfælde se således ud:

Da den sidste rest er nul, slutter algoritmen med 21 og gcd(1071, 462) = 21.

I tabelform var trinene som følger:

Hvis det er påkrævet at finde gcd for mere end to tal, er algoritmen ens, ved hvert trin erstattes alle tal undtagen de mindste af rester modulo de mindste. Ingen rester, hvis nogen, er streget over. Algoritmen slutter, når der er et ikke-nul tal tilbage, dette er GCD.

Ansøgninger

Udvidet Euklids algoritme og Bezouts relation

Formlerne for kan omskrives som følger:

Her er s og t heltal. Denne repræsentation af den største fælles divisor kaldes Bezout-forholdet , og tallene s og t  er Bezout-koefficienterne [13] . Bezouts relation er nøglen i beviset for Euklids lemma og aritmetikkens grundlæggende sætning .

Fortsat brøker

Euklids algoritme er ret nært beslægtet med fortsatte fraktioner [6] . Relationen a / b kan repræsenteres som en fortsat brøk:

I dette tilfælde er den fortsatte brøkdel uden det sidste led lig med forholdet mellem Bezout-koefficienter t / s , taget med et minustegn:

Rækkefølgen af ​​ligheder, der definerer Euklids algoritme, kan omskrives i formen:

Det sidste led på højre side af en ligning er altid lig med det reciproke af venstre side af den følgende ligning. Derfor kan de to første ligninger kombineres i formen:

Den tredje lighed kan bruges til at erstatte nævneren af ​​udtrykket r 1 / r 0 , vi får:

Det sidste forhold mellem rester r k / r k −1 kan altid erstattes med den næste lighed i sekvensen, og så videre indtil den sidste ligning. Resultatet er en fortsat fraktion:

I ovenstående eksempel blev GCD(1071, 462) beregnet, og kvotienterne q k blev fundet at være henholdsvis 2, 3 og 7. Derfor kan 1071/462 skrives som:

Lineære diofantiske ligninger

En diofantligning  er en ligning med heltalskoefficienter og med en eller flere variable, og opgaven er kun at finde dens heltalsrødder. En sådan ligning kan have et uendeligt antal løsninger, et begrænset antal løsninger eller slet ingen. Den enkleste diophantinske ligning er lineær med to ubekendte:

hvor a , b , c  er heltal. Ved hjælp af den euklidiske algoritme kan en komplet løsning til en ligning af denne type findes [5] . Først ved hjælp af denne algoritme kan du bestemme d = gcd( a , b ). Derefter, ved hjælp af den udvidede Euclid-algoritme, bestemmes k og l således , at:

Det vil sige, x \u003d k og y \u003d l  er en særlig løsning på ligningen for c \u003d d . Det viser sig, at hvis c = q⋅d , så er x = q⋅k , y = q⋅l  en bestemt løsning af den oprindelige ligning, da:

Omvendt, hvis der er mindst én løsning til ligningen, så er c et multiplum af d . Dette følger af, at d deler både a og b (og dermed hele venstre side), så den skal også dele c (højre side). Således har en lineær diofantligning mindst én løsning, hvis og kun hvis c er et multiplum af gcd( a , b ).

Variationer og generaliseringer

Euklidisk ring

Ringe , hvori den euklidiske algoritme er anvendelig, kaldes euklidiske ringe [14] . Disse omfatter især ringe af heltal og ringe af polynomier .

Generaliseret Euklids algoritme for polynomier

Euklids algoritme og den udvidede Euklids algoritme generaliserer naturligt til ringen af ​​polynomier k [ x ] i én variabel over et vilkårligt felt k , da division med resten er defineret for sådanne polynomier. Når man udfører Euclid-algoritmen for polynomier, på samme måde som Euclid-algoritmen for heltal, opnås en polynomisk residualsekvens (PRS) [15] .

Lad cont(f) per definition være gcd af polynomiets koefficienter fra  indholdet af polynomiet. Kvotienten for at dividere f(x) med cont(f) kaldes den primitive del af polynomiet f(x) og betegnes primpart(f(x)). Disse definitioner vil være nødvendige for at finde GCD af to polynomier p 1 (x) og p 2 (x) i ringen . For polynomier over heltal gælder følgende:

NIK NIK

NIK NIK

Således er problemet med at finde gcd af to vilkårlige polynomier reduceret til problemet med at finde gcd for primitive polynomier.

Lad der være to primitive polynomier p 1 (x) og p 2 (x) fra Z[x], for hvilke forholdet mellem deres potenser er opfyldt: deg(p 1 (x)) = m og deg(p 2 (x) ) = n, m > n. Delingen af ​​polynomier med en rest indebærer den nøjagtige delelighed af den højeste koefficient af udbyttet med den højeste koefficient af divisoren; i det generelle tilfælde kan division med en rest ikke udføres. Derfor introduceres en pseudo-delingsalgoritme, som alligevel giver mulighed for at opnå en pseudokvotient og en pseudo-rest (prem), som selv vil tilhøre mængden af ​​polynomier over heltal.

Med pseudo-division mener vi, at selve divisionen er forudgået af multiplikationen af ​​polynomiet med , dvs.

hvor og  er henholdsvis den pseudopartielle og pseudoresidue.

Så, og desuden . Så består Euklids algoritme af følgende trin:

1. Beregning af GCD-indhold:

GCD .

2. Beregning af primitive dele:

3. Opbygning af en sekvens af polynomierester:

4. Returner resultat:

Hvis , så returner , ellers returner .

Accelererede versioner af algoritmen

• En af metoderne til at fremskynde Euclid-heltalsalgoritmen er at bruge den symmetriske rest [16] :

• En version af den accelererede euklidiske algoritme for polynomier er baseret på det faktum, at algoritmens mellemværdier hovedsageligt afhænger af høje potenser. Anvendelsen af ​​" del og hersk "-strategien gør det muligt at reducere den asymptotiske kompleksitet af algoritmen [16] .

Beregningsmæssig kompleksitet af algoritmen

Den beregningsmæssige kompleksitet af Euclid-algoritmen er blevet fuldt ud undersøgt. [17] Denne kompleksitet kan beskrives som produktet af antallet af divisionstrin, der kræves af algoritmen gange beregningskompleksiteten af ​​et trin. Den første kendte analyse af Euklids algoritme blev foreslået af Reinaud i 1811. [18] Han viste, at antallet af trin i algoritmen for et talpar ( u , v ) er begrænset til v . Han forbedrede senere bundet til v /2 + 2. Émile Léger, i 1837, studerede det værste tilfælde, når successive Fibonacci-tal indlæses for at beregne gcd . [19] Så, i 1841, viste Pierre Joseph Fink [20] at antallet af trin i algoritmen ikke overstiger 2 log 2  v  + 1. Derfor kører algoritmen i polynomiel tid på størrelsen af ​​den mindste af parret af tal ( u , v ). [19] Finks analyse blev forfinet af Gabriel Lame i 1844. [21] Han viste, at antallet af trin, der kræves for at fuldføre algoritmen, ikke er mere end fem gange h  , antallet af cifre i decimalrepræsentationen af ​​det mindste af talparret ( u , v ). [22] [23]

Når GCD beregnes for tal, der passer i ét maskinord , tager hvert trin i algoritmen konstant tid. I dette tilfælde tyder Lames analyse på, at den beregningsmæssige kompleksitet er estimeret til at være O ( h ). I en beregningsmodel, der er egnet til beregninger med tal større end ét maskinord, kan estimatet af kompleksiteten ved at beregne en rest være O ( h 2 ). [24] I dette tilfælde kan den samlede tid for alle trin i algoritmen analyseres ved hjælp af teleskopserien , hvilket viser, at den også er O ( h 2 ). For at fremskynde Euclid-algoritmen kan moderne algoritmiske metoder baseret på Schönhage-Strassen-metoden til hurtig heltalsmultiplikation anvendes. Dette fører til kvasi-polynomisk tid . [25]

Antal trin

Antallet af trin til beregning af gcd af to naturlige tal a og b er angivet som T ( a ,  b ). Hvis g  er den største fælles divisor af a og b , så er a  =  mg og b  =  ng for to coprimtal m og n . Så T ( a , b ) = T ( m , n ) , hvilket kan ses, hvis vi dividerer ligningerne opnået ved udregning af gcd for parret ( a ,  b ) med g . [26] Ved at bruge samme princip forbliver antallet af trin i algoritmen uændret, hvis a og b ganges med en fælles faktor w , som svarer til T ( a , b ) = T ( wa , wb ). Derfor kan antallet af trin T variere meget mellem tilstødende talpar, såsom ( a ,  b ) og ( a ,  b+1 ), da denne værdi afhænger af gcd.

Euklid-algoritmens rekursive karakter giver følgende ligning T ( a , b ) = 1 + T ( b , r 0 ) = 2 + T ( r 0 , r 1 ) = … = N + T ( r N −2 , r N −1 ) = N + 1 , hvor T ( x , 0) = 0 ved antagelse. [17]

Worst case

Hvis Euklids algoritme kræver N trin for et par naturlige tal a  >  b  > 0, er de mindste værdier af a og b , som dette gælder for, henholdsvis Fibonacci-tallene F N +2 og F N +1 . [27] Så, hvis Euklids algoritme kræver N trin for et par tal ( a , b ), hvor a  >  b , gælder følgende uligheder a  ≥  F N +2 og b  ≥  F N +1 . Dette kan bevises ved matematisk induktion . Hvis N  = 1, så er a deleligt med b uden en rest. De mindste naturlige tal, for hvilke dette er sandt, er b  = 1 og a  = 2, henholdsvis F 2 og F 3 . Antag nu, at resultatet gælder for alle værdier af N op til M  − 1. Det første trin i den euklidiske algoritme med M trin er a  =  q 0 b  +  r 0 , og den euklidiske algoritme for talparret ( b , r 0 ), hvor b  >  r 0 , kræver M  − 1 trin. Ved induktionshypotesen har vi b  ≥  FM +1 og r 0  ≥  FM . Derfor er a  =  q 0 b  +  r 0  ≥  b  +  r 0  ≥  FM +1  +  F M  =  FM +2 , hvilket er den ønskede ulighed. Dette bevis, udgivet af Gabriel Lame i 1844, repræsenterer begyndelsen på teorien om beregningsmæssig kompleksitet , [28] og også den første praktiske anvendelse af Fibonacci-tal . [27]

Lames sætning

Antallet af divisioner med en rest i processen med at anvende Euklid-algoritmen overstiger ikke fem gange antallet af cifre i et mindre tal skrevet i decimalsystem [29] .

Gennemsnit

Der er forskellige måder at beregne det gennemsnitlige antal trin i en algoritme. Den første beregningsmetode er den gennemsnitlige tid T ( a ), der kræves for at beregne gcd af et givet tal a og et mindre naturligt tal b , valgt med lige stor sandsynlighed fra heltal fra 0 til a  − 1. [17]

Men da T ( a , b ) svinger meget med gcd af de to tal, er den gennemsnitlige funktion T ( a ) også støjende. [30] For at reducere denne støj tages et andet gennemsnit τ ( a ) over alle tal relativt primtal til a .

hvor φ ( a ) er Euler-funktionen . Dette gennemsnit vokser jævnt efterhånden som et stiger . [31]

Konstanten (Porters konstant [32] ) i denne formel er , og ε er infinitesimal .

Den tredje middelværdi Y ( n ) er defineret som det gennemsnitlige antal trin, der kræves, når a og b er valgt tilfældigt ( ensartet fordelt ) fra 1 til n .

Beregningsmæssig kompleksitet af et trin

Ved hvert trin i den euklidiske algoritme beregnes koefficienten q k og resten r k for et givet par heltal r k −2 og r k −1 . Disse mængder er relateret af følgende relation:

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

Den beregningsmæssige kompleksitet af hvert trin er hovedsageligt relateret til at finde q k , da den resterende r k hurtigt kan beregnes ved hjælp af r k −2 , r k −1 og q k

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

Den beregningsmæssige kompleksitet af operationen med at dividere antallet af størrelse h bits estimeres som O ( h ( ℓ +1)), hvor ℓ er størrelsen af ​​kvotienten. [24]

Til sammenligning kan den originale Euklidiske algoritme, ved hjælp af subtraktion, være meget langsommere. I de fleste tilfælde er koefficienten q k et lille tal. Sandsynligheden for en given kvotient q er omtrent lig med ln| u /( u  − 1)|, hvor u  = ( q  + 1) 2 . [33] For at illustrere er sandsynligheden for en kvotient 1, 2, 3 eller 4 ca. henholdsvis 41,5 %, 17,0 %, 9,3 % og 5,9 %. Da subtraktion er hurtigere end division, især for tal større end ét ord, [34] Euklids algoritme, der bruger subtraktion, kan være mere konkurrencedygtig end algoritmen, der bruger division. [35] Dette bruges i den binære algoritme til beregning af gcd . [36]

Algoritmens kompleksitetsestimat beregnes som produktet af antallet af trin og den tid, det tager at gennemføre et trin. Den viser, at Euklids algoritme vokser kvadratisk O ( h 2 ), hvor h  er det gennemsnitlige antal cifre i de to begyndelsestal a og b i decimalnotation. Lad h 0 , h 1 , …, h N −1 repræsentere antallet af cifre i på hinanden følgende rester r 0 ,  r 1 , …,  r N −1 . Da antallet af trin N vokser lineært med h , er køretiden begrænset af følgende udtryk:

Noter

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. Matematiske konstruktioner og programmering. - M., Nauka , 1978. - Oplag 100.000 eksemplarer. — c. 170
24. ↑ 1 2 Knuth, 1997 , s. 257-261.
25. ↑ Møller, 2005 , s. en.
26. ↑ Ore, 1948 , s. 45.
27. ↑ 1 2 Knuth, 1997 , s. 343.
28. ↑ LeVeque, 1996 , s. 3.
29. ↑ Abramov S. A. Matematiske konstruktioner og programmering. - M., Nauka, 1978. - Oplag 100.000 eksemplarer. — c. 170
30. ↑ Knuth, 1997 , s. 353.
31. ↑ Tonkov, 1974 , s. 47-57.
32. ↑ Weisstein, Eric W. Porter's Constant  på Wolfram MathWorld -webstedet .
33. ↑ Knuth, 1997 , s. 352.
34. ↑ Wagon, 1999 , s. 335-336.
35. ↑ Cohen, 1993 , s. fjorten.
36. ↑ Cohen, 1993 , s. 14-15, 17-18.

Litteratur

• Abramov S. A. Den mest berømte algoritme // Kvant / red. A. L. Semenov , A. A. Gaifullin - MIAN , 1985. - vol. 11. - S. 44-46. — ISSN 0130-2221
• Vinogradov I.M. Grundlæggende om talteori . - M. - L. : GITTL, 1952. - 180 s. - ISBN 978-5-811-40535-0 .
• Kaluzhin L. A. Den grundlæggende sætning for aritmetik. — Populære Forelæsninger om Matematik . - M . : Nauka, 1969. - 33 s.
• Knut D. E. Kunsten at programmere. - Williams, 2001. - T. 2. - 829 s. — ISBN 5-8459-0081-6 .
• Courant R., Robbins G. Supplement til kapitel I, § 4. // Hvad er matematik?  - 3. udg., Rev. og yderligere - M. , 2001. - 568 s. - ISBN 5-900916-45-6 .
• Kurosh A. G. Forelæsninger om generel algebra / red. O. N. Golovin - 2. udg. — M .: Nauka , 1973. — 400 s. — ISBN 978-5-8114-0617-3
• Euklids begyndelse / oversat fra græsk. og komm. D. D. Mordukhai-Boltovsky, red. Vygodsky M. Ya. og Veselovsky I. N. - GITTL, 1949. - T. 2. - 511 s.
• Pankratiev EV Elementer af computer algebra. - INTUIT, 2007. - 217 s. - ISBN 978-5-955-60099-4 .
• Tikhomirov VM Store matematikere fra fortiden og deres store teoremer. — 2. udg., rettet. - MTsNMO , 2003. - 16 s. — ISBN 5-94057-110-7 .
• Hasse G. Forelæsninger om talteori. - Ed. udenlandsk litteratur, 1953. - 527 s.
• Zeiten GG Matematikkens historie i antikken og i middelalderen. - GTTI, 1932. - 232 s.
• Engeler E. Elementær matematiks metamatematik. — M .: Mir, 1987. — 128 s.
• Cohen H. Et kursus i beregningsmæssig algebraisk talteori . - 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. Om antallet af divisioner i at finde en GCD  //  The American Mathematical Monthly. - 1924. - Bd. 31 , udg. 9 . - S. 443 . - doi : 10.2307/2298146 . — .
• Knuth D.E. Kunsten at programmere computer . - 3. - Addison-Wesley, 1997. - V. 2: Seminumeriske algoritmer. — 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  (fransk) . Comptes Rendus Acad. Sci., 1844. - Nr. 19 .
• LeVeque WJ Fundamentals of Number Theory  (engelsk) . - Dover, 1996. - ISBN 0-486-68906-9 .
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. - CRC-Press, 1996. - 816 s. - (Diskret matematik og dens anvendelser). - ISBN 0-8493-8523-7 .
• Møller Niels. Mathematics of Computing  (engelsk) . - 2005.
• Ore O. Talteori og dens historie  (engelsk) . - McGraw-Hill, 1948.
• Shallit J. Oprindelsen af ​​analysen af ​​den euklidiske algoritme  (engelsk)  // Historia Math .. - 1994. - Vol. 21 . - doi : 10.1006/hmat.1994.1031 .
• Tonkov T. Om den gennemsnitlige længde af endelige fortsatte fraktioner  (engelsk)  // Acta Arithmetica. - 1974. - Bd. 26 .
• Wagon S. Mathematica i aktion  . - Springer-Verlag, 1999. - ISBN 0-387-98252-3 .

Links

• Implementering af Euclid-algoritmen i Pascal

• Euklids algoritme på e-maxx.ru
• Implementering af den udvidede euklidiske algoritme i C

Ordbøger og encyklopædier	Flot dansk Fantastisk norsk Stor russer kroatisk Britannica (online) Brockhaus
I bibliografiske kataloger	GND : 4659898-4