1. Fundamentele teoriei numărului Teoria congruențelor
2. Istoria teoriei numerelor
În
originile teoriei numerelor ca disciplină științifică
studiile lui Euclid (secolul III î.Hr.),
Diophantus (secolul III d.Hr.), Fermat (1601-1665), Euler
(1707-1783), păstrată în scris.
Sursele istorice confirmă acest lucru
creatorul teoriei numerelor este Euler. În acest caz,
trebuie remarcat faptul că mai multe teoreme din teorie
numerele (de obicei fără dovezi) au fost
formulată înainte de Euler.
fiecare
un număr natural mai mare decât unul,
este împărțit în cel puțin două numere: cu 1 și de la sine
ei înșiși. Dacă numărul nu are divizori, cu excepția ei înșiși
ea însăși și unitățile, se numește simplu și dacă y
există încă divizoare, apoi compozite. Unitatea
nu este considerat nici un număr prime, nici unul compozit.
De exemplu, numerele 7 și 29 sunt simple; numerele 9, 15 -
compus (9 împărțit la 3, 15 împărțit la 3 și 5).
Nu se poate spune imediat fiecărui număr dacă este simplu sau compozit.
Dacă numărul este mai mic de o sută, atunci cel mai probabil putem răspunde imediat
la această întrebare. Cu toate acestea, cu un număr mare problema este mai complicată.
Se întâmplă că testul de simplitate este mult mai lung și
pentru a lucra cu numere întregi mari chiar
programe de calculator speciale.
Căutarea numerelor prime prime este importantă
matematică și nu numai. De exemplu, în criptografie mare
Numerele simple sunt folosite în algoritmii de criptare cu deschis
cheie. Pentru a asigura fiabilitatea criptare acolo
Utilizați primes până la 1024 biți în lungime.
Este relativ ușor să multiplicați două numere, mai ales dacă
Avem un calculator, iar numerele nu sunt prea mari. Există, de asemenea
problemă inversă - problemă de factorizare - găsirea a două sau a
mai multe numere care dau o multiplicare a unui numar dat. aceasta
Sarcina este mult mai dificilă decât multiplicarea numerelor, și oricine
a încercat să o rezolve, acest lucru este cunoscut.
De exemplu, dacă vrem să înmulțim 67 cu 113, atunci rezultatul,
7571, vor fi probabil primite în mai puțin de un minut. Dacă de la
Suntem obligați să găsim două numere ale căror produse sunt egale cu 7571,
atunci, cel mai probabil, ne va lua mult mai mult timp.
6. Teorema principală a aritmeticii
7. Numere prime primordiale și funcția Euler
Se spune că două numere sunt relativ prime dacă nu au una
divizorul comun, cu excepția unuia.
De exemplu, numerele 11 și 12 sunt relativ prime (nu au divizoare comune
cu excepția unuia), numerele 30 și 35 nu sunt (au un divizor comun 5).
O investigație a regularităților asociate cu întregi este lungă
a fost angajat în matematica elvețiană Leonard Euler. Una dintre aceste probleme,
de care era interesat, a fost următorul: câte sunt
din numere naturale care nu depășesc n și relativ prime la n?
Răspunsul la această întrebare a fost primit de Euler în 1763 și de acest răspuns
este legat de descompunerea canonică a numărului n prin factori primari.
8. Numărul de numere naturale care nu depășesc n și relativ prime la n este numit funcția Euler și este notat cu
De exemplu, găsim numărul de numere naturale care nu depășesc
12 și relativ prime la 12. Din seria numerelor naturale 1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11 sunt relativ prime (fără divizori comuni) cu 12
vor fi doar numerele 1, 5, 7, 11. Numărul lor este de patru.
Folosim funcția Euler și obținem și 4.
Pentru a face acest lucru, mai întâi scriem descompunerea canonică a numărului
12: 12 = 22 * 3.
Este convenabil să folosiți formula lui Euler pentru
mare n dacă expansiunea n
la primii factori.
Pentru criptografie, formula lui Euler este importantă,
E ușor să obțineți un număr pentru
simple și alte numere.
Euler a fost unul dintre primii care au folosit și
Chiar și algoritmul lui Euclid îmbunătățit în
aritmetică.
11. GCD prin algoritmul Euclid
Euclid algoritmul este un algoritm pentru găsire
cel mai mare divizor comun (GCD) al unei perechi de numere întregi
numere.
Cel mai mare divizor comun (GCD) este
Un număr care împarte restul de două numere și
se împărtășește fără nici o rămășiță nimănui
divizorul a două numere. Pur și simplu puneți asta
Cel mai mare număr care poate fi
restul pentru a împărți cele două numere pentru care căutăm
GCD.
12. O descriere a algoritmului pentru identificarea GCD prin împărțire
1. Cu cât este mai mare numărul împărțit în mai mici.
2. Dacă este divizibil fără rest, atunci numărul mai mic și
există un GCD (ieșire din buclă).
3. Dacă există un rest, atunci un număr mai mare este înlocuit
pe restul diviziei.
4. Continuați cu pasul 1.
Exemplul 1: Găsiți GCD pentru 30 și 18.
30/18 = 1 (restul 12)
18/12 = 1 (soldul 6)
12/6 = 2 (restul 0).
GCD (30, 18) = 6
13. Identificarea GCD prin factorizare în factori primari
Cel mai mare divizor comun poate fi găsit
prin extinderea numerelor prin factori primari.
Formăm regula:
GCD a două numere întregi a și b
este egal cu produsul tuturor simplelor simple
multiplicatori în extinderea numerelor a
și b de factori primari.
14. Găsiți cel mai mare divizor comun de 72 și 96
Soluția.
Se descompun în principalii factori, numerele 72 și 96:
72 = 2 · 2 · 2 · 3 · 3
96 = 2 · 2 · 2 · 2 · 2 · 3
Factorii simpli simple sunt 2, 2, 2 și 3.
Astfel, GCD (72, 96) = 2 · 2 · 2 · 3 = 24.
răspundă:
DUMNEZEU (72, 96) = 24.
15. Găsirea a trei sau mai multe numere de GCD-uri
Găsind cel mai mare divizor comun de trei
și mai multe numere pot fi reduse la
identificarea secvențială a GCD a două numere.
Cel mai mare divizor comun al mai multor numere
a1, a2, ..., ak este egal cu numărul dk, care este la
calculul secvențial al GCD (a1, a2) = d2,
GCD (d2, a3) = d3, GCD (d3, a4) = d4, ..., GCD (dk-1,
ak) = dk.
16. Găsiți GCD (78, 294, 570 și 36)
Găsiți GCD (78. 294. 570 și 36)
1) Folosind algoritmul Euclid, determinăm cel mai mare
divizorul comun d2 al primelor două numere 78 și 294.
Când divizăm, obținem egalitățile 294 = 78 · 3 + 60;
78 = 60,1 + 18; 60 = 18,3 + 6 și 18 = 6,3.
Astfel, d2 = GCD (78, 294) = 6.
2) Calculăm d3 = GCD (d2, a3) = GCD (6, 570).
T.570 = 6 · 95, prin urmare, d3 = GCD (6, 570) = 6.
3) Calculați d4 = GCD (d3, a4) = GCD (6, 36) = 6.
Astfel, cel mai mare divizor comun de patru
din numerele date este d4 = 6.
DUMNEZEU (78, 294, 570, 36) = 6.
17. Găsirea datelor cele mai mici comune (NOC) ale numerelor
Cel mai mic
comun
plia
de date
natural
numerele
este numit
cel mai mic
un număr natural care reprezintă un multiplu al fiecăruia dintre aceste numere.
Un exemplu.
NOC (24, 42) = 168. Acesta este cel mai mic număr,
care este împărțită în 24 și 42.
18. Găsirea celei mai puțin frecvente multiple
Pentru a găsi LCM a mai multor date
numerele naturale trebuie să fie:
1) descompune fiecare dintre aceste numere în simplu
multiplicatori;
2) scrieți expansiunea celei mai mari dintre numere și
înmulțiți-l cu factorii care lipsesc
extinderea altor numere.
Cel mai mic număr de două numere relativ prime
este egal cu produsul acestor numere.
19. Găsiți LCM (35; 40)
Noi descompunem numerele 35 și 40 în principalii factori
35 = 5 · 7, 40 = 2 · 2 · 2 · 5 sau 40 = 23 · 5
Luăm descompunerea mai mare de 40 și se completează
lipsesc
multiplicatori.
NOC (35; 40) = 23,5; 7 = 40; 7 = 280.
Răspunsul este: NOC (35; 40) = 280.
20. găsiți NOC (75, 120, 150)
Descompunem numerele 75, 120 și 150 în simple
multiplicatori.
75 = 3 ∙ 52, 120 = 23 ∙ 3 ∙ 5, 150 = 2 ∙ 3 ∙ 52
Luăm descompunerea unui număr mai mare de 150 și
îl suplimentăm cu două "dude", deoarece în
extinderea numărului 120 există trei "două", și în
descompunerea numărului 150 este doar una.
NOC (75, 120, 50) = 2 ∙ 3 ∙ 52 ∙ 2 ∙ 2 = 150 ∙ 4 = 600.
Răspuns: NOC (75, 120, 150) = 600.
21. Teoria congruențelor
Fiecărui număr întreg îi corespunde o definiție
restul de împărțind-o cu m;
dacă două numere întregi a și b corespund aceleași
restul de m, ele sunt numite echidistant în
modulul m sau modulul m comparabil.
Comparabilitatea numerelor a și b modulo m este notată
după cum urmează:
care se citește: a este comparabilă cu b modulo m.
comparație
spectacol
util
pentru
matematicieni și criptografi, în multe privințe
similar cu proprietățile egalității.
Aceste proprietăți fac posibilă o simplificare substanțială
calcule aritmetice.
De exemplu, proprietățile comparațiilor sunt utile pentru
calcule în algoritmi de criptare cu un algoritm deschis
cheie.
23. Proprietățile congruențelor
1. Dacă a-b este divizibil cu m, atunci
De exemplu,
deoarece 15 -1 = 14, iar 14 este un multiplu de 7.
2. În cazul în care
De exemplu,
24. Proprietățile congruențelor
3. În cazul în care
4. Dacă,
simplu cu m.
De exemplu
atunci
apoi cu
25. Teorema mică a lui Fermat
Baza algoritmului de criptare pentru sistemul RSA
este
teoremă
formulat
în
începutul
din secolul al XVII-lea fără dovada de către francezi
matematicianul Pierre Fermat. Este deseori
numita "teorema minora a lui Fermat".
Dacă p este un număr prime și m este orice număr
nu este divizibilă de p, atunci
adică numărul mp-1, împărțit la p, dă restul 1.
Articole similare
Trimiteți-le prietenilor: