Glosar

Selectați unul dintre cuvintele cheie din stânga ...

Divizibilitate și Numere PrimeCel Mai Mare Divizor Comun

Timp de citit: ~15 min

Un arhitect proiectează podeaua unei curți mari cu dimensiunea 18m pe 30m. El vrea ca aceasta să fie acoperită cu dale pătratice fără să existe goluri sau suprapuneri de-a lungul marginilor. Care este dimensiunea maximă a pătratelor pe care le poate folosi?

Dalele au dimensiunea de ${x}m.

La fel ca mai înainte, această întrebare nu este despre geometrie - este despre divizibilitate. Lungimea laturilor dalelor trebuie să dividă pe 18 și 30, iar cel mai mare număr posibil care îndeplinește această condiție este . Acesta se numește Cel Mai Mare Divizor Comun sau cmmdc al lui 18 și 30.

Putem folosi din nou descompunerea în factori primi pentru a calcula cmmdc al oricăror două numere. Să ne reamintim că orice divizor al unui număr trebuie să aibă o parte din divizorii primi ai acelui număr.

18
=
2
×
3
×
3
30
=
2
×
3
×
5

Să presupunem că X este cmmdc al lui 18 și 30. Atunci X divide pe 18, deci divizorii primi ai lui X vor fi 2, 3 și 3. De asemenea, X divide pe 30, deci divizorii primi ai lui X vor fi 2, 3 și 5.

Pentru a-l afla pe X, avem nevoie sa înmulțim toate numerele care sunt divizori primi pentru numere 18 și 30:

X  =  2 × 3  =  6.

Acum avem o metodă simplă pentru găsirea cmmfc a două numere:

  1. Descompuneți în factori primi fiecare număr.
  2. Înmulțește factorii primi ce aparțin ambelor numere.

Încă o dată numerele prime sunt speciale: cmmdc a două numere prime diferite este mereu , pentru că nu au în comun niciun divizor prim.

Criptografia

Una din cele mai importante aplicații moderne ale numerelor prime este în ramura matematicii numită Criptografie. Timp de mii de ani, oamenii au încercat să ascundă mesaje astfel încât doar destinatarii stabiliți să le poată citi - acest proces se numește criptare. Criptarea este folosită de oricine, de la generalii care făceau schimb de ordine secrete în timpul războiului până la poșta electronică sau transferurile bancare pe internet. Oamenii au încercat întotdeauna să găsească metode de criptare mai bune și mai sigure, dar, după o vreme, toate erau sparte cu ajutorul algoritmilor și mai avansați. În timpul celui de-al Doilea Război mondial, armata germană a folosit Enigma: o mașină complexă formată dintr-o tastatură, discuri rotative și un tablou de prize. Această mașină criptografia mesajele folosind una din cele 158 de milioane de milioane de milioane de posibilități (acesta e un 158 urmat de 18 zerouri!). Se credea că acest cod nu putea fi spart, dar Serviciul Secret Britanic, condus de matematicianul Alan Turing, a construit unul din primele calculatoare care au reușit să-l descifreze.

Mașina germană Enigma cu patru rotoare

În ziua de azi, calculatoarele sunt mult mai performante și sunt capabile să încerce milioane de posibilități în fiecare secundă. Pentru a dezvolta algoritmi de criptare mai buni, trebuie să găsim o operație matematică dificilă chiar și pentru calculatoarele puternice. Calculatoarele sunt incredibil de rapide la adunăre, scădere, înmulțire și împărțire. Cu toate acestea, ele sunt foarte lente la descompunerea numerelor întregi în numere prime…

ÎN CURÂND – exemplu RSA cu Alice și Bob

Acest algoritm criptografic numit se numește Criptografie RSA, numit după cei trei inventatori ai săi, Ron Rivest, Adi Shamir și Leonard Adleman care l-au făcut public în anul 1977. Se pare că Serviciului Britanic Secret știa o metodă foarte similară încă din anul 1973, dar algoritmul a rămas clasificat până mult mai târziu.

Astăzi, numerele prime sunt utilizate de calculatoarele din toată lumea pentru a face schimb de date. În timp ce navighezi pe internet sau trimiți mesaje de chat, telefonul sau laptopul tău vor genera în liniște numere prime mari și vor face schimburi de chei publice cu alte calculatoare.