69
Menggunakan
Teorema 2.1.4.8 diperoleh bahwa f ( p) = p - 1. Sehingga diperoleh
a
p
-1
=
a
f
(m)
=
1
(mod p
)
. Dengan demikian teorema terbukti.
Dengan
hasil
yang diperoleh pada Teorema 2.1.5.1, dapat dibentuk sebuah
algoritma tes keprimaan, sebagai berikut:
Algoritma 2.7 : Tes Fermat (Menezes, Oorschot and Vanstone, 1996)
Input
: Sebuah bilangan bulat positif ganjil
p
=
3
dan sebuah parameter
t
=
1
.
Output : Pernyataan “prima” atau “komposit”.
Langkah :
1. Untuk i dari 1 sampai t kerjakan:
1.1. Diambil sebarang bilangan bulat positif a,
2
=
a
=
p - 1
.
1.2. Hitung
y
=
a
p
-1
(mod p
)
.
1.3. Jika
y
?
1, maka output (“komposit”).
2. Output (“prima”).
Namun pada kenyataanya,
nilai
y
=
1
(mod p)
tidak
selamanya
menjamin bahwa
p adalah prima. Berikut diberikan contohnya.
Contoh 2.1.5.1. (Buchmann, 2000)
Diberikan p = 341. Diambil a = 2, dengan tes Fermat diperoleh
2
340
=
1
(mod 341)
yang
menyatakan
bahwa
341
adalah
bilangan
prima.
Namun
hal
ini
tidak
benar
karena
341
adalah bilangan komposit,
yaitu 341 = (11)(13). Dari
sini terbukti,
walaupun diperoleh
 |