Algoritme index-calculus untuk menyelesaikan masalah logaritma diskret pada grup Z*p

Abstract

Masalah logaritma diskret pada grup Z, adalah menentukan x sedemikian sehingga a = ẞ mod p, dengan a merupakan generator dari Z. Salah satu algoritme yang dapat menyelesaikan masalah tersebut adalah algoritme index-calculus. Algoritme index-calculus terdiri atas tiga fase utama. Fase pertama mencari relasi linear yang menghubungkan logaritma dari anggota basis faktor, fase kedua adalah menyelesaikan sistem linear yang terbentuk menggunakan teknik aljabar linear, fase ketiga adalah mencari nilai dari logaritma yang diinginkan dengan menggunakan logaritma dari bilangan prima yang ada di dalam basis faktor yang didefinisikan sebagai list t bilangan prima pertama. Algoritme ini menggunakan teorema dasar aritmatika, sifat logaritma diskret dan konsep smoothness sebagai alat utama, dan dalam implementasinya pada program, penulis menggunakan metode trial division sebagai alat uji smoothness suatu bilangan.