Linear Congruential Generator (LCG)

PNRG

Pseudorandom Number Generator (PNRG) atau dalam bahasa Indonesia Pembangkit bilangan acak semu adalah sebuah algoritma yang membangkitkan sebuah deret bilangan yang tidak benar-benar acak. Keluaran dari pembangkit bilangan acak semu hanya mendekati beberapa dari sifat-sifat yang dimiliki bilangan acak. Walaupun bilangan yang benar-benar acak hanya dapat dibangkitkan oleh perangkat keras pembangkit bilangan acak, bukannya oleh perangkat lunak komputer, akan tetapi bilangan acak semu banyak digunakan dalam beberapa hal seperti simulasi dalam ilmu fisika, matematika, biologi dan sebagainya, dan juga merupakan hal yang sangat penting dalam dunia kriptografi. Beberapa algoritma enkripsi baik yang simetris maupun nirsimetris memerlukan bilangan acak sebagai parameter masukannya seperti parameter kunci pada algoritma kunci publik dan pembangkitan initialization vector (IV) pada algoritma kunci simetri. Walaupun terlihat sederhana untuk mendapatkan bilangan acak, tetapi diperlukan analisis matematika yang teliti untuk membangkitkan bilangan seacak mungkin (Ramadhan, 2007). Salah satu metodenya adalah linear congruential generator atau LCG.

LCG

Linear Congruential Generator atau jika diubah kedalam bahasa Indonesia menjadi Pembangkit Bilangan Acak Kongruen-Lanjar merupakan pembangkit bilangan acak yang sederhana, mudah dimengerti teorinya, dan juga mudah untuk diimplementasikan. LCG didefinisikan dalam relasi berulang berikut :

X_n = (aX_{n – 1} + b) mod m

Dimana :

X_n       =  bilangan acak ke-n dari deretnya
X_n-1    =  bilangan acak sebelumnya
a        =  faktor pengali
b        =  increment
m       =  modulus

X₀ adalah kunci pembangkit atau disebut juga umpan (seed). LCG mempunyai periode tidak lebih besar dari m, dan pada kebanyakan kasus periodenya kurang dari itu.  LCG mempunyai periode penuh (m – 1) jika memenuhi syarat berikut:

1. b relatif prima terhadap m.
2. a – 1 dapat dibagi dengan semua faktor prima dari m
3. a – 1 adalah kelipatan 4 jika m adalah kelipatan 4
4. m > maks (a, b, X₀)
5. a > 0, b > 0

Keunggulan LCG

Keunggulan LCG terletak pada kecepatannya dan hanya membutuhkan sedikit operasi bit. Sayangnya, LCG tidak dapat digunakan untuk kriptografi karena bilangan acaknya dapat diprediksi urutan kemunculannya. Oleh karena itu LCG tidak aman digunakan untuk kriptografi. Namun demikian, LCG tetap berguna untuk aplikasi non-kriptografi seperti simulasi, sebab LCG memperlihatkan sifat statistik yang bagus dan sangat tepat untuk uji-uji empirik (Putranto, 2010).

Semua dari beberapa algoritma untuk membangkitkan bilangan acak semu, tidak ada yang benar-benar dapat menghasilkan bilangan acak secara sempurna dalam arti benar-benar acak dan tanpa ada perulangan selama pembangkit yang digunakan adalah komputer yang memiliki sifat deterministik. Bilangan yang benar-benar acak hanya dapat dihasilkan oleh perangkat keras (hardware) (Ramadhan, 2007).