Algoritmi matematici discreți

Euclid algoritm

Euclid și-a inventat faimosul algoritm pentru rezolvarea problemei de comensurabilitate a două segmente. O măsură comună a segmentelor cu lungimile L 1 și L 2 este un segment cu cea mai mare lungime posibilă L. Aceasta poate fi aplicată fără reziduuri atât în ​​primul, cât și în cel de-al doilea segment. După cum se știe, algoritmul este după cum urmează. Segmentul mai mic (cu lungimea L 2) se potrivește cu numărul maxim posibil (L 1), adică de 1. ori, după care rămâne un segment de lungime L 1 - a 1 L 2. pe care îl denotăm cu L 3. Apoi repetați această operație cu L 2 și L 3, etc. Algoritmul încheie lucrarea la acel pas, spunând cu numărul k. atunci când segmentul L k + 1 obținut în etapa anterioară se potrivește cu un număr întreg de ori pe segmentul L k. Răspunsul este L k +1.

Avansat algoritm Euclid

Puțini completează algoritmul euclidian, îl puteți folosi pentru a obține coeficienții întregi x și y. pentru care

(a.b) = GCD (a.b) = a x + b y

GCD - cel mai mare divizor comun

Timpul de funcționare al algoritmului euclidian

Fie e (m. N) numărul de pași ai algoritmului euclidian aplicat numerelor naturale n și m. Până în prezent, cel mai celebru rezultat al funcției e (m. N) rămâne găsit de matematicianul francez Gabriel Lam (Gabriel Lamé, 1795-1870) în prima jumătate a secolului al XIX-lea (1844), scorul superior:

e (m n) ≤ [logφ 5 1/2 (max (m n) + 1/2)] - 1, unde φ = (1 + 5 1/2) / 2

Această estimare este exactă și se obține la numerele Fibonacci vecine: m = F k + 1. n = F k.

Pentru o dovadă și diferite interpretări ale algoritmului euclidian, a se vedea [5]

Comparații modulo

Se consideră că două numere întregi a și b sunt modulo m congruent. dacă a - b este divizibilă de m.

a ≡ b (mod m) ↔ m | (A - b)

Fiecare număr natural este comparabil cu unul dintre numerele modulo m.

Inelul de reziduuri Z / n Z

Toate reziduurile modulo n formează un inel de reziduu, notat cu Z / n Z. Numărul elementelor din inelul Z / n Z este egal cu n. De exemplu, inelul Z / 6 Z constă din 6 elemente :.

Acțiuni în ring Z / n Z

Elementele acestui inel pot fi adăugate, scăzute și înmulțite ca numere obișnuite. De exemplu, în inelul Z / 6 Z se păstrează următoarele egalități:

2 + 3 ≡ 5 (mod 6)
3 - 5 ≡ 4 (mod 6)
2 · 4 ≡ 2 (mod 6)

Diviziunea în Z / n Z

Divizarea inelului Z / n Z nu este întotdeauna posibilă. De exemplu, în Z / 8 Z ring, nu puteți împărți 1 la 2, dar puteți împărți 2 cu 3 (se dovedește 6). Care este motivul imposibilității divizării în unele cazuri? Pentru a înțelege acest lucru, vom determina ce este împărțirea.

Să presupunem că ni se dă ecuația

a x ≡ b (mod m)

În ea, a și b sunt parametri, x nu este cunoscut.
Dacă x există și este unic, atunci x se numește coeficientul împărțirii lui b cu a.

Respingem această ecuație după cum urmează:

Evident, dacă b nu este divizibil de către (a. M), atunci nu există soluții și împărțirea este imposibilă. (De aceea 1 nu poate fi împărțit cu 2 în Z / 8 Z) Pentru a rezolva această ecuație, găsim x. y. astfel încât

Deoarece b = w (a. M), obținem:

b = a (xw) + m (yw)

Deci, am găsit una din soluțiile ecuației a x ≡ b (mod m). Este ușor de demonstrat că această ecuație are exact soluții (a. M).

Astfel, împărțirea b cu a în Z / n Z este posibilă numai atunci când (a. M) = 1. Dacă n este prime, atunci divizarea în Z / n Z este posibilă pentru toate elementele altele decât zero.

Modele aritmetice modulare

Modulul aritmetic modular se bazează pe așa-numita teoremă a restului chinez (CTO). În jurul anului 100 î.Hr. e. matematicianul chinez Sun-Tsu a rezolvat această problemă: găsiți numărul care dă restul 2, 3, respectiv 2, atunci când se împarte cu 3, 5, 7.

Teorema restului chinezesc

Fie n = n 1 n 2 ... n k. Mai mult, numerele n 1. n 2. ..., n k sunt pereche relativ prime. Luați în considerare corespondența

unde i este restul de împărțire a cu n i. Apoi definește o corespondență unu-la-unu între Z / n Z și Z / n 1 Zs ... × Z / n k Z.

Funcția Euler

Funcția Euler φ (a) este definită pentru toate numerele naturale a și reprezintă numărul de numere de la 1 la un relativ prime la a. exemple:

Ce este φ (239)?

Este ușor de demonstrat că funcția Euler este multiplicativă, adică pentru orice n și m astfel încât (n. M) = 1

φ (nm) = φ (n) φ (m)

Este evident că pentru un simplu p următoarele egalități dețin:

φ (p) = p-1,
φ (p n) = p n -1 (p -1)

Aceste proprietăți ne permit să calculăm rapid funcția Euler dacă cunoaștem descompunerea numărului n în factorii primari.

Interesant, există astfel de n. că φ (n) = 239?

Teoremele Euler și Fermat

Teorema (Euler)

Pentru m> 1 și (a. M) = 1, următoarele sunt adevărate:

a a (m) ≡ 1 (mod m)

Teorema (Fermat)

Pentru orice prim p și orice număr natural a, sunt valabile următoarele:

un p ≡ a (mod p)

Exponentiație dichotomică

Exponentierea în modulul joacă un rol important în verificarea numerelor pentru simplitate și, de asemenea, în criptosistemele RSA.

Primele rădăcini

Fie p un număr prime. Apoi, după cum se știe bine, Z / p Z este un câmp. Ordinea reziduului a> 0 este cel mai mic număr natural m, astfel încât

a m ≡ 1 (mod p)

Conform teoremei mici a lui Fermat, există cel puțin un astfel de m (și este egal cu p -1).

Pentru orice prim p există un rest g de ordin p -1.

Un astfel de reziduu g se numește modulo rădăcină antiderivantă.

De asemenea, este ușor să arătăm că există exact reziduuri φ (p -1).

Din ipoteza extinsă a lui Riemann (vezi [3], p. 112) rezultă că cel mai mic modem rădăcină primitiv este limitat de O (log 6 p).

Verificarea numerelor pentru simplitate

Cea mai simplă modalitate de a verifica numărul n pentru simplitate este de a testa divizorii (diviziune de încercare).

Un test bazat pe o mică teoremă Fermat

O mică teoremă Fermat afirmă că dacă n este prime, atunci se aplică următoarea condiție: pentru toate a, are loc o comparație

a n -1 ≡ 1 (mod n) (1)

Din această teorem rezultă că dacă congruența (1) nu este satisfăcută pentru cel puțin un număr a în intervalul, atunci n este unul compozit. Prin urmare, putem propune următorul test probabilistic de simplitate:

  1. alegem un număr aleatoriu a și verificăm, folosind algoritmul euclidian, condiția (a. n) = 1;
  2. dacă nu este satisfăcut, atunci răspunsul "n - compus";
  3. a verifica fezabilitatea comparației (1);
  4. dacă comparația nu este efectuată, atunci răspunsul "n - compus";
  5. dacă se face comparația, atunci răspunsul este necunoscut, dar puteți repeta din nou testul.

a n -1 ≡ 1 (mod n)

Testul probabilistic Miller-Rabin

Fie n nod și n - 1 = 2 s t. t este ciudat.

Dacă numărul n este simplu, atunci pentru toate a> 1

a n -1 ≡ 1 (mod n)

Prin urmare, luând în considerare elementele puteți observa că fie dintre ele există o egalitate -1 (mod n), fie o t ≡ 1 (mod n).

Pe această notă, se bazează următorul test probabilistic de simplitate:

  1. alegem un număr aleatoriu a din interval și verificăm, folosind algoritmul lui Euclid, condiția (a. n) = 1;
  2. dacă nu este satisfăcut, atunci răspunsul "n - compus";
  3. calcula un t (mod n);
  4. dacă un t ≡ ± 1 (mod n), atunci trecem la subsecțiunea 1;
  5. calculăm un 2 t. ..., un 2 s -1 t până când apare -1;
  6. dacă nici unul dintre aceste numere nu este -1, atunci răspunsul este "n - compus";
  7. dacă am ajuns la -1, atunci răspunsul este necunoscut (și testul poate fi repetat din nou).

Un număr compozit nu va fi definit ca un compozit cu probabilitate 1/4 (vezi [1]).

Dacă ipoteza extinsă Riemann este adevărată, atunci este suficient să verificați toate a (vezi [3]).

Aplicație. Unele concepte din algebră

Definiția. Un câmp este un set K cu două operații binare și + definite pe el care îndeplinesc următoarele condiții:

  1. (a + b) + c = a + (b + c) și (a · b) · c = a · (b · c) b. c ∈ K (asociativitate)
  2. a + b = b + a și a · b = b · a pentru toate a. b ∈ K (comutativitate)
  3. a · (b + c) = a · b + a · c pentru toate a. b. c ∈ K (distributivitate)
  4. Există elemente 0 și 1, numite zero și respectiv, respectiv, astfel încât a + 0 = a · 1 = a pentru orice a ∈ K
  5. Pentru orice element a ∈ K există un element b. astfel încât a + b = 0 (existența unui aditiv invers)
  6. Pentru orice element a ∈ K. nu egal cu zero, există un element c. astfel încât a · c = 1 (existența unui invers multiplicativ)

Definiția. Un inel (sau inel comutativ) este un set R cu două operații binare și + pe acesta, care îndeplinesc următoarele condiții:

  1. (a + b) + c = a + (b + c) și (a · b) · c = a · (b · c) b. c ∈ R (asociativitate)
  2. a + b = b + a și a · b = b · a pentru toate a. b ∈ R (comutativitate)
  3. a · (b + c) = a · b + a · c pentru toate a. b. c ∈ R (distributivitate)
  4. Există elemente 0 și 1, numite zero și respectiv, respectiv, astfel încât a + 0 = a · 1 = a pentru orice a ∈ R
  5. Pentru orice element a ∈ R există un element b. astfel încât a + b = 0 (existența unui aditiv invers)

Definiția. Un grup este un set G cu o operație binară definită pe acesta, care satisface următoarele condiții:

  1. (a · b) · c = a · (b · c) pentru toate a. b. c ∈ G (asociativitate)
  2. Există un element 1, numit unitate. astfel încât a · 1 = 1 · a = a pentru orice a ∈ G
  3. Pentru orice element a ∈ G există un element b. astfel încât a · b = b · a = 1 (existența elementului invers)

literatură

Mikhail Lukin, Roman Satyukov

Mulțumesc, a ajutat foarte mult. )

Articole similare