Algoritmul lui Euclid

Animaţie ce prezintă algoritmul lui Euclid pentru numerele 252 şi 105. Barele reprezintă unităţile de 21, cel mai mare divizor comun (CMMDC). La fiecare pas, numărul mai mic este scăzut din cel mai mare, până când unul dintre numere ajunge să fie zero. Celălalt este CMMDC.

În matematică, algoritmul lui Euclid este o metodă eficientă de calcul al celui mai mare divizor comun (CMMDC). El este denumit după matematicianul grec Euclid, care l-a descris în Cărţile VII şi X din Elementele.[1]

CMMDC al două numere este cel mai mare număr care le divide pe ambele. Algoritmul lui Euclid se bazează pe principiul că cel mai mare divizor comun al două numere nu se modifică dacă numărul cel mai mic este scăzut din cel mai mare. De exemplu, 21 este CMMDC al numerelor 252 şi 105 (252 = 21 × 12; 105 = 21 × 5); întrucât 252 − 105 = 147, CMMDC al lui 147 şi 105 este tot 21. Cum cel mai mare dintre cele două numere este redus, repetarea acestui proces dă numere din ce în ce mai mici, până când unul dintre ele este 0. Când se întâmplă aceasta, CMMDC este celălalt număr, cel nenul. Inversând paşii algoritmului lui Euclid, CMMDC se poate exprima sub formă de suma celor două numere iniţiale, fiecare înmulţite cu un întreg pozitiv sau negativ, de exemplu: 21 = 5 × 105 + (−2) × 252. Această proprietate importantă se numeşte identitatea lui Bézout.

Prima descriere rămasă a algoritmului lui Euclid este lucrarea lui Euclid intitulată Elementele (c. 300 î.e.n.), fiind unul dintre cei mai vechi algoritmi numerici încă utilizaţi. Algoritmul original a fost descris doar pentru numere naturale şi lungimi geometrice (numere reale), dar algoritmul a fost generalizat în secolul al XIX-lea şi la alte tipuri de numere, cum ar fi întregii Gaussieni şi polinoamele de o variabilă. Aceasta a dus la noţiuni moderne de algebră abstractă, cum ar fi domeniile euclidiene. Algoritmul lui Euclid s-a generalizat şi pentru alte structuri matematice, cum ar fi nodurile şi polinoamele multivariate.

Algoritmul lui Euclid are numeroase aplicaţii practice şi teoretice. Este un element cheie al algoritmului RSA, o metodă de criptare cu chei publice des folosită în comerţul electronic. Este utilizat pentru rezolvarea ecuaţiile diofantice, cum ar fi calcularea numerelor care satisfac mai multe congruenţe (Teorema chinezească a resturilor) sau inversul multiplicativ al unui corp. Algoritmul lui Euclid poate fi utilizat pentru a construi fracţii continue, în metoda lanţului Sturm pentru găsirea rădăcinilor reale ale unui polinom, şi în mai mulţi algoritmi moderni de factorizare a întregilor. În fine, este o unealtă de bază pentru demonstrarea unor teoreme din teoria modernă a numerelor, cum ar fi teorema celor patru pătrate a lui Lagrange şi teorema fundamentală a aritmeticii (factorizarea unică).

Algoritmul lui Euclid calculează eficient CMMDC a două numere oricât de mari sunt, deoarece nu necesită niciodată mai mult decât de cinci ori numărul de cifre (în bază 10) al celui mai mic întreg. Gabriel Lamé a demonstrat aceasta în 1844, marcând începutul teoriei complexităţii computaţionale. În secolul al XX-lea s-au dezvoltat metode de îmbunătăţire ale eficienţei algoritmului.

Bazele

Cel mai mare divizor comun

Algoritmul lui Euclid calculează cel mai mare divizor comun (CMMDC) al două numere naturale a şi b. Cel mai mare divizor comun g este cel mai mare număr natural care îi divide pe a şi pe b. Cel mai mare divizor comune este adesea scris ca CMMDC(ab) sau, mai simplu, ca (ab),[2] deşi a doua notaţie matematică este utilizată şi pentru alte concepte matematice, cum ar fi vectorii bidimensionali sau intervalele deschise.

Dacă CMMDC(ab) = 1, atunci a şi b sunt prime între ele.[3] Această proprietate nu depinde de primalitatea lui a şi a lui b.[4] De exemplu, numerele 6 şi 35 nu sunt numere prime, deoarece ambele au doi factori: 6 = 2 × 3 şi 35 = 5 × 7. Cu toate acestea, 6 şi 35 sunt prime între ele. Niciun alt număr natural în afară de 1 nu divide şi pe 6 şi pe 35, deoarece ele nu au niciun factor prim în comun.

Un dreptunghi 24-pe-60 acoperit cu zece pătrate 12-pe-12, în care 12 este CMMDC al numerelor 24 şi 60. Mai general, un dreptunghi de a-pe-b poate fi acoperit din pătrate cu latura de c doar dacă c este divizor comun al lui a şi b.

Fie g = CMMDC(ab). Cum a şi b sunt multipli ai lui g, ele pot fi scrise sub forma a = mg şi b = ng, şi nu există niciun număr mai mare G > g pentru care aceasta să fie adevărată. Numerele naturale m şi n trebuie să fie prime între ele, deoarece orice factor comun poate fi scos din m şi n pentru a-l face pe g mai mare. Astfel, orice alt număr c care divide şi pe a şi pe b trebuie să-l dividă şi pe g. Cel mai mare divizor comun g al lui a şi b poate fi definit ca divizorul comun care este divizibil cu orice alt divizor comun c.[5]

CMMDC poate fi vizualizat după cum urmează.[6] Fie o suprafaţă dreptunghiulară a pe b, şi orice divizor comun c care divide pe a şi pe b. Laturile dreptunghiului pot fi divizate în segmente de lungime c, ceea ce împarte dreptunghiul în pătrate de latură c. Cel mai mare divizor comun g este cea mai mare valoare a lui c pentru care acest lucru este posibil. Pentru ilustrare, o suprafaţă dreptunghiulară de 24-pe-60 se poate diviza în pătrate de: 1-pe-1, 2-pe-2, 3-pe-3, 6-pe-6 sau 12-pe-12. Deci 12 este cel mai mare divizor comun al lui 24 şi 60. O suprafaţă dreptunghiulară 24-pe-60 poate fi împărţită într-un grid de 12-pe-12 pătrate, cu două pătrate pe o latură (24/12 = 2) şi cinci pătrate pe cealaltă (60/12 = 5).

CMMDC al două numere a şi b se poate defini ca produsul factorilor primi comuni ai celor două numere.[7] De exemplu, întrucât 462 se factorizează în 2 × 3 × 7 × 11 şi 1071 se factorizează în 3 × 3 × 7 × 17, cel mai mare divizor comun al lui 462 şi 1071 este egal cu 21 = 3 × 7, produsul factorilor lor primi comuni. Dacă nouă numere nu au factori primi în comun, cel mai mare divizor comun al lor este 1—ele sunt prime între ele. Un avantaj important al algoritmului lui Euclid este că el poate găsi CMMDC eficient fără să trebuiască să calculeze factorii primi.[8][9] Factorizarea numerelor întregi mari este considerată a fi o problemă atât de dificilă încât multe sisteme criptografice moderne se bazează pe ea.[10]

O definiţie mai subtilă a CMMDC este utilă în matematica avansată, în particular în teoria inelelor.[11] Cel mai mare divizor comun g  al două numere a şi b este şi cel mai mic multiplu întreg al lor, adică cel mai mic număr de forma ua + vb unde u şi v sunt numere întregi. Rezultă că mulţimea multiplilor întregi ai lui a şi b (mulţimea numerelor de forma ua + vb) este aceeaşi cu mulţimea multiplilor întregi ai lui g (mg, unde m este întreg). În limbajul matematic modern, Idealul format de a şi b este ideal principal generat de g. Echivalenţa acestei definiţii a CMMDC cu celelalte definiţii este descrisă mai jos.

CMMDC al trei sau mai multe numere este egal cu produsul factorilor primi comuni ai tuturor celor trei numere,[12] care poate fi calculat luând CMMDC pe perechi de numere.[13] For example,

CMMDC(abc) = CMMDC(a, CMMDC(bc)) = CMMDC(CMMDC(ab), c) = CMMDC(CMMDC(ac), b).

Astfel, algoritmul lui Euclid care calculează CMMDC al doi întregi este suficient pentru a calcula CMMDC al oricât de mulţi întregi.

Inducţie, recursivitate şi coborâre infinită

Trei metode matematice sunt utilizate mai jos: inducţia, recursivitatea şi coborârea infinită. Inducţia[14] este utilizată adesea pentru a demonstra o teoremă pentru toate numerele naturale n.[15] Această abordare începe prin a arăta că, dacă teorema este valabilă pentru n, ea este valabilă şi pentru n + 1. Astfel, dacă teorema este valabilă pentru un singur caz (de regulă, n = 1), ea este valabilă pentru toate numerele mai mari (n = 2, 3, etc.). Recursivitatea unei ecuaţii[16] este proprietatea ei de a lega numerele ce formează un şir a1a2a3, etc.[17] Al n-lea termen al şirului, an, este adesea exprimat în funcţie de alţi termeni ai şirului, cum ar fi an−1. De exemplu, numerele Fibonacci sunt definite recursiv; fiecare termen este suma celor doi termeni precedenţi: Fn = Fn−1 + Fn−2. Mai multe ecuaţii asociate cu algoritmul lui Euclid sunt recursive. În fine, în coborârea infinită,[18] o soluţie dată în numere naturale este utilizată pentru a construi o soluţie cu numere naturale mai mici.[19] Soluţiile, însă, nu se pot micşora nelimitat, deoarece există un număr finit de numere naturale mai mici ca numerele naturale iniţiale. Astfel, fie soluţia originală era imposibilă, fie construcţia unor soluţii mai mici trebuie să se termine. Acest din urmă argument este folosit pentru a arăta că algoritmul lui Euclid pentru numere naturale trebuie să se termine într-un număr finit de paşi.[20]

Descriere

Procedură

Algoritmul lui Euclid este iterativ, adică răspunsul se găseşte după un număr de paşi; rezultatul fiecărui pas este utilizat ca punct de început pentru pasul următor.[21] Fie k un întreg care numără paşii algoritmului, începând cu zero. Astfel, pasul iniţial corespunde lui k = 0, pasul următor corespunde lui k = 1, şi aşa mai departe.

Fiecare pas începe cu două resturi nenegative rk−1 şi rk−2. Întrucât algoritmul asigură că resturile scad la fiecare pas, rk−1 este mai mic decât predecesorul sau rk−2. Scopul pasului k este găsirea câtului qk şi a restului rk astfel încât să fie satisfăcută ecuaţia:

rk−2 = qk rk−1 + rk

unde rk < rk−1. Cu alte cuvinte, multiplii celui mai mic număr rk−1 sunt scăzuţi din numărul mai mare rk−2 până când restul este mai mic decât rk−1.

În pasul iniţial (k = 0), resturile r−2 şi r−1 sunt chiar a şi b, numerele al căror CMMDC este căutat. În pasul următor (k = 1), resturile sunt b şi restul r0 al pasului iniţial, şi aşa mai departe. Astfel, algoritmul poate fi scris ca o secvenţă de ecuaţii

a = q0 b + r0
b = q1 r0 + r1
r0 = q2 r1 + r2
r1 = q3 r2 + r3

Dacă a este mai mic decât b, primul pas al algoritmului schimbă numerele între ele. De exemplu, dacă a < b, câtul iniţial q0 este zero, iar restul r0 este a. Astfel, rk este mai mic decât predecesorul său rk−1 pentru orice k ≥ 0.

Întrucât resturile scad la fiecare pas dar nu pot fi niciodată negative, un rest rN trebuie în cele din urmă să fie zero, moment în care algoritmul se opreşte.[20] Ultimul rest nenul rN−1 este cel mai mare divizor comun al lui a şi b. Numărul N nu poate fi infinit deoarece există doar un număr finit de numere nenegative intregi între restul iniţial r0 şi zero.

Demonstraţia corectitudinii

Corectitudinea algoritmului lui Euclid se poate demonstra în doi paşi.[22] La primul pas, se arată că ultimul rest nenul rN−1 divide atât pe a cât şi pe b. Cum este divizor comun, el trebuie să fie mai mic sau egal cu cel mai mare divizor comul g. În al doilea pas, se arată că orice divizor comun al lui a şi b, inclusiv g, trebuie să-l dividă pe rN−1; deci, g trebuie să fie mai mic sau egal cu rN−1. Aceste două concluzii sunt inconsistente doar dacă rN−1 nu este egal cu g.

Pentru a demonstra că rN−1 divide şi pe a şi pe b (primul pas), rN−1 divide predecesorul său rN−2

rN−2 = qN rN−1

întrucât ultimul rest rN este zero. rN−1 divide şi pe următorul său predecesor rN−3

rN−3 = qN−1 rN−2 + rN−1

deoarece el divide ambii termeni ai părţii drepte a ecuaţiei. Iterând acelaşi argument, rN−1 divide toate celelalte resturi, inclusiv pe a şi pe b. Niciunul din resturile anterioare rN−2, rN−3, etc. nu divid pe a şi pe b, deoarece toate lasă un rest nenul. Cum rN−1 este un divizor comun al lui a şi b, rN−1 ≤ g.

În al doilea pas, orice număr natural c care divide pe a şi pe b (cu alte cuvinte, orice divizor comun al lui a şi b) divide resturile rk. Prin definiţie, a şi b pot fi scrise ca multipli de c: a = mc şi b = nc, unde m şi n sunt numere naturale. Deci c divide restul iniţial r0, întrucât r0 = a − q0b = mc − q0nc = (m − q0n)c. O demonstraţie analogă arată că c divide şi celelalte resturi r1, r2, etc. Deci cel mai mare divizor comun g divide rN−1, de unde rezultă că g ≤ rN−1. Întrucât în prima parte a demonstraţiei s-a arătat că (rN−1 ≤ g), rezultă că g = rN−1. Deci g este cel mai mare divizor comun al tuturor perechilor succesive:[23][24]

g = CMMDC(a, b) = CMMDC(b, r0) = CMMDC(r0, r1) = … = CMMDC(rN−2, rN−1) = rN−1

Exemplu

Animaţie a algoritmului. Dreptunghiul verde iniţial are dimensiunile a = 1071 şi b = 462. El se împarte în pătrate de dimensiune 462×462 până rămâne un dreptunghi 462×147. Acesta e împărţit mai departe în pătrate 147×147 până rămâne un dreptunghi 21×147. Acest al treilea dreptunghi este împărţit în pătrate 21×21, şi nu rămâne niciun rest. Deci 21 este cel mai mare divizor comun al lui 1071 şi 462.

Pentru ilustrare, algoritmul lui Euclid se poate utiliza pentru a găsi cel mai mare divizor comun al lui a = 1071 şi b = 462. Pentru început, multiplii lui 462 sunt scăzuţi din 1071 până rămâne un rest mai mic decât 462. Se pot scădea doi astfel de multipli (q0 = 2), lăsând numărul 147

1071 = 2 × 462 + 147.

Apoi multiplii lui 147 sunt scăzuţi din 462 până când restul este mai mic decât 147. Trei multipli se pot scădea (q1 = 3) şi rămâne restul 21

462 = 3 × 147 + 21.

Apoi se scad multiplii lui 21 din 147 până când restul este mai mic decât 21. Se pot scădea şapte multipli (q2 = 7) şi nu rămâne niciun rest

147 = 7 × 21 + 0.

Cum ultimul rest este zero, algoritmul se termină cu 21 ca cel mai mare divizor comun al lui 1071 şi 462. Rezultatul este în concordanţă cu CMMDC(1071, 462) găsit prin factorizarea efectuată mai sus. În formă tabelară, paşii sunt:

Step k Equation Quotient and remainder
0 1071 = q0 462 + r0 q0 = 2 and r0 = 147
1 462 = q1 147 + r1 q1 = 3 and r1 = 21
2 147 = q2 21 + r2 q2 = 7 and r2 = 0; algorithm ends

Vizualizare

Algoritmul lui Euclid poate fi vizualizat în termenii analogiei pătratelor dată mai sus pentru cel mai mare divizor comun.[25] Se presupune că se doreşte acoperirea unui dreptunghi a-pe-b cu pătrate care să-l acopere exact, unde a este cel mai mare dintre cele două numere. Întâi, se încearcă împărţirea dreptunghiului în pătrate b-pe-b; aceasta lasă, însă, un dreptunghi rezidual r0-pe-b neacoperit, unde r0<b. Atunci se încearcă împărţirea dreptunghiului rezidual cu pătrate r0-pe-r0. Rămâne un al doilea dreptunghi rezidual r1-pe-r0, pe care se încearcă să fie acoperit cu pătrate r1-pe-r1, şi aşa mai departe. Şirul acesta se termină atunci când nu mai rămâne niciun dreptunghi rezidual, adică atunci când pătratele acoperă exact dreptunghiul rezidual. Lungimea laturilor celui mai mic pătrat este CMMDC al dimensiunilor dreptunghiului original. De exemplu, cel mai mic pătrat din figura alăturată este 21-pe-21 (cu roşu), iar 21 este CMMDC de 1071 şi 462, dimensiunile dreptunghiului original (verde).

Calculul câturilor şi resturilor

La fiecare pas k, algoritmul lui Euclid calculează un cât qk şi un rest rk ale două numere rk−1 şi rk−2

rk−2 = qk rk−1 + rk

unde modulul lui rk este strict mai mic decât cel al lui rk−1. Teorema împărţirii cu rest asigură că există întotdeauna acest cât şi acest rest. Teorema împărţirii cu rest a numerelor naturale spune şi că qk şi rk sunt unice, dar unicitatea lor nu este necesară pentru algoritmul lui Euclid.[26]

În versiunea originală dată de Euclid pentru acest algoritm, câtul şi restul se găsesc prin scădere repetată; adică rk−1 este scăzut din rk−2 repetat până când restul rk este mai mic decât rk−1. O abordare mai eficientă utilizează împărţirea numerelor întregi şi operaţia modulo pentru a calcula respectiv câtul şi restul. Operaţia modulo dă restul împărţirii a două numere; astfel,

rk rk−2 mod rk−1

Restul este echivalent cu clasa de congruenţă din aritmetica modulară.

Implementări

Implementările algoritmului se pot exprima în pseudocod. De exemplu, versiunea bazată pe împărţire trebuie să fie programată ca[27]

function CMMDC(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

La îneputul iteraţiei k, variabila b deţine ultimul rest rk−1, iar variabila a deţine predecesorul acesteia, rk−2. Pasul b := a mod b este echivalent cu formula recursivă de mai sus rkrk−2 mod rk−1. Variabila t reţine valoarea lui rk−1 în timp ce se calculează următorul rest rk. La sfârşitul acestei bucle de iteraţii, variabila b va păstra restul rk, iar variabila a va reţine predecesorul, rk−1.

În versiunea pe bază de scădere, definită de Euclid, calculul restului (b = a mod b) este înlocuit cu scăderea repetată.[28]

function CMMDC(a, b)
    if a = 0
       return b
    while b ≠ 0
        if a > b
           a := a − b
        else
           b := b − a
    return a

Variabilele a şi b reţin alternativ resturile anterioare rk−1 şi rk−2. Se presupune că a este mai mare ca b la începutul unei iteraţii; atunci a este egal cu rk−2, fiindcă rk−2 > rk−1. Pe parcursul acestei bucle, a este redus cu multipli ai restului anterior b până când a este mai mic ca b. Atunci a este următorul rest rk. Atunci b este redus cu multipli ai lui a până când este mai mic decât a, dând următorul rest rk+1, şi aşa mai departe.

Versiunea recursivă[29] se bazează pe egalitatea CMMDC al resturilor succesive şi pe condiţia de oprire CMMDC(rN−1, 0) = rN−1.

function CMMDC(a, b)
    if b = 0
       return a
    else
       return CMMDC(b, a mod b)

Pentru ilustrare, se calculează CMMDC(1071, 462) din CMMDC(462, 1071 mod 462) = CMMDC(462, 147). Acest al doilea CMMDC se calculează din CMMDC(147, 462 mod 147) = CMMDC(147, 21), care la rândul său se calculează din CMMDC(21, 147 mod 21) = CMMDC(21, 0) = 21.

Metoda celor mai mici resturi absolute

Într-o altă versiune a algoritmului lui Euclid, câtul de la fiecare pas este crescut cu unu dacă restul negativ rezultat este mai mic în modul decât restul pozitiv tipic.[30][31] Anterior, ecuaţia

rk−2 = qk rk−1 + rk

presupunea că rk−1 > rk > 0. Se poate, însa, calcula şi un alt rest negativ ek

rk−2 = (qk + 1) rk−1 + ek

unde rk−1 este presupus pozitiv. Dacă |ek| < |rk|, atunci rk este înlocuit de ek. După cum a arătat Leopold Kronecker, această versiune necesită cel mai mic număr de paşi dintre toate versiunile algoritmului lui Euclid.[30][31]

Istoric

Algoritmul lui Euclid a fost probabil inventat cu câteva secole înaintea lui Euclid (în imagine)

Algoritmul lui Euclid este unul dintre cei mai vechi algoritmi încă în uz.[32] El apare în Elemente (c. 300 î.e.n.), anume în Cartea 7 (Propunerile 1–2) şi în Cartea 10 (Propunerile 2–3). În Cartea 7, algoritmul este formulat pentru întregi, pe când în Cartea 10, el este formulat pentru lungimi de segmente de dreaptă. (în uz modern, s-ar spune că a fost formulat pentru numere reale. Dar lungimile, ariile şi volumele, reprezentate ca numere reale în uz modern, nu se măsoară în aceleaşi unităţi şi nu există o unitate naturală de lungime, arie sau volum, iar conceptul de numere reale nu era cunoscut la acea vreme.) Al doilea algoritm este geometric. CMMDC al două lungimi a şi b corespunde celei mai mari lungimi g care măsoară a şi b exact; cu alte cuvinte, lungimile a şi b sunt ambele multipli întregi ai lungimii g.

Algoritmul nu a fost, probabil, descoperit de Euclid, care doar a compilat rezultate ale matematicienilor dinaintea sa în lucrarea Elemente.[33][34] Matematicianul şi istoricul B. L. van der Waerden sugerează că Cartea VII derivă dintr-un manual de teoria numerelor scris de matematicieni ai şcolii lui Pitagora.[35] Algoritmul a fost probabil cunoscut lui Eudoxus din Cnidus (circa 375 î.e.n.)[36][37] Algoritmul ar putea fi dinainte chiar şi de Eudoxus,[38][39] judecând după utilizarea termenului tehnic ἀνθυφαίρεσις (anthyphairesis, scădere reciprocă) din lucrările lui Euclid şi Aristotel.[40]

După mai multe secole, algoritmul lui Euclid a fost descoperit independent în India şi în China,[41] şi a fost utilizat mai ales pentru rezolvarea de ecuaţii diofantice care apar în astronomie şi la realizarea de calendare precise. Spre sfârşitul secolului al V-lea, matematicianul şi astronomul indian Aryabhata a descris algoritmul sub numele de „pulverizatorul”,[42] poate din cauza eficienţei sale în rezolvarea de ecuaţiilor diofantice.[43] Deşi un caz special al teoremei chinezeşti a resturilor fusese deja descris de matematicianul şi astronomul chinez Sun Tzu,[44] soluţia generală a fost publicată de Qin Jiushao în cartea sa din 1247 intitulată Shushu Jiuzhang (數書九章 „Tratat matematic în nouă secţiuni”).[45] Algoritmul lui Euclid a fost descris în Europa pentru prima dată în a doua ediţie a lucrării lui Bachet Problèmes plaisants et délectables (Probleme plăcute şi delectabile, 1624).[46] În Europa, a fost folosit tot pentru rezolvarea de ecuaţii diofantice, dar şi la construcţia fracţiilor continue. Algoritmul lui Euclid extins a fost publicat de matematicianul englez Nicholas Saunderson, care i l-a atribuit lui Roger Cotes ca metodă de calcul eficient a fracţiilor continue.[47]

În secolul al XIX-lea, algoritmul lui Euclid a dus la dezvoltarea unor noi sisteme de numere, cum ar fi întregii gaussieni şi întregii eisensteinieni. În 1815, Carl Gauss a utilizat algoritmul lui Euclid pentru a demonstra factorizarea unică a întregilor gaussieni, deşi lucrarea sa a fost publicată pentru prima oară în 1832.[48] Gauss a menţionat algoritmul în Disquisitiones Arithmeticae (publicat la 1801), dar numai ca metodă pentru fracţiile continue.[49] Peter Dirichlet pare a fi fost primul care a descris algoritmul lui Euclid ca bază pentru teoria numerelor.[50] Dirichlet a observat că multe din rezultatele teoriei numerelor, cum ar fi unicitatea factorizării, sunt adevărate pentru toate celelalte sisteme de numere în care se poate aplica algoritmul lui Euclid.[51] Cursurile lui Dirichlet pe tema teoriei numerelor au fost editate şi extinse de Richard Dedekind, care a utilizat algoritmul lui Euclid pentru a studia întregii algebrici, un tip general de numere. De exemplu, Dedekind a fost primul care a demonstrat teorema celor două pătrate a lui Fermat folosind factorizarea unică a întregilor gaussieni.[52] Dedekind a definit şi conceptul de domeniu euclidian, un sistem numeric în care se poate defini o versiune generalizată a algoritmului lui Euclid. În ultimele decenii ale secolului al XIX-lea, însă, algoritmul lui Euclid a fost treptat eclipsat de teoria mai generală a lui Dedekind despre idealuri.[53]

„[Algoritmul lui Euclid] este străbunicul tuturor algoritmilor, deoarece este cel mai vechi algoritm netrivial care a supravieţuit până în ziua de azi.”

Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition (1981), p. 318.

În secolul al XIX-lea, au fost dezvoltate şi alte aplicaţii ale algoritmului lui Euclid. În 1829, Charles Sturm a arătat că algoritmul este util în metoda lanţurilor Sturm de numărare a rădăcinilor reale dintr-un interval dat ale polinoamelor.[54]

Algoritmul lui Euclid a fost prima metodă de descoperire a relaţiilor între numere întregi de acelaşi ordin de mărime. În ultimii ani, s-au mai dezvoltat câţiva alţi algoritmi noi legaţi de relaţiile între întregi, ca de exemplu algoritmul Ferguson–Forcade (1979) al lui Helaman Ferguson şi R.W. Forcade,[55] şi algoritmii asociaţi, algoritmul LLL, algoritmul HJLS şi algoritmul PSLQ.[56][57]

În 1969, Cole şi Davie au dezvoltat un joc în doi pe baza algoritmului lui Euclid, joc intitulat Jocul lui Euclid,[58] care are o strategie optimă.[59] Jucătorii încep cu două grămezi de pietre a şi b. Jucătorii elimină pe rând m multiplii ai celei mai mici grămezi din cea mai mare. Astfel, daca cele două grămezi au x respectiv y pietre, unde x este mai mare ca y, următorul jucător poate reduce grămada mai mare de la x pietre la xmy pietre, atâta vreme cât al doilea este un număr nenegativ. Câştigă primul jucător care reduce una dintre grămezi la zero pietre.[60][61]

Aplicaţii matematice

Identitatea lui Bézout

Identitatea lui Bézout spune că cel mai mare divizor comun g al două numere întregi a şi b se poate reprezenta sub formă de combinaţie liniară a primelor două numere a şi b.[62] Cu alte cuvinte, întotdeauna există două numere întregi s şi t astfel încât g = sa + tb.[63][64]

Întregii s şi t pot fi calculaţi pe baza câturilor q0, q1 etc. inversând ordinea ecuaţiilor din algoritmul lui Euclid.[65] Începând cu penultima ecuaţie, g poate fi exprimat în termeni de câtul qN−1 şi de cele două resturi anterioare, rN−2 and rN−3.

g = rN−1 = rN−3qN−1 rN−2

Acele două resturi pot fi, de asemenea, exprimate în termeni de câturile corespunzătoare lor şi de resturile anterioare,

rN−2 = rN−4qN−2 rN−3
rN−3 = rN−5qN−3 rN−4

Înlocuind aceste formule pentru rN−2 şi rN−3 în prima ecuaţie rezultă g sub formă de combinaţie liniară a resturilor rN−4 şi rN−5. Procesul de substituţie a resturilor din formulele ce implică predecesoarele lor se poate continua până când se ajunge la numerele originale a şi b

r2 = r0q2 r1
r1 = bq1 r0
r0 = aq0 b

După ce toate resturile r0, r1 etc. au fost substituite, ultima ecuaţie îl exprimă pe g sub forma unei combinaţii liniare de a şi b: g = sa + tb. Identitatea lui Bézout, şi deci şi algoritmul anterior, poate fi generalizată la contextul domeniilor euclidiene.

Idealuri principale

Identitatea lui Bézout dă o altă definiţie a celui mai mare divizor comun g al două numere a şi b.[11] Fie mulţimea tuturor numerelor de forma ua + vb, unde u şi v sunt orice două numere întregi. Cum a şi b sunt ambele divizibile cu g, toate numerele din mulţime sunt divizibile cu g. Cu alte cuvinte, toate numerele din această mulţime sunt multipli întregi ai lui g. Acest lucru este adevărat pentru orice divizor comun al lui a şi b. Spre deosebire de alţi divizori comuni, însă, cel mai mare divizor comun este şi el membru al mulţimii; din identitatea lui Bézout, alegând u = s şi v = t rezultă g. Un divizor comun mai mic nu poate fi membru al mulţimii, deoarece toate elementele mulţimii trebuie să fie divizibile cu g. Invers, orice multiplu m al lui g poate fi obţinut alegând u = ms şi v = mt, unde s şi t sunt întregii din identitatea lui Bézout. Aceasta se poate vedea înmulţind indentitatea lui Bézout cu m

mg = msa + mtb

Astfel, mulţimea tuturor numerelor ua + vb este echivalentă cu mulţimea multiplilor m ai lui g. Cu alte cuvinte, mulţimea tuturor sumelor posibile de multipli întregi ai două numere (a şi b) este echivalentă cu mulţimea multiplilor lui CMMDC(a, b). CMMDC se spune că este generator al idealului lui a şi b. Aceată definiţie pentru CMMDC a dus la unele concepte moderne din algebra abstractă, cum ar fi cel de ideal principal (un ideal generat de un singur element) şi de domeniu de ideal principal (un domeniu în care toate idealurile sunt principale).

Unele probleme se pot rezolva cu acest rezultat.[66] De exemplu, fie două ceşti de măsurare de volum a respectiv b. Adăugând sau scăzâd u multipli ai primei ceşti şi v multipli ai celei de-a doua ceşti, poate fi măsurat orice volum ua + vb. Aceste volume sunt toate multipli ai lui g = CMMDC(ab).

Algoritmul lui Euclid extins

Întregii s şi t din identitatea lui Bézout se pot calcula eficient utilizând algoritmul lui Euclid extins. Această extensie adaugă algoritmului lui Euclid două ecuaţii recursive[67]

sk = sk−2qk−1sk−1
tk = tk−2qk−1tk−1

cu valorile de început

s−2 = 1, t−2 = 0
s−1 = 0, t−1 = 1

Cu ajutorul acestei relaţii de recurenţă, întregii lui Bézout s şi t sunt daţi de s = sN şi t = tN, unde N este pasul la care algoritmul se termină cu rN = 0.

Validitatea acestei abordări se poate demonstra prin inducţie. Se presupune că formula recursivă este corectă până la pasul k−1 al algoritmului, cu alte cuvinte, se presupune că

rj = sj a + tj b

pentru orice j mai mic decât k. Al k-lea pas al algoritmului dă ecuaţia

rk = rk−2qk−1rk−1

Întrucât formula de recurenţă este considerată corectă pentru rk−2 şi rk−1, ele pot fi exprimate în funcţie de variabilele corespunzătoare s şi t

rk = (sk−2 a + tk−2 b) − qk−1(sk−1 a + tk−1 b)

Rearanjând această ecuaţie, rezultă formula de recurenţă pentru pasul k

rk = sk a + tk b = (sk−2qk−1sk−1) a + (tk−2qk−1tk−1) b

Metoda matriceală

Întregii s şi t pot fi găsiţi şi folosind o metodă echivalentă bazată pe matrice.[68] Secvenţa de ecuaţii a algoritmului lui Euclid

a = q0 b + r0
b = q1 r0 + r1
rN−2 = qN rN−1 + 0

se poate scrie ca produs al matricilor câturilor 2-pe-2 înmulţite cu un vector bidimensional al resturilor

Fie M produsul tuturor matricelor–cât

Aceasta simplifică algoritmul lui Euclid la forma

Pentru a exprima pe g sub formă de combinaţie liniară de a şi b, ambele părţi ale acestei ecuaţii pot fi înmulţite cu inversa matricei M.[68][69] Determinantul lui M este egal cu (−1)N+1, deoarece este egal cu produsul determinanţilor matricelor–cât, care sunt egale cu minus unu. Întrucât determinantul lui M nu este niciodată zero, vectorul final de resturi se poate rezolva găsind inversa lui M

Deoarece ecuaţia de sus dă

g = (−1)N+1 ( m22 am12 b)

cei doi întregi ai identităţii lui Bézout sunt s = (−1)N+1m22 şi t = (−1)Nm12. Metoda matricei este la fel de eficientă ca şi cea a formulei de recurenţă, cu două înmulţiri şi două adunări la fiecare pas al algoritmului lui Euclid.

Lema lui Euclid şi unicitatea factorizării

Identitatea lui Bézout este esenţială pentru multe aplicaţii ale algoritmului lui Euclid, cum ar fi demonstrarea unicităţii descompunerii numerelor în factori primi.[70] Pentru a ilustra aceasta, se presupune că un număr L poate fi scris ca produs de doi factori u şi v, adică L = uv. Dacă un alt număr w îl divide şi el pe L dar este prim cu u, atunci înseamnă că w îl divide pe v, pentru că, dacă cel mai mare divizor comun al lui u şi w este 1, atunci se pot găsi doi întregi s şi t astfel încât

1 = su + tw

conform identităţii lui Bézout. Înmulţind ambele părţi ale ecuaţiei cu v rezultă relaţia

v = suv + twv = sL + twv

Cum w divide ambii termeni din partea dreaptă, înseamnă că el divide şi termenul din stânga, v. Acest rezultat este cunoscut sub numele de lema lui Euclid:[71] Dacă un număr prim divide pe L, atunci el divide cel puţin unul din factorii lui L. La fel, dacă un număr w este prim cu mai multe numere a1, a2, …, an, atunci w este prime şi cu produsul lor, a1 × a2 × … × an.[72]

Lema lui Euclid este suficientă pentru a demonstra că toate numerele au o unică descompunere în factori primi.[73] Dacă se presupune contrariul, şi anume că există două factorizări independente ale lui L în m respectiv n factori primi

L = p1p2pm = q1q2qn

Întrucât toate numerele prime p divid pe L conform presupunerii, atunci fiecare dintre ele divide unul dintre factorii q; întrucât fiecare q este şi el prim, atunci înseamnă că p = q. Împărţind iterativ la factorii p rezultă că fiecare p are un corespondent q; cele două descompuneri în factori primi sunt identice cu excepţia ordinii factorilor. Factorizarea unică a numerelor în factori primi are mai multe aplicaţii în demonstraţiile matematice.

Ecuaţiile liniare diofantice

Graficul unei ecuaţii diofantice, 9x + 12y = 483. Soluţiile sunt arătate ca cercuri albastre.

Ecuaţiile diofantice sunt ecuaţii ale căror soluţii sunt neapărat numere întregi; ele îşi trag numele de la matematicianul alexandrian din secolul al III-lea Diophantus.[74] O ecuaţie diofantică liniară tipică în variabilele întregi x şi y are forma[75]

ax + by = c

unde a, b şi c sunt numere întregi date. Aceasta se poate scrie ca o ecuaţie în x de forma:

axc mod b.

Fie g cel mai mare divizor comun al lui a şi b. Ambii termeni din ecuaţia ax + by sunt divizibili cu g; deci, fie c este divizibil cu g, fie ecuaţia nu are soluţii. Împărţind ambele părţi ale ecuaţiei la c/g, ea poate fi redusă la identitatea lui Bezout

sa + tb = g

unde s şi t se pot găsi prin algoritmul lui Euclid extins.[76] Aceasta mai dă o soluţie a ecuaţiei diofantice, x1 = s (c/g) şi y1 = t (c/g).

În general, o ecuaţie diofantică liniară fie nu are soluţie, fie are un număr infinit de soluţii.[77] Pentru a demonstra cel de-al doilea caz, se consideră două soluţii, (x1y1) şi (x2y2)

ax1 + by1 = c = ax2 + by2

sau echivalent

a(x1x2) = b(y2y1).

Astfel, cea mai mică diferenţă între două soluţii x este b/g, pe când cea mai mică diferenţă între două soluţii y este a/g. Astfel, soluţiile pot fi exprimate ca

x = x1bt/g
y = y1 + at/g.

Permiţând lui t să varieze pe toată mulţimea numerelor întregi, se poate genera o familie infinită de soluţii dintr-una singură (x1y1). Dacă soluţiile trebuie să fie întregi pozitivi (x > 0, y > 0), este posibil să existe doar un număr finit de soluţii. Această restricţie asupra soluţiilor acceptabile permite rezolvarea de sisteme de ecuaţii diofantice cu un număr de ecuaţii mai mare decât cel de necunoscute;[78] aceasta este imposibilă pentru un sistem de ecuaţii liniare ale cărui soluţii pot fi orice număr real.

Inversul multiplicativ şi algoritmul RSA

Un corp finit este o mulţime de numere cu patru operaţii generice. Aceste operaţii se numesc adunare, scădere, înmulţire şi împărţire şi au proprietăţile obişnuite, cum ar fi comutativitatea, asociativitatea şi distributivitatea. Un exemplu de corp finit este mulţimea de 13 numere {0, 1, 2, …, 12} cu aritmetica modulară. În acest corp, rezultatele oricărei operaţii matematice (adunare/scădere/înmulţire/împărţire) se reduce modulo 13; adică din rezultat se scad multipli ai lui 13 până când rezultatul ajunge să fie între 0–12. De exemplu, rezultatul operaţiei 5 × 7 = 35 mod 13 = 9. Asemenea corpuri finite pot fi definite pentru orice număr prim p; utilizând definiţii mai sofisticate, se pot defini pentru orice putere m a unui număr prim p m. Corpurile finite sunt adesea numite corpuri Galois, şi sunt notate cu GF(p) sau GF(p m).

Într-un astfel de corp cu m numere, fiecare element nenul a are un invers multiplicativ unic modulo m, a−1 astfel încât aa−1 = a−1a ≡ 1 mod m. Acest invers se poate găsi rezolvând ecuaţia ax ≡ 1 mod m,[79] sau ecuaţia diofantică liniară echivalentă[80]

ax + my = 1

Această ecuaţie se poate rezolva cu ajutorul algoritmului lui Euclid, după cum s-a arătat mai sus. Găsirea inversului multiplicativ este un pas esenţial în algoritmul RSA, folosit pe scară largă în comerţul electronic; anume, ecuaţia determină întregul utilizat pentru a decripta mesajul.[81] Deşi algoritmul RSA utilizează inele şi nu corpuri, se poate folosi algoritmul lui Euclid pentru găsirea inversului multiplicativ acolo unde el există. Algoritmul lui Euclid are şi alte aplicaţii în codurile corectoare de erori; de exemplu, el se poate folosi ca alternativă la algoritmul Berlekamp–Massey pentru decodificarea codurilor BCH şi Reed–Solomon, coduri bazate pe corpuri Galois.[82]

Teorema chinezească a resturilor

Algoritmul lui Euclid se poate folosi pentru a rezolva şi mai multe ecuaţii liniare diofantice.[83] Astfel de ecuaţii apar în teorema chinezească a resturilor, care descrie o metodă nouă de reprezentare a unui întreg x. În loc de a reprezenta un număr întreg prin cifrele sale, el se poate reprezenta prin resturile xi ale împărţirii lui modulo o mulţime de N numere prime între ele mi.[84]

x1x mod m1
x2x mod m2
xNx mod mN

Scopul este determinarea lui x din cele N resturi xi. Soluţia se obţine combinând mai multe ecuaţii într-o singură ecuaţie diofantică cu un modul M mult mai mare care este produsul tuturor modulelor individuale mi, şi definind Mi

Mi = M / mi

Astfel, fiecare Mi este produsul tuturor modulelor cu excepţia lui mi. Soluţia depinde de găşirea a N noi numere hi astfel încât

Mihi ≡ 1 mod mi

Cu aceste numere hi, orice întreg x se poate reconstitui din resturile xi prin ecuaţia

x ≡ (x1M1h1 + x2M2h2 + … + xNMNhN ) mod M

Deoarece aceste numere hi sunt inversele multiplicative ale numerelor Mi, ele se pot găsi folosind algoritmul lui Euclid aşa cum s-a arătat în subsecţiunea anterioară.

Fracţii continue

Algoritmul luo Euclid este în strânsă relaţie cu noţiunea de fracţie continuă.[85] Şirul de ecuaţii poate fi scris sub forma

a/b = q0 + r0/b
b/r0 = q1 + r1/r0
r0/r1 = q2 + r2/r1
rk−2/rk−1 = qk + rk/rk−1
rN−2/rN−1 = qN

Ultimul termen din partea dreaptă este întotdeauna egal cu inversul părţii stângi din ecuaţia următoare. Astfel, primele două ecuaţii pot fi combinate formând

a/b = q0 + 1/(q1 + r1/r0)

A treia ecuaţie poate fi folosită pentru a substitui termenul de la numitor r1/r0, dând

a/b = q0 + 1/(q1 + 1/(q2 + r2/r1))

Raportul final al resturilor rk/rk−1 poate fi oricând înlocuit folosind următoarea ecuaţie din serie, până la ultima. Rezultatul este fracţia continuă

a/b = q0 + 1/(q1 + 1/(q2 + 1/(… + 1/qN))…) = [q0; q1, q2, …, qN]

În exemplul de mai sus, s-a calculat CMMDC(1071, 462), iar câturile qk erau 2, 3 şi respectiv 7. Deci fracţia 1071/462 poate fi scrisă sub forma

1071/462 = 2 + 1/(3 + 1/7) = [2; 3, 7]

după cum confirmă şi calculele.

Algoritmii de factorizare

Calculul celui mai mare divizor comun este un pas esenţial în mai mulţi algoritmi de factorizare a întregilor,[86] such as Pollard's rho algorithm,[87] algoritmul lui Shor,[88] metoda de factorizare a lui Dixon[89] şi factorizarea Lenstra cu curbe eliptice.[90] Algoritmul lui Euclid poate fi utilizat eficient pentru găsirea CMMDC în aceste cazuri. Factorizarea cu fracţii continue utilizează fracţiile continue, determinate folosind algoritmul lui Euclid.[91]

Eficienţa algoritmului

Numărul de paşi din algoritmul lui Euclid pentru CMMDC(x,y). Punctele roşii indică paşi relativ puţini (viteză mare), iar punctele galbene, verzi şi albastre indică un număr din ce în ce mai mare de paşi (viteză scăzută).

Eficienţa computaţională a algoritmului lui Euclid a fost mult studiată.[92] Această eficienţă poate fi descrisă de numărul de paşi al algoritmului înmulţit cu costul computaţional al fiecărui pas. După cum a arătat Gabriel Lamé pentru prima oară în 1844,[93] numărul de paşi necesar pentru termniarea calculului nu este niciodată mai mare decât numărul h de cifre (în baza 10) al celui mai mic număr.[94][95] Întrucât costul computaţional al fiecărui pas este şi el de ordinul lui h, costul total creşte ca h2.

Numărul de paşi

Numărul de paşi necesari pentru calculul CMMDC al două numere naturale, a şi b, se poate nota cu T(ab).[96] Dacă g este CMMDC al lui a şi b, atunci a = mg şi b = ng pentru două numere m şi n prime între ele. Atunci

T(a, b) = T(m, n)

după cum se poate vedea împărţind toţi paşii din algoritmul lui Euclid la g.[97] După acelaşi argument, numărul de paşi rămâne acelaşi dacă a şi b sunt înmulţiţi cu un factor comun w: T(a, b) = T(wa, wb). De aceea, numărul T de paşi poate varia dramatic între perechi foarte apropiate de numere, cum ar fi T(a, b) şi T(ab + 1), în funcţie de cât de mare este CMMDC în fiecare caz.

Natura recursivă a algoritmului lui Euclid dă o altă ecuaţie:

T(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1

unde se presupune că T(x, 0) = 0.[98]

Numărul maxim de paşi

Dacă algoritmul lui Euclidean se execută în N paşi pentru două numere naturale a > b > 0, cele mai mici valori ale lui a şi b pentru care acest lucru este adevărat sunt numerele Fibonacci FN+2 respectiv FN+1.[99] Aceasta se poate arăta prin inducţie.[100] Dacă N = 1, b divide a; cele mai mici numere naturale pentru care acest lucru este adevărat sunt b = 1 şi a = 2, care sunt F2 şi respectiv F3. Se presupune că rezultatul este valabil pentru toate valorile lui N până la M − 1. Primul pas al algoritmului de M paşi este a = q0b + r0, iar al doilea pas este b = q1r0 + r1. Algoritmul fiind recursiv, el a rulat M−1 paşi pentru a găsi CMMDC(br0) iar valorile lor cele mai mici sunt FM+1 şi FM. Cea mai mică valoare a lui a este deci cea cu q0 = 1, de unde a = b + r0 = FM+1 + FM = FM+2. Această demonstraţie, publicată de Gabriel Lamé în 1844, reprezintă începuturile teoriei complexităţii computaţionale,[101] fiind şi prima aplicaţie practică a şirului lui Fibonacci.[102]

Acest rezultat este suficient pentru a arăta că numărul de paşi din algoritmul lui Euclid nu poate fi niciodată mai mare decât de cinci ori numărul cifrelor sale (în bază 10).[103] Dacă algoritmul rulează în N paşi, atunci b este mai mare sau egal cu FN+1 care este mai mare sau egal cu φN, unde φ este raportul de aur. Cum b > φN, atunci N < logφb. Întrucât log10φ > 1/5, N/5 < log10φ logφb = log10b. Astfel, N < 5 log10b. Deci, algoritmul lui Euclid are nevoie întotdeauna de mai puţin decât O(h) împărţiri, unde h este numărul de cifre al celui mai mic număr b.

Numărul mediu de paşi

Numărul mediu de paşi al algoritmului lui Euclid a fost definit în trei moduri diferite. Prima definiţie este timpul mediu T(a) necesar pentru a calcula CMMDC al unui număr a şi al unui număr mai mic b ales cu probabilitate egală dintre întregii dintre 0 şi a − 1[104]

Deoarece T(ab) fluctează dramatic cu CMMDC al celor două numere, însă, funcţia T(a) este afectată de „zgomote”.[105]

Pentru a reduce aceste zgomote, se face o a doua medie τ(a) peste toate numerele prime cu a

Există φ(a) numere întregi prime cu a şi mai mici decât acesta, unde φ este indicatorul lui Euler. Această medie tau creşte uniform cu a[106][107]

τ(a) = (12/π2) ln 2 ln a + C + O(a−(1/6) + ε)

cu eroarea reziduală de ordinul lui a−(1/6) + ε, unde ε este infinitezimal. Constanta C din această formulă este egală cu

C = −(1/2) + 6 (ln 2/π2)( 4γ − 24π2ζ '(2) + 3 ln 2 − 2) ≈ 1.467

unde γ este constanta Euler–Mascheroni iar ζ' este derivata funcţiei zeta Riemann.[108][109] Coeficientul dominant (12/π2) ln 2 a fost determinat prin două metode independente.[110][111]

Întrucât prima medie se poate calcula din media tau prin sumă peste divizorii d ai lui a[112]

ea poate fi aproximată prin formula[113]

T(a) ≈ C + (12/π2) ln 2 ( ln a − Σd|a Λ(d)/d )

unde Λ(d) este funcţia Mangoldt.[114]

O a treia medie Y(n) este definită ca numărul mediu de paşi necesar atunci când a şi b sunt ambele alese aleator (cu distribuţie uniformă) între 1 şi n[113]

Înlocuind formula aproximativă pentru T(a) în această ecuaţie rezultă o estimare a lui Y(n)[115]

Y(n) ≈ (12/π2) ln 2 ln n + 0.06.

Costul computaţional al unui pas

La fiecare pas k al algoritmului lui Euclid, se calculează câtul qk şi restul rk pentru o pereche dată de întregi rk−2 şi rk−1

rk−2 = qk rk−1 + rk.

Costul computaţional al fiecărui pas este asociat cu găsirea lui qk, întrucât restul rk poate fi calculat rapid din rk−2, rk−1, and qk

rk = rk−2qk rk−1.

Costul computaţional al împărţirii numerelor pe h biţi scalează ca O(h(+1)), unde este lungimea câtului.[116]

Pentru comparaţie, algoritmul original al lui Euclid bazat pe scăderi poate fi mult mai lent. O singura împărţire de întregi este echivalentă cu q scăderi (q este câtul împărţirii). Dacă raportul a supra b este foarte mare, şi câtul este mare şi este nevoie de multe scăderi. Pe de altă parte, s-a arătat că sunt şanse mari ca aceste câturi să fie numere întregi mici. Probabilitatea ca un cât dat să aibă o anumită valoare q este aproximativ ln|u/(u − 1)| unde u = (q + 1)2.[117] Pentru ilustrare, probabilitatea ca la împărţire să rezulte câtul 1, 2, 3, sau 4 este aproximativ 41,5%, 17,0%, 9,3%, respectiv 5,9%. Întrucât operaţia de scădere este mai rapidă decât cea de împărţire, mai ales în cazul numerelor mari,[118] algoritmul lui Euclid bazat pe scăderi este competitiv cu cel bazat pe împărţiri.[119] Acest aspect este exploatat de versiunea binară a algoritmului lui Euclid.[120]

Combinarea numărului estimat de paşi cu calculul computaţional estimat al fiecărui pas arată că algoritmul lui Euclid are o creştere pătratică (h2) în funcţie de numărul de cifre h al celor două numere iniţiale a şi b. Fie h0, h1, …, hN−1 numărul de cifre ale resturilor succesive r0r1, …, rN−1. Cum numărul de paşi N creşte liniar cu h, timpul de execuţie este limitat de

Eficienţa unor metode alternative

Algoritmul lui Euclid este folosit pe scară largă în practică, mai ales pentru numere mici, datorită simplităţii sale. Pentru comparaţie, se poate determina eficienţa unor alternative la algoritmul lui Euclid.

O abordare ineficientă a găsirii CMMDC al două numere naturale a şi b este de a le calcula toţi divizorii comuni; CMMDC este, atunci, cel mai mare dintre aceştia. Divizorii comuni se pot găsi împărţind succesiv ambele numere la numerele de la 2 la cel mai mic dintre cele două, b. Numărul de paşi al acestei abordări creşte liniar cu b, sau exponenţial cu numărul de cifre. O altă abordare ineficientă este găsirea factorilor primi ai unuia sau ai ambelor numere. Aşa cum se arată mai sus, CMMDC este egal cu produsul factorilor primi comuni ai celor două numere a şi b.[7] Metodele actuale de factorizare sunt şi ele ineficiente; multe alte sisteme criptografice se bazează tocmai pe această ineficienţă.[10]

Algoritmul CMMDC binar este o alternativă eficientă care înlocuieşte împărţirea cu operaţii mai rapide, exploatând reprezentările binare utilizate de calculatoare.[121][122] Această alternativă, însă, scalează şi ea ca O(h²). Este de regulă mai rapidă pe calculatoarele reale, dar scalează la fel ca algoritmul lui Euclid.[123] Eficienţa se poate îmbunătăţi examinând doar primele cifre ale numerelor a şi b.[124][125] The binary algorithm can be extended to other bases (k-ary algorithms),[126] with up to fivefold increases in speed.[127]

O abordare recursivă pentru numere întregi foarte mari (cu peste 25.000 de cifre) conduce la algoritmi CMMDC subcuadratici,[128] cum ar fi cel al lui Schönhage,[129][130] şi cel al lui Stehlé şi Zimmermann.[131] Aceşti algoritmi exploatează forma matriceală 2×2 a algoritmului lui Euclid prezentată mai sus. Aceste metode subcuadratice scalează în general ca O(h (log h)2 (log log h)). [123][132]

Alte sisteme de numere

După cum s-a descris mai sus, algoritmul lui Euclideste folosit pentru a găsi cel mai mare divizor comun al două numere naturale (numere întregi pozitive). Acesta poate fi, însă, generalizat la numere reale, şi la sisteme de numere mai exotice, cum ar fi polinoamele, întregii cuadratici şi cuaternionii Hurwitz. În ultimele două cazuri, algoritmul lui Euclid este folosit pentru a demonstra proprietatea crucială de unicitate a factorizării, anume cea că astfel de numere pot fi factorizate în mod unic în elemente ireductibile, structuri similare numerelor prime. Unicitatea factorizării este esenţială în multe demonstraţii din teoria numerelor.

Note

  1. ^ Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications
  2. ^ Stark, p. 16.
  3. ^ Stark, p. 21.
  4. ^ LeVeque, p. 32.
  5. ^ Leveque, p. 31.
  6. ^ Grossman JW (). Discrete Mathematics. New York: Macmillan. p. 213. ISBN 0-02-348331-8. 
  7. ^ a b Schroeder, pp. 21–22.
  8. ^ Schroeder, p. 19.
  9. ^ Ogilvy CS, Anderson JT (). Excursions in number theory. New York: Oxford University Press. pp. 27–29. Library of Congress Control Number 66-14484. 
  10. ^ a b Schroeder, pp. 216–219.
  11. ^ a b Leveque, p. 33.
  12. ^ Stark, p. 25.
  13. ^ Ore, pp. 47–48.
  14. ^ Knuth, Donald E. (). The Art of Computer Programming, Volume 1: Fundamental Algorithms (ed. 3rd). Addison-Wesley. ISBN 0-201-89683-4.  (Secţiunea 1.2.1: Mathematical Induction, pp. 11–21.)
  15. ^ Rosen, pp. 18–21.
  16. ^ Rosen, pp. 21–24.
  17. ^ Anderson JA (). Discrete Mathematics with Combinatorics. Upper Saddle River, NJ: Prentice Hall. pp. 165–223. ISBN 0-13-086998-8. 
  18. ^ Rosen, p. 492.
  19. ^ Anderson JA (). Discrete Mathematics with Combinatorics. Upper Saddle River, NJ: Prentice Hall. pp. 109–119. ISBN 0-13-086998-8. 
  20. ^ a b Stark, p. 18.
  21. ^ Stark, pp. 16–20.
  22. ^ Stark, pp. 16–20.
  23. ^ Knuth, p. 320.
  24. ^ Lovász L, Pelikán J, Vesztergombi K (). Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. pp. 100–101. ISBN 0-387-95584-4. 
  25. ^ Kimberling C (). „A Visual Euclidean Algorithm”. Mathematics Teacher. 76: 108–109. 
  26. ^ Cohn, pp. 104–110.
  27. ^ Knuth, pp. 319–320.
  28. ^ Knuth, pp. 318–319.
  29. ^ Stillwell, p. 14.
  30. ^ a b Ore, p. 43.
  31. ^ a b Stewart BM (). Theory of Numbers (ed. 2nd). New York: Macmillan. pp. 43–44. Library of Congress Control Number 64-10964. 
  32. ^ Knuth, p. 318.
  33. ^ Weil A (). Number Theory. Boston: Birkhäuser. pp. 4–6. ISBN 0-8176-3141-0. 
  34. ^ Jones A (). „Greek mathematics to AD 300”. Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. pp. 46–48. ISBN 0-415-09238-8. 
  35. ^ van der Waerden BL (). Science Awakening. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd. pp. 114–115. 
  36. ^ Knuth, p. 318.
  37. ^ von Fritz K (). „The Discovery of Incommensurability by Hippasus of Metapontum”. Ann. Math. 46: 242–264. doi:10.2307/1969021. 
  38. ^ Heath TL (). Mathematics in Aristotle. Oxford Press. pp. 80–83. 
  39. ^ Fowler DH (). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. pp. 31–66. ISBN 0-19-853912-6. 
  40. ^ Becker O (). „Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid”. Quellen und Studien zur Geschichte der Mathematik B. 2: 311–333. 
  41. ^ Stillwell, p. 31.
  42. ^ Tattersall, p. 70.
  43. ^ Rosen, pp. 86–87.
  44. ^ Ore, pp. 247–248.
  45. ^ Tattersall, pp. 72, 184–185.
  46. ^ Tattersall, p. 70.
  47. ^ Tattersall, pp. 72–76.
  48. ^ Eroare la citare: Etichetă <ref> invalidă; niciun text nu a fost furnizat pentru ref-urile numite Gauss_1832
  49. ^ Stillwell, p. 31.
  50. ^ Stillwell, pp. 31–32.
  51. ^ Dirichlet, pp. 29–31.
  52. ^ Dedekind R (). „Supplement XI”. În PGL Dirichlet. Vorlesungen über Zahlentheorie. 
  53. ^ Stillwell J (). Elements of Number Theory. New York: Springer-Verlag. pp. 41–42. ISBN 0-387-95587-9. 
  54. ^ Sturm C (). „Mémoire sur la résolution des équations numériques”. Bull. des sciences de Férussac. 11: 419–422. 
  55. ^ Eric W. Weisstein, Integer Relation la MathWorld.
  56. ^ Peterson I (). „Jazzing Up Euclid's Algorithm”. ScienceNews.  Legătură externa în |title= (ajutor)
  57. ^ Cipra BA (). „The Best of the 20th Century: Editors Name Top 10 Algorithms”. SIAM News. Society for Industrial and Applied Mathematics. 33 (4).  Legătură externa în |title= (ajutor)
  58. ^ Cole AJ, Davie AJT (). „A game based on the Euclidean algorithm and a winning strategy for it”. Math. Gaz. 53: 354–357. doi:10.2307/3612461. 
  59. ^ Spitznagel EL (). „Properties of a game based on Euclid's algorithm”. Math. Mag. 46: 87–92. 
  60. ^ Rosen, p. 95.
  61. ^ Roberts J (). Elementary Number Theory: A Problem Oriented Approach. Cambridge, MA: MIT Press. pp. 1–8. ISBN 0-262-68028-0 Verificați valoarea |isbn=: checksum (ajutor). 
  62. ^ Jones GA, Jones JM (). „Bezout's Identity”. Elementary Number Theory. New York: Springer-Verlag. pp. 7–11. 
  63. ^ Rosen, p. 81.
  64. ^ Cohn, p. 104.
  65. ^ Rosen, p. 91.
  66. ^ Schroeder, p. 23.
  67. ^ Rosen, pp. 90–93.
  68. ^ a b Koshy T (). Elementary Number Theory with Applications. Burlington, MA: Harcourt/Academic Press. pp. 167–169. ISBN 0-12-421171-2. 
  69. ^ Bach E, Shallit J (). Algorithmic number theory. Cambridge, MA: MIT Press. pp. 70–73. ISBN 0-262-02405-5. 
  70. ^ Stark, pp. 26–36.
  71. ^ Ore, p. 44.
  72. ^ Ore, p. 44.
  73. ^ Stark, pp. 281–292.
  74. ^ Rosen, pp. 119–125.
  75. ^ Schroeder, pp. 106–107.
  76. ^ Schroeder, pp. 108–109.
  77. ^ Rosen, pp. 120–121.
  78. ^ Stark, p. 47.
  79. ^ Schroeder, pp. 107–109.
  80. ^ Stillwell, pp. 186–187.
  81. ^ Schroeder, p. 134.
  82. ^ "Error correction coding: mathematical methods and algorithms", pagina 266, Todd K. Moon, John Wiley and Sons, 2005, ISBN 0-471-64800-0
  83. ^ Rosen, pp. 143–170.
  84. ^ Schroeder, pp. 194–195.
  85. ^ Vinogradov IM (). Elements of Number Theory. New York: Dover. pp. 3–13. 
  86. ^ Crandall R, Pomerance C (). Prime Numbers: A Computational Perspective (ed. 1st). New York: Springer-Verlag. pp. 225–349. ISBN 0-387-94777-9. 
  87. ^ Knuth, pp. 369–371.
  88. ^ Shor PW (). „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM J. Sci. Statist. Comput. 26: 1484. 
  89. ^ Dixon JD (). „Asymptotically fast factorization of integers”. Math. Comput. 36: 255–260. doi:10.2307/2007743. 
  90. ^ Lenstra Jr. HW (). „Factoring integers with elliptic curves”. Annals of Mathematics. 126: 649–673. doi:10.2307/1971363. 
  91. ^ Knuth, pp. 380–384.
  92. ^ Knuth, pp. 339–364.
  93. ^ Lamé G (). „Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers”. Comptes Rendus Acad. Sci. 19: 867–870. 
  94. ^ Grossman H (). „On the Number of Divisions in Finding a G.C.D”. The American Mathematical Monthly. 31: 443. doi:10.2307/2298146. 
  95. ^ Honsberger R (). Mathematical Gems II. The Mathematical Association of America. pp. 54–57. ISBN 0-88385-302-7. 
  96. ^ Knuth, p. 344.
  97. ^ Ore, p. 45.
  98. ^ Knuth, p. 344.
  99. ^ Knuth, p. 343.
  100. ^ Mollin, p. 21.
  101. ^ LeVeque, p. 35.
  102. ^ Knuth, p. 343.
  103. ^ Mollin, pp. 21–22.
  104. ^ Knuth, p. 344.
  105. ^ Knuth, p. 353.
  106. ^ Knuth, p. 357.
  107. ^ Tonkov T (). „On the average length of finite continued fractions”. Acta arithmetica. 26: 47–57. 
  108. ^ Porter JW (). „On a Theorem of Heilbronn”. Mathematika. 22: 20–28. 
  109. ^ Knuth DE (). „Evaluation of Porter's Constant”. Computers and Mathematics with Applications. 2: 137–139. doi:10.1016/0898-1221(76)90025-0. 
  110. ^ Dixon JD (). „The Number of Steps in the Euclidean Algorithm”. J. Number Theory. 2: 414–422. doi:10.1016/0022-314X(70)90044-2. 
  111. ^ Heilbronn HA (). „On the Average Length of a Class of Finite Continued Fractions”. În Paul Turán. Number Theory and Analysis. New York: Plenum. pp. 87–96. Library of Congress Control Number 68-8991. 
  112. ^ Knuth, p. 354.
  113. ^ a b Norton GH (). „On the Asymptotic Analysis of the Euclidean Algorithm”. Journal of Symbolic Computation. 10: 53–58. doi:10.1016/S0747-7171(08)80036-3. 
  114. ^ Knuth, p. 355.
  115. ^ Knuth, p. 356.
  116. ^ Knuth, pp. 257–261.
  117. ^ Knuth, p. 352.
  118. ^ Wagon S (). Mathematica in Action. New York: Springer-Verlag. pp. 335–336. ISBN 0-387-98252-3. 
  119. ^ Cohen, p. 14.
  120. ^ Cohen, pp. 14–15, 17–18.
  121. ^ Knuth, pp. 321–323.
  122. ^ Stein J (). „Computational problems associated with Racah algebra”. Journal of Computational Physics. 1: 397–405. doi:10.1016/0021-9991(67)90047-2. 
  123. ^ a b Crandall R, Pomerance C (). Prime Numbers: A Computational Perspective (ed. 1st). New York: Springer-Verlag. pp. 77–79, 81–85, 425–431. ISBN 0-387-94777-9. 
  124. ^ Knuth, p. 328.
  125. ^ Lehmer DH (). „Euclid's Algorithm for Large Numbers”. The American Mathematical Monthly. 45: 227–233. doi:10.2307/2302607. 
  126. ^ Sorenson J (). „Two fast GCD algorithms”. J. Algorithms. 16: 110–144. doi:10.1006/jagm.1994.1006. 
  127. ^ Weber K (). „The accelerated GCD algorithm”. ACM Trans. Math. Soft. 21: 111–122. doi:10.1145/200979.201042. 
  128. ^ Aho A, Hopcroft J, Ullman J (). The Design and Analysis of Computer Algorithms. New York: Addison–Wesley. pp. 300–310. 
  129. ^ Schönhage A (). „Schnelle Berechnung von Kettenbruchentwicklungen”. Acta Informatica. 1: 139–144. doi:10.1007/BF00289520. 
  130. ^ Cesari G (). „Parallel implementation of Schönhage's integer GCD algorithm”. În G. Buhler. Algorithmic Number Theory: Proc. ANTS-III, Portland, OR. New York: Springer-Verlag. pp. 64–76.  Volume 1423 in Lecture notes in Computer Science.
  131. ^ Stehlé D, Zimmermann P (). „Gal's accurate tables method revisited”. Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17). Los Alamitos, CA: IEEE Computer Society Press. 
  132. ^ Möller N (). „On Schönhage's algorithm and subquadratic integer gcd computation”. Mathematics of Computation. 77: 589–607. doi:10.1090/S0025-5718-07-02017-0.  Legătură externa în |title= (ajutor)

Bibliografie

  • Cohen H (). A Course in Computational Algebraic Number Theory. New York: Springer-Verlag. ISBN 0-387-55640-0. 
  • Cohn H (). Advanced Number Theory. New York: Dover. ISBN 0-486-64023-X. 
  • Cormen TH, Leiserson CE, Rivest RL, and Stein C (). Introduction to Algorithms (ed. 2nd). MIT Press and McGraw–Hill. ISBN 0262032937. 
  • Cox D, Little J, and O'Shea D (). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (ed. 2nd). Springer-Verlag. ISBN 0-387-94680-2. 
  • Dirichlet PGL (). Richard Dedekind, ed. Vorlesungen über Zahlentheorie. Braunschweig: Vieweg. 
  • Hardy GH, Wright EM [revised by D.R. Heath-Brown and J.H. Silverman]. (). An Introduction to the Theory of Numbers (ed. 6th). Oxford: Clarendon Press. 
  • Knuth D (). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (ed. 3rd). Addison–Wesley. ISBN 0201896842. 
  • LeVeque WJ (). Fundamentals of Number Theory. New York: Dover. ISBN 0-486-68906-9. 
  • Mollin RA (). Fundamental Number Theory with Applications (ed. 2nd). Boca Raton: Chapman & Hall/CRC. ISBN 9781420066593. 
  • Ore Ø (). Number Theory and Its History. New York: McGraw–Hill. 
  • Rosen KH (). Elementary Number Theory and its Applications (ed. 4th). Reading, MA: Addison–Wesley. ISBN 0201870738. 
  • Schroeder MR (). Number Theory in Science and Communication (ed. 4th). Springer-Verlag. ISBN 0387158006. 
  • Stark H (). An Introduction to Number Theory. MIT Press. ISBN 0-262-69060-8. 
  • Stillwell J (). Numbers and Geometry. New York: Springer-Verlag. ISBN 0-387-98289-2. 
  • Tattersall JJ (). Elementary number theory in nine chapters. Cambridge: Cambridge University Press. ISBN 9780521850148. 
  • Uspensky JV, Heaslet MA (). Elementary Number Theory. New York: McGraw–Hill. 

Legături externe