Teori nombor & aritmetik modulo: soalan latihan dengan penyelesaian langkah demi langkah

1Baki dan kongruen

Membahagi a dengan n memberi hasil bahagi q dan baki r: a = q·n + r dengan 0 ≤ r < n. Baki ditulis a mod n. Bagi nombor negatif, q juga negatif: −3 = −1·7 + 4, maka −3 mod 7 = 4.

Dua nombor adalah kongruen modulo n, a ≡ b (mod n), apabila keduanya meninggalkan baki yang sama, iaitu apabila n membahagi a − b.

Baki boleh dikurangkan pada setiap langkah, yang memastikan nombor kecil:

Contohnya 47·58 mod 9: 47 ≡ 2 dan 58 ≡ 4, maka 47·58 ≡ 8 (mod 9).

2Algoritma Euclid

Pembahagi sepunya terbesar gcd(a, b) ialah nombor terbesar yang membahagi kedua-duanya. Algoritma Euclid menggunakan gcd(a, b) = gcd(b, a mod b):

1. Bahagi: a = q·b + r.
2. Gantikan (a, b) dengan (b, r).
3. Ulang sehingga baki ialah 0. Baki bukan sifar yang terakhir ialah gcd.

Gandaan sepunya terkecil terhasil daripadanya: lcm(a, b) = a·b / gcd(a, b).

3Songsangan dan algoritma lanjutan

Songsangan a modulo n ialah nombor x dengan a·x ≡ 1 (mod n). Ia wujud tepat apabila gcd(a, n) = 1.

Algoritma Euclid lanjutan menjalankan Euclid pada (n, a) dan menyimpan pekali t bagi setiap baki, supaya setiap baki r ≡ t·a (mod n). Mulakan dengan t = 0 untuk n dan t = 1 untuk a; setiap t baharu ialah t dua baris di atas tolak q darab t satu baris di atas. Apabila baki 1 muncul, t-nya ialah songsangan.

Dengan songsangan, kongruen a·x ≡ b (mod n) diselesaikan dengan x ≡ a⁻¹·b. Apabila d = gcd(a, n) lebih besar daripada 1, terdapat d penyelesaian jika d membahagi b, dan tiada jika tidak.

Dua kongruen dengan modulus pasangan perdana relatif, x ≡ r₁ (mod m₁) dan x ≡ r₂ (mod m₂), mempunyai tepat satu penyelesaian modulo m₁·m₂ (teorem baki Cina). Tulis x = r₁ + m₁k dan selesaikan untuk k.

4Kuasa modular dan RSA

Kuasa dua berulang mengira aᵏ mod n dengan cepat: tulis k dalam perduaan, cari a, a², a⁴, a⁸, … mod n dengan mengkuasaduakan dan mengurangkan, dan darabkan kuasa yang bitnya 1.

Teorem kecil Fermat: untuk nombor perdana p yang tidak membahagi a, aᵖ⁻¹ ≡ 1 (mod p). Maka eksponen boleh dikurangkan modulo p − 1.

RSA membina kunci daripada dua nombor perdana p dan q:

1. n = p·q dan φ(n) = (p − 1)(q − 1).
2. Pilih e dengan gcd(e, φ(n)) = 1; (n, e) ialah kunci awam.
3. Hitung d = e⁻¹ mod φ(n): kunci persendirian.
4. Penyulitan c = mᵉ mod n; penyahsulitan m = cᵈ mod n.

φ(n) Euler mengira nombor dari 1 hingga n yang perdana relatif dengan n: φ(p) = p − 1 untuk nombor perdana, φ(pᵏ) = pᵏ − pᵏ⁻¹, dan φ bersifat multiplikatif untuk faktor perdana relatif.

5Kesilapan lazim

• Memberi baki negatif bagi nombor negatif: −17 mod 5 ialah 3, bukan −2.
• Menghentikan Euclid pada baki pertama dan bukan baki bukan sifar yang terakhir.
• Terlupa menambah n pada pekali negatif daripada algoritma lanjutan.
• Mengira eksponen RSA d modulo n dan bukan modulo φ(n).
• Mengurangkan eksponen modulo p dan bukan p − 1 dengan teorem Fermat.

6Rupa soalan peperiksaan

• Mudah: gcd dan baki. Anda menjalankan algoritma Euclid untuk gcd atau lcm, mencari baki bagi nombor negatif, dan mengurangkan hasil tambah serta hasil darab modulo n.
• Sederhana: songsangan dan kongruen. Anda mencari songsangan modular dengan algoritma lanjutan, menyelesaikan kongruen linear, menggabungkan dua kongruen dengan teorem baki Cina, dan mengira φ(n) Euler.
• Sukar: kuasa modular dan RSA. Anda menggunakan kuasa dua berulang dan teorem Fermat, menyelesaikan kongruen dengan beberapa penyelesaian, dan mencari eksponen persendirian RSA, teks sulit dan mesej yang dinyahsulit.