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:
- alegem un număr aleatoriu a și verificăm, folosind algoritmul euclidian, condiția (a. n) = 1;
- dacă nu este satisfăcut, atunci răspunsul "n - compus";
- a verifica fezabilitatea comparației (1);
- dacă comparația nu este efectuată, atunci răspunsul "n - compus";
- 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:
- alegem un număr aleatoriu a din interval și verificăm, folosind algoritmul lui Euclid, condiția (a. n) = 1;
- dacă nu este satisfăcut, atunci răspunsul "n - compus";
- calcula un t (mod n);
- dacă un t ≡ ± 1 (mod n), atunci trecem la subsecțiunea 1;
- calculăm un 2 t. ..., un 2 s -1 t până când apare -1;
- dacă nici unul dintre aceste numere nu este -1, atunci răspunsul este "n - compus";
- 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:
- (a + b) + c = a + (b + c) și (a · b) · c = a · (b · c) b. c ∈ K (asociativitate)
- a + b = b + a și a · b = b · a pentru toate a. b ∈ K (comutativitate)
- a · (b + c) = a · b + a · c pentru toate a. b. c ∈ K (distributivitate)
- Există elemente 0 și 1, numite zero și respectiv, respectiv, astfel încât a + 0 = a · 1 = a pentru orice a ∈ K
- Pentru orice element a ∈ K există un element b. astfel încât a + b = 0 (existența unui aditiv invers)
- 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:
- (a + b) + c = a + (b + c) și (a · b) · c = a · (b · c) b. c ∈ R (asociativitate)
- a + b = b + a și a · b = b · a pentru toate a. b ∈ R (comutativitate)
- a · (b + c) = a · b + a · c pentru toate a. b. c ∈ R (distributivitate)
- Există elemente 0 și 1, numite zero și respectiv, respectiv, astfel încât a + 0 = a · 1 = a pentru orice a ∈ R
- 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:
- (a · b) · c = a · (b · c) pentru toate a. b. c ∈ G (asociativitate)
- Există un element 1, numit unitate. astfel încât a · 1 = 1 · a = a pentru orice a ∈ G
- 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
Trimiteți-le prietenilor: