Ce este un numar prim?
Un numar prim e un numar natural mai mare decat 1 care se imparte exact doar la 1 si la el insusi. Exemple: 2, 3, 5, 7, 11, 13.
Infinitatea numerelor prime (Euclid)
Presupunem ca multimea numerelor prime e finita: P = {p1, p2, ..., pn}. Construim N = (p1 * p2 * ... * pn) + 1. Obtinem un prim nou, contradictie. Deci primele sunt infinite.
Teorema fundamentala
Orice numar natural se descompune unic ca produs de numere prime. Ex: 84 = 2^2 * 3 * 7.
Numere prime Mersenne
Mp = 2^p - 1, unde p e prim. Ex: M2=3, M3=7, M5=31, M7=127. Nu toate sunt prime: M11=2047=23*89.
La ce folosesc numerele Mersenne?
Desi par o curiozitate matematica, numerele Mersenne au aplicatii practice importante:
-
Testarea hardware-ului — GIMPS (Great Internet Mersenne Prime Search) e unul dintre cele mai mari proiecte de calcul distribuit. A descoperit cele mai mari numere prime cunoscute, cu sute de mii de cifre.
-
Generatoare de numere aleatoare — Primele Mersenne sunt folosite in generatoare pseudo-aleatoare de inalta calitate (Mersenne Twister).
-
Criptografie — Numerele prime mari (inclusiv Mersenne) stau la baza criptografiei cu cheie publica, inclusiv RSA.
-
Cercetare matematica — Ajuta la testarea conjecturilor si a limitelor computatiei.
Testul Lucas-Lehmer
Verifica daca Mp e prim. Sir: S1=4, S(k+1)=(S(k)^2 - 2) mod Mp. Mp e prim daca S(p-1)=0.
Exemplu M5=31: S1=4, S2=14, S3=8, S4=0 → 31 e prim. E folosit de GIMPS pentru a descoperi cele mai mari prime cunoscute.
RSA si numerele prime
RSA alege doua numere prime mari p, q si le inmulteste: n = p*q. E usor de inmultit, extrem de greu de factorizat. Pe aceasta asimetrie se bazeaza securitatea RSA.
Distributia primelor
π(x) ~ x / ln(x). Cu cat numerele sunt mai mari, cu atat primele sunt mai rare.