Introducere

Ați văzut lecția pe Criptografia modernă? La ultimul punct de control, cea mai populară întrebare adresată de utilizatori a fost aceasta:

(Traducere: Aș vrea să știu mai multe despre descompunerea în factori primi! Partea aceasta din matematică mi s-a părut interesantă și ar fi distractiv să o văd aplicată. Mulțumesc!) În această lecție am văzut că descompunerea în factori primi a jucat un rol esențial în createa lacătelor matematică. Un lacăt matematic (sau funcție într-un singur sens) necesită o procedură care se execută ușor, dar este greu de parcurs în sens invers.

De exemplu, dacă alegem aleator două numere prime foarte mari precum: P1 = 709 și P2 = 733

și le înmulțim, obținem: N = P1 * P2

N = 709 * 733 = 519697     (acest calcul se efectuează ușor)

Obținem două lucruri: un număr foarte mare (519697) și descompunerea în factori primi a acestuia (709 * 733)

Acum imaginează-ți că ascund descompunerea în factori primi și îți spun doar atât:

519697 = ? * ?     (este greu de calculat)

Dacă îți cer să descompui în factori primi, de unde ai începe? Nu te îngrijora, oricine poate avea dificultăți cu această problemă! Pentru a rezolva, trecem printr-o serie de încercări și eșecuri. Înmulțirea se calculează rapid (ușor), dar descompunerea în factori primi este înceată (grea). Acest fapt simplu constituie fundamentul pentru Schema de criptare RSA.

👁️ Urmărește acest grafic animat pentru a vedea diferența.

Totuși, înainte de a merge mai departe, trebuie să analizăm mai îndeaproape primul pas și să ne punem următoarea întrebare importantă: Când spunem "alege aleator două numere prime mari", cum procedăm rapid? Este aceasta o problemă ușoară?

Dacă te gândești puțin, până la urmă vei fi de acord cu mine că acest pas necesită, cel puțin, abilitatea de a verifica dacă un număr generat aleator (precum 99194853094755497) este număr prim sau număr compus. Găsești pe calculatorul tău un buton care să îți spună asta?

Eu nu văd un astfel de buton….Oare de ce?

Pentru a afla, să începem cu o provocare...