Bevezetés

Láttad a Modern kriptográfiáról szóló fejezetet? Az utolsó feladat kapcsán ez volt a leggyakoribb kérdése a felhasználóknak:

(Az angol szöveg fordítása: Szeretnék többet megtudni a prímtényezőkre bontásról! A matek feladatos rész menő volt, és tetszett az itt látható alkalmazás.) A leckében láthattuk, hogy a prímtényezőkre bontás milyen fontos szerepet játszik a matematikai lakatok készítése során. A matematikai lakat (az egyirányú függvény) készítéséhez olyan eljárásra van szükség, amit könnyű elvégezni, de nehéz visszacsinálni.

Például ha véletlenszerűen kiválasztok két nagy prímszámot, mondjuk: P1 = 709-et és P2 = 733-at,

és összeszorzom őket, ezt kapom: N = P1 · P2

N = 709 · 733 = 519697     (ezt könnyű kiszámítani)

Ezáltal két dologhoz jutok hozzá: egy nagy számhoz (519697) és a nagy szám prímtényezőihez (709 · 733).

Tegyük fel, hogy elrejtem a prímtényezős felbontást, és csak az ezt adom oda:

519697 = ? · ?     (ezt nehéz kiszámítani)

Ha szeretnéd megtalálni a prímtényezős felbontást, hogyan fognál neki? Ne ijedj meg, ez mindenkinek gondot okoz! A megoldáshoz egy csomó próbálkozás kell. A szorzást gyorsan ki lehet számítani (könnyű), a prímtényezős felbontás lassú (nehéz). Ez az egyszerű tény az alapja az RSA titkosítási eljárásnak.

👁️ Nézd meg ezt az animált grafikont, amely a különbséget illusztrálja.

Mielőtt továbbmegyünk, meg kell vizsgálnunk közelebbről az első lépést, és fel kell tenni egy fontos kérdést. Amikor azt mondjuk „véletlenszerűen kiválasztunk két nagy prímszámot”, ezt hogyan tudjuk gyorsan megcsinálni? Ez egy könnyű feladat?

Ha elgondolkodsz ezen, akkor rájössz arra, hogy ehhez a lépéshez minimum az kell, hogy ellenőrizni tudd, hogy egy véletlenszerűen generált szám (mint például 99194853094755497) prímszám-e vagy összetett szám. Van olyan gomb a számológépen, ami erre választ ad?

Én ilyet nem találok….Vajon miért?

Ahhoz, hogy megkapjuk erre a választ, nézzünk egy feladatot...