Penyelesaian Masalah Logaritma Diskrit pada Zp*

NABILA PRATIWI, Dr. Diah Junia Eksi Palupi, M.S

2021 | Skripsi | S1 MATEMATIKA

Keamanan dari sistem kripto El-Gamal terletak pada fungsi enkripsi dan fungsi dekripsinya yang memanfaatkan nilai logaritma diskrit dari kunci publik beta. Beberapa metode yang dapat digunakan untuk menyelesaikan masalah logaritma diskrit pada Zp* dengan p bilangan prima antara lain algoritma Pohlig-Hellman, metode index calculus dan metode yang memanfaatkan bilangan smooth atas +- 1 pada Zp*. Tupel-4 (a,b,c,d) di Zp* dikatakan bilangan smooth atas +- 1 jika memenuhi ab equivalen 1 (mod p), cd equivalen 1 (mod p), ac equivalen -1 (mod p) dan bd equivalen -1 (mod p). Terdapat dua metode yang memanfaatkan bilangan smooth atas +- 1 yaitu Algoritma I dan Algoritma II. Dari keempat metode tersebut diperoleh bahwa algoritma Pohlig-Hellman membutuhkan waktu yang lebih singkat dalam menyelesaikan masalah logaritma diskrit pada Zp* dibandingkan dengan tiga metode lainnya.

The security of El-Gamal cryptosystem lies on the encryption and decryption function which use the discrete logarithm value of public key beta. Several methods that can be used to solve the discrete logarithm problem in Zp* with prime number p are the Pohlig-Hellman algorithm, index calculus method, and method that use the smooth number of +- 1 in Zp*. The 4-tuple (a,b,c,d) in Zp* is called smooth number of +- 1 if ab equivalen 1 (mod p), cd equivalen 1 (mod p), ac equivalen -1 (mod p), and bd equivalen -1 (mod p). There are two methods which use those characteristics, namely Algorithm I and Algorithm II. Among those methods, the Pohlig-Hellman algorithm is quicker in solving the discrete logarithm problem on Zp* in comparison with the other three methods.

Kata Kunci : masalah logaritma diskrit di Zp*, algoritma Pohlig-Hellman, metode index calculus, bilangan smooth atas +- 1 / discrete logarithm problem in Zp*, Pohlig-Hellman algorithm, index calculus method, smooth number of +- 1.