Latihan 7.5 Latihan Tambahan: Keprimaan dan Faktorisasi

Dalam sistem kriptografi RSA, kemampuan menemukan bilangan prima besar dengan mudah sangatlah penting. Selain itu, sistem ini tidak aman jika kita dapat memfaktorkan bilangan komposit yang merupakan hasil kali dua bilangan prima besar. Pendekatan dasar untuk kedua masalah ini cukup sederhana. Untuk menentukan apakah bilangan \(n\) prima atau untuk memfaktorkan \(n\text{,}\) kita dapat menggunakan pembagian percobaan. Kita cukup membagi \(n\) dengan \(d = 2, 3, \ldots, \sqrt{n}\text{.}\) Kita akan memperoleh suatu faktorisasi, atau \(n\) prima jika tidak ada \(d\) yang membagi \(n\text{.}\) Masalahnya, komputasi semacam ini memerlukan waktu yang terlampau lama jika \(n\) sangat besar.

1.

Algoritma yang lebih baik untuk memfaktorkan bilangan bulat positif ganjil adalah algoritma faktorisasi Fermat.

Misalkan \(n= ab\) adalah bilangan komposit ganjil. Buktikan bahwa \(n\) dapat ditulis sebagai selisih dua kuadrat sempurna:

\begin{equation*} n = x^2 - y^2 = (x - y)(x + y)\text{.} \end{equation*}

Akibatnya, bilangan bulat positif ganjil dapat difaktorkan tepat ketika kita dapat menemukan bilangan bulat \(x\) dan \(y\) sedemikian sehingga \(n = x^2 - y^2\text{.}\)
Tulislah program yang menerapkan algoritma faktorisasi berikut berdasarkan pengamatan pada bagian (a). Ekspresi ceiling(sqrt(n)) berarti bilangan bulat terkecil yang lebih besar daripada atau sama dengan akar kuadrat \(n\text{.}\) Tulislah program lain untuk melakukan faktorisasi dengan pembagian percobaan, lalu bandingkan kecepatan kedua algoritma. Algoritma mana yang lebih cepat, dan mengapa?

x := ceiling(sqrt(n))
y := 1

1 : while x^2 - y^2 > n do
    y := y + 1

if x^2 - y^2 < n then
    x := x + 1
    y := 1
    goto 1
else if x^2 - y^2 = 0 then
    a := x - y
    b := x + y
    write n = a * b

2. Uji Keprimaan.

Ingat kembali Teorema Kecil Fermat dari Bab 6. Misalkan \(p\) prima dengan \(\gcd(a, p) = 1\text{.}\) Maka \(a^{p-1} \equiv 1 \pmod{p}\text{.}\) Kita dapat menggunakan Teorema Kecil Fermat sebagai uji penyaring untuk bilangan prima. Sebagai contoh, \(15\) tidak mungkin prima karena

\begin{equation*} 2^{15-1} \equiv 2^{14} \equiv 4 \pmod{15}\text{.} \end{equation*}

Namun, \(17\) berpotensi prima karena

\begin{equation*} 2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}\text{.} \end{equation*}

Bilangan komposit ganjil \(n\) disebut pseudoprima jika

\begin{equation*} 2^{n-1} \equiv 1 \pmod{n}\text{.} \end{equation*}

Manakah di antara bilangan berikut yang prima dan manakah yang pseudoprima?

\(\displaystyle 342\)
\(\displaystyle 811\)
\(\displaystyle 601\)
\(\displaystyle 561\)
\(\displaystyle 771\)
\(\displaystyle 631\)

3.

Misalkan \(n\) adalah bilangan komposit ganjil dan \(b\) adalah bilangan bulat positif sedemikian sehingga \(\gcd(b, n) = 1\text{.}\) Jika \(b^{n-1} \equiv 1 \pmod{n}\text{,}\) maka \(n\) disebut pseudoprima terhadap basis \(b\text{.}\) Tunjukkan bahwa \(341\) merupakan pseudoprima terhadap basis \(2\text{,}\) tetapi bukan terhadap basis \(3\text{.}\)

4.

Tulislah program untuk menentukan semua bilangan prima yang kurang dari \(2000\) dengan pembagian percobaan. Tulislah program kedua yang menentukan semua bilangan kurang dari \(2000\) yang merupakan bilangan prima atau pseudoprima. Bandingkan kecepatan kedua program tersebut. Berapa banyak pseudoprima di bawah \(2000\text{?}\)

Terdapat bilangan komposit yang merupakan pseudoprima untuk setiap basis yang relatif prima terhadap bilangan tersebut. Bilangan-bilangan ini disebut bilangan Carmichael. Bilangan Carmichael pertama adalah \(561 = 3 \cdot 11 \cdot 17\text{.}\) Pada tahun 1992, Alford, Granville, dan Pomerance membuktikan bahwa terdapat tak berhingga banyak bilangan Carmichael [4]. Namun, bilangan Carmichael sangat jarang. Hanya ada \(2163\) bilangan Carmichael yang kurang dari \(25 \times 10^9\text{.}\) Untuk uji keprimaan yang lebih canggih, lihat [1], [6], atau [7].

Sblm.Paling Atas Lanjut