Sirait Blog's: MATERI KULIAH

MATERI KULIAH

Pembangkitan Bilangan Prima

· Sebagian besar algoritma kunci-publik menggunakan bilangan prima sebagai salah satu nilai parameternya. Bilangan prima yang disarankan berkuran besar sehingga penggunaan tipe data bilangan bulat yang besar mutlak diperlukan.

· Cara lain untuk membangkitkan bilangan prima adalah:

1. Bangkitkan bilangan acak p sepanjang n angka.

2. Uji brute force terhadap p dengan membagi p dengan bilangan prima kurang dari 256. Pengujian ini akan menghilangan bilangan bukan prima sebesar 80%. Yang paling mangkus adalah membagi p dengan bilangan prima yang lebih kecil dari 2000.

3. Jika p berhasil melewati uji brute force, uji p dengan algoritma Lehmann.

Algoritma Lehmann

{ Masukan: p (yang akan diuji keprimaannya)

Keluaran: p adalah prima atau tidak prima }

(a) Bangkitkan bilangan acak a yang lebih kecil dari p.

(b) Hitung a^{(p – 1)/2} mod p.

(d) Jika a^{(p – 1)/2} º 1 atau –1 (mod p), maka peluang p bukan prima adalah 50%.

4. Ulangi pengujian dengan algoritma Lehmann di atas sebanyak t kali (dengan nilai a yang berbeda). Jika hasil perhitungan langkah (b) sama dengan 1 atau –1, tetapi tidak selalu sama dengan 1, maka peluang p adalah prima mempunyai kesalahan tidak lebih dari 1/2^t.

· Bilangan acak a yang digunakan pada algoritma Lehmann dapat dipilih nilai yang kecil agar perhitungan lebih cepat. Sedangkan jumlah pengujian yang disarankan adalah lima kali.

· Selain algoritma Lehmann, metode lain yang banyak digunakan untuk menguji bilangan prima adalah Rabin-Miller.

Algoritma Rabin-Miller

{ Sebelum algoritma ini dijalankan, lakukan prosedur

berikut:

1. Bangkitkan bilanagn p yang akan diuji keprimaannya.

2. Hitung b, yang dalam hal ini 2^b adalah nilai pangkat 2 terbesar yang habis membagi p – 1.

3. Hitung m sedemikian sehingga p = 1 + 2^bm.

Masukan: p, m, dan b

Keluaran: p adalah prima atau tidak prima. }

(a) Bangkitkan bilangan acak a yang lebih kecil dari p.

(b) Nyatakan j = 0 dan hitung z = a^m mod p.

(d) Jika z > 0 dan z = 1, maka p bukan prima.

(e) Nyatakan j = j + 1. Jika j < b dan z ¹ p – 1, nyatakan z = z² mod p dan kembali ke langkah (d). Jika z = p – 1, maka p lolos pengujian dan mungkin prima.

(f) Jika j = b dan z ¹ p – 1, maka p tidak prima.

· Ulangi pengujian dengan algoritma Rabin-Miller di atas sebanyak t kali (dengan nilai a yang berbeda).

4. Tabel Bilangan Prima dari 2 – 256

2	3	5	7	11	13	17	19	23	29
31	41	43	47	53	59	61	67	71	73
79	83	89	97	101	103	107	109	113	127
131	139	149	151	157	163	167	173	179	181
191	193	199	211	223	227	229	233	239	241
251

Sirait Blog's

Do the best for your self :)

MATERI KULIAH

Algoritma Lehmann

Algoritma Rabin-Miller

0 Comments »

Leave a comment

Archives

2	3	5	7	11	13	17	19	23	29
31	41	43	47	53	59	61	67	71	73
79	83	89	97	101	103	107	109	113	127
131	139	149	151	157	163	167	173	179	181
191	193	199	211	223	227	229	233	239	241
251

2	3	5	7	11	13	17	19	23	29
31	41	43	47	53	59	61	67	71	73
79	83	89	97	101	103	107	109	113	127
131	139	149	151	157	163	167	173	179	181
191	193	199	211	223	227	229	233	239	241
251

2	3	5	7	11	13	17	19	23	29
31	41	43	47	53	59	61	67	71	73
79	83	89	97	101	103	107	109	113	127
131	139	149	151	157	163	167	173	179	181
191	193	199	211	223	227	229	233	239	241
251