Metode LCM (Linear Congruent Method)

Bilangan acak yang dibangkitkan oleh komputer merupakan bilangan acak semu, karena pembangkitannya menggunakan operasi-operasi aritmatika. Banyak algoritma atau metode yang dapat digunakan untuk membangkitkan bilangan acak. Di dalam buku teks statistik klasik, angka-angka acak diciptakan dengan mengambil bola yang dinomori ke luar dari suatu kotak yang berisi sejumlah bola bernomor yang diketahui jumlahnya. Jika jumlah bola yang ada didalam kotak jumlahnya sedikit, maka hal tersebut masih mungkin dilakukan. Tetapi jika jumlah bolanya dalam jumlah yang sangat besar, maka hal tersebut akan susah dan tidak efektif dilakukan. Terlepas dari hal itu, ada isu yang lain yang meragukan bahwa mengambil bola bernomor dari suatu kotak besar merupakan suatu proses acak dengan kesempatan sama untuk semua bola. Karena hal tersebut dan pertimbangan lainnya, maka dilakukan komputerisasi generator bilangan random/acak. Sesungguhnya, bahasa pemrograman tingkat tinggi menawarkan sedikitnya satu format dari generator bilangan random. Pembuatan angkaangka yang acak bukan merupakan hal yang mudah, karena komputer adalah suatu mesin deterministik. Karena itulah mustahil untuk membuat angka-angka acak/bilangan yang benar-benar random tanpa adanya perangkat keras tambahan.

True random number secara definisi tidak dapat terprediksi. TRNG dilakukan dengan melakukan sampling entropi sumber dari alam dan memprosesnya melalui komputer. Misalnya adalah bilangan random yang dihasilkan oleh Random.org dan Laverand.sgi.com. Random.org menggunakan atmospheric noise dari radio dan Lavarand.sgi.com menggunakan Lava Lite® lamps sebagai entropi sumber. Entropi sumber yang lain yang cukup bagus adalah radioaktivitas yang juga digunakan oleh Fourmilab di Swiss untuk membangkitkan true random number. 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 seperti untuk simulasi dalam ilmu fisika, matematika, biologi dan sebagainya, dan juga merupakan hal yang sangat penting dalam dunia kriptografi.

Linear Congruent Method (LCM) merupakan metode pembangkitkan bilangan acak yang banyak digunakan dalam program komputer. LCM memanfaatkan model linier untuk membangkitkan bilangan acak yang didefinisikan dengan :

Xn+1 = (aXn+c)      (mod m)

Dimana :       xn = adalah bil. acak ke n

                          a dan c adalah konstanta LCM

                    m adalah batas maksimum bilangan acak

Ciri khas dari LCM adalah terjadi pengulangan pada periode waktu tertentu atau setelah sekian kali pembangkitan, hal ini adalah salah satu sifat dari metode ini, dan pseudo random generator pada umumnya. Penentuan konstanta LCM (a, c dan m) sangat menentukan baik tidaknya bilangan acak yang diperoleh dalam arti memperoleh bilangan acak yang seakan-akan tidak terjadi pengulangan. Dapat dilihat dari beberapa contoh seperti di bawah ini :

Rumus :

 
Xn+1 = (aXn+c)      (mod m)

a = 4

c = 7

x0 = 3

m = 27

Penyelesaian :

X(0) = 3

X(1) = (4 (3) + 7) mod 27 = 19

X(2) = (4 (19) + 7) mod 27 = 2

X(3) = (4 (2) + 7) mod 27 = 15

X(4) = (4 (15) + 7) mod 27 = 13

X(5) = (4 (13) + 7) mod 27 = 5

X(6) = (4 (5) + 7) mod 27 = 0

X(7) = (4 (0) + 7) mod 27 = 7

X(8) = (4 (7) + 7) mod 27 = 8

X(9) = (4 (8) + 7) mod 27 = 12

X(10) = (4 (12) + 7) mod 27 = 1

X(11) = (4 (1) + 7) mod 27 = 11

X(12) = (4 (11) + 7) mod 27 = 24

X(13) = (4 (24) + 7) mod 27 = 22

X(14) = (4 (22) + 7) mod 27 = 14

X(15) = (4 (14) + 7) mod 27 = 9

X(16) = (4 (9) + 7) mod 27 = 16

X(17) = (4 (10) + 7) mod 27 = 17

X(18) = (4 (17) + 7) mod 27 = 21

X(19) = (4 (21) + 7) mod 27 = 10

X(20) = (4 (10) + 7) mod 27 = 20

X(21) = (4 (20) + 7) mod 27 = 6

X(22) = (4 (6) + 7) mod 27 = 4

X(23) = (4 (4) + 7) mod 27 = 23

X(24) = (4 (23) + 7) mod 27 = 18

X(25) = (4 (18) + 7) mod 27 = 25

X(26) = (4 (25) + 7) mod 27 = 26

Bilangan acak yang dibangkitkan 1 sampai 26  tidak terlihat pengulangan secara periodik.