Skaičių teorija ir modulinė aritmetika: uždaviniai su sprendimais žingsnis po žingsnio

1Liekanos ir kongruencijos

Dalijant a iš n gaunamas dalmuo q ir liekana r: a = q·n + r, kur 0 ≤ r < n. Liekana žymima a mod n. Neigiamam skaičiui q taip pat neigiamas: −3 = −1·7 + 4, taigi −3 mod 7 = 4.

Du skaičiai yra kongruentūs moduliu n, a ≡ b (mod n), kai duoda tą pačią liekaną, t. y. kai n dalija a − b.

Liekanas galima redukuoti kiekviename žingsnyje, taip skaičiai išlieka maži:

Pavyzdžiui, 47·58 mod 9: 47 ≡ 2 ir 58 ≡ 4, taigi 47·58 ≡ 8 (mod 9).

2Euklido algoritmas

Didžiausias bendrasis daliklis gcd(a, b) yra didžiausias skaičius, dalijantis abu. Euklido algoritmas naudoja gcd(a, b) = gcd(b, a mod b):

1. Padalykite: a = q·b + r.
2. Pakeiskite (a, b) į (b, r).
3. Kartokite, kol liekana bus 0. Paskutinė nenulinė liekana yra DBD.

Mažiausias bendrasis kartotinis išplaukia iš jo: lcm(a, b) = a·b / gcd(a, b).

3Atvirkštiniai skaičiai ir išplėstinis algoritmas

Skaičiaus a atvirkštinis moduliu n yra skaičius x, kad a·x ≡ 1 (mod n). Jis egzistuoja tik tada, kai gcd(a, n) = 1.

Išplėstinis Euklido algoritmas vykdo Euklido algoritmą porai (n, a) ir kiekvienai liekanai išsaugo koeficientą t, kad kiekviena liekana r ≡ t·a (mod n). Pradėkite nuo t = 0 skaičiui n ir t = 1 skaičiui a; kiekvienas naujas t yra t dviem eilutėmis aukščiau minus q kartų t viena eilute aukščiau. Pasirodžius liekanai 1, jos t yra atvirkštinis skaičius.

Turint atvirkštinį skaičių, kongruencija a·x ≡ b (mod n) išsprendžiama x ≡ a⁻¹·b. Kai d = gcd(a, n) didesnis už 1, yra d sprendinių, jei d dalija b, o priešingu atveju sprendinių nėra.

Dvi kongruencijos su tarpusavyje pirminiais moduliais, x ≡ r₁ (mod m₁) ir x ≡ r₂ (mod m₂), turi lygiai vieną sprendinį moduliu m₁·m₂ (Kinų liekanų teorema). Užrašykite x = r₁ + m₁k ir spręskite k atžvilgiu.

4Moduliniai laipsniai ir RSA

Kartotinis kėlimas kvadratu greitai apskaičiuoja aᵏ mod n: užrašykite k dvejetainiu pavidalu, raskite a, a², a⁴, a⁸, … mod n keldami kvadratu ir redukuodami, ir sudauginkite laipsnius, kurių bitas lygus 1.

Mažoji Ferma teorema: pirminiam p, nedalijančiam a, aᵖ⁻¹ ≡ 1 (mod p). Taigi rodiklį galima redukuoti moduliu p − 1.

RSA raktas sudaromas iš dviejų pirminių skaičių p ir q:

1. n = p·q ir φ(n) = (p − 1)(q − 1).
2. Pasirinkite e, kad gcd(e, φ(n)) = 1; (n, e) yra viešasis raktas.
3. Apskaičiuokite d = e⁻¹ mod φ(n): tai privatusis raktas.
4. Užšifruokite c = mᵉ mod n; iššifruokite m = cᵈ mod n.

Oilerio φ(n) skaičiuoja skaičius nuo 1 iki n, tarpusavyje pirminius su n: pirminiam skaičiui φ(p) = p − 1, φ(pᵏ) = pᵏ − pᵏ⁻¹, o tarpusavyje pirminių daugiklių atveju φ yra multiplikatyvi.

5Dažnos klaidos

• Duoti neigiamą liekaną neigiamam skaičiui: −17 mod 5 yra 3, o ne −2.
• Sustoti ties pirmąja Euklido algoritmo liekana, o ne paskutine nenuline.
• Pamiršti pridėti n prie neigiamo išplėstinio algoritmo koeficiento.
• Skaičiuoti RSA rodiklį d moduliu n, o ne moduliu φ(n).
• Pagal Ferma teoremą redukuoti rodiklį moduliu p, o ne p − 1.

6Kaip atrodo egzamino uždaviniai

• Lengvas: DBD ir liekanos. Vykdote Euklido algoritmą DBD ar MBK rasti, ieškote neigiamų skaičių liekanų ir redukuojate sumas bei sandaugas moduliu n.
• Vidutinis: atvirkštiniai skaičiai ir kongruencijos. Randate modulinius atvirkštinius skaičius išplėstiniu algoritmu, sprendžiate tiesines kongruencijas, jungiate dvi kongruencijas Kinų liekanų teorema ir skaičiuojate Oilerio φ(n).
• Sunkus: moduliniai laipsniai ir RSA. Naudojate kartotinį kėlimą kvadratu ir Ferma teoremą, sprendžiate kongruencijas su keliais sprendiniais, randate RSA privačiuosius rodiklius, šifrogramas ir iššifruotus pranešimus.