www.gmindo.web.id/forum
Forum ini sudah tidak dipakai lagi. Silakan ke forum baru di www.gmindo.web.id/forum Very Happy

Terima kasih

Pseudo-random Number Generator

Topik sebelumnya Topik selanjutnya Go down

Pseudo-random Number Generator

Post by Asuna on Mon 11 Mar 2013, 21:47

Bilangan acak (random) adalah bilangan yang tidak dapat diprediksi dan terdistribusi secara uniform pada rentang tertentu. Secara umum pembangkitan bilangan acak terdiri dari dua metode, yaitu:
1. Metode fisik: dadu, roulette wheel, lotre, dll
2. Metode numerik/aritmetik.

Pembangkit bilangan acak secara matematis menggunakan fungsi matematis yang sekuensial, tiap bilangan baru merupakan fungsi deterministik dari bilangan-bilangan sebelumnya (rekuren). Basis dari fungsi rekursif tersebut disebut umpan (seed), yaitu satu atau lebih bilangan awal. Tidak ada fungsi matematis yang dapat menghasilkan deret bilangan acak yang sempurna/natural. Oleh karena itu pembangkit semacam itu disebut pseudo-random number generator (PRNG).


Linear Congruential Generator (LCG)

Merupakan PRNG yang paling sederhana dan lebih mudah & cepat dikomputasi. Fungsinya adalah sebagai berikut: Xn = (aXn – 1 + b) mod m
dimana:
Xn = bilangan acak ke-n dari deretnya
a, b = koefisien parameter
m = modulus
Basis dari fungsi ini adalah X0 yang disebut seed. Berikut contohnya.
Spoiler:

LCG memiliki kelemahan, yaitu mempunyai periode tertentu yang selalu lebih kecil dari m. Pada contoh di atas, deret bilangan berulang dengan periode 16. Dengan menemukan perulangan, deret bilangan menjadi lebih mudah ditebak. Kita mungkin dapat memperkuatnya dengan menggunakan nilai m yang lebih besar dan nilai a & b tertentu yang mengakibatkan periode penuh (m-1).

Dengan demikian, LCG tidak aman untuk menghindari pembobolan, terutama untuk keperluan kriptografi. Secara praktis, LCG berguna untuk aplikasi non-kriptografi seperti game dan simulasi, karena LCG efisien dan memperlihatkan sifat statistik yang bagus dan sangat tepat untuk uji-uji empirik.


Cryptographically Secure Pseudorandom Generator (CSPRNG)

Pembangkit bilangan acak yang digunakan dalam kriptografi memiliki syarat yang penting, yaitu lolos uji keacakan statistik dan tahan terhadap serangan yang bertujuan untuk memprediksi bilangan acak yang dihasilkan. Pembangkit semacam ini disebut cryptographically secure pseudorandom generator (CSPRNG).


Blum Blum Shub (BBS)

BBS merupakan CSPRNG yang paling sederhana dan efisien dalam komputasi. BBS dibuat pada tahun 1986 oleh Lenore Blum, Manuel Blum, dan Michael Shub. Berikut algoritmanya.
1. Pilih dua buah bilangan prima rahasia, p dan q, yang masing-masing kongruen dengan 3 modulo 4.
2. Kalikan keduanya menjadi n = pq. Bilangan m ini disebut bilangan bulat Blum
3. Pilih bilangan bulat acak lain, s, sebagai umpan sedemikian sehingga:
(i) 2 <= s < n
(ii) s dan n relatif prima
kemudian hitung x0 = s2 mod n
4. Barisan bit acak dihasilkan dengan melakukan iterasi berikut sepanjang yang diinginkan:
(i) Hitung xi = xi – 1 2 mod n
(ii) zi = bit LSB (Least Significant Bit) dari xi
Barisan bit acak adalah z1, z2, z3, …

Keamanan BBS terletak pada sulitnya memfaktorkan n. Nilai n tidak perlu rahasia dan dapat visible secara publik.

BBS tidak dapat diprediksi dari arah kiri dan tidak dapat diprediksi dari arah kanan pula, artinya jika diberikan barisan bit yang dihasilkan oleh BBS, kriptanalis tidak dapat memprediksi barisan bit sebelumnya dan barisan bit sesudahnya.


Fungsi Chaos

Fungsi chaos adalah fungsi yang bersifat sangat peka terhadap nilai awal. Sensitifitas fungsi tersebut memperlihatkan keacakan bilangan yang dihasilkannya. Berikut contoh fungsi chaos.

a. Persamaan Logistik
xi+1 = r xi (1 – xi)
dimana:
r = laju pertumbuhan ( 0 <= r <= 4 )
x = nilai-nilai chaos (0 <= x <= 1)

b. Henon map
xn = 1 + b(xn–2 – xn–3) + cx2n–2
avatar
Asuna
Global Moderator
Global Moderator

100%
Jumlah posting : 1711
Points : 1901
Join date : 10.01.13

Lihat profil user

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by zebrakelabu on Tue 12 Mar 2013, 01:01

wah wah dahsyat Very Happy

ini sih lebih keren dari trit gw Jempol2

hmmmm ternyata ada fungsi chaos? tapi itu tetep tergolong pseudo kan?
avatar
zebrakelabu
Admin
Admin

100%
Jumlah posting : 933
Points : 960
Join date : 06.01.13
Lokasi : Jakarta

Lihat profil user http://www.project25games.com

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by DONI on Tue 12 Mar 2013, 05:09

nambah pengetahuan nih...
avatar
DONI
GM Beginner
GM Beginner

75%
Jumlah posting : 104
Points : 110
Join date : 14.02.13

Lihat profil user

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by Kevin Blaze Coolerz on Tue 12 Mar 2013, 14:18

wah, gk ngerti Ngakak

ini utk memperoleh nilai scara random kan? kyk fungsi random() pada GM.
dan kok kliatan ny ribet bnget? Bingung

atau mksd dri trit di atas itu kyk enkripsi nilai gitu, jdi contoh ny kyk gini:
ak mau meng-enkripsi nilai pada var uang (uang=1000), trus ak pke salah satu metode di atas, yaitu yg BBS. trus ak menentukan 2 nilai rahasia, yaitu p&q = 1 & 9

trus stelah di proses, jdi ny kyk gini "uang = 1000+NILAI_BBS"

dan misalkan kalo ak mau enkrip exp, maka ak akan merubah nilai p&q lgi, shingga ak mndapat nilai yg berbeda lgi dri nilai BBS tdi. bgitu kah konsep / fungsi dari tulisan" diatas? Very Happy
avatar
Kevin Blaze Coolerz
Admin
Admin

100%
Jumlah posting : 3323
Points : 3795
Join date : 06.01.13
Age : 22
Lokasi : Palembang

Lihat profil user http://kevin-blaze-coolerz.blogspot.com/

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by Asuna on Tue 12 Mar 2013, 14:36

@zebrakelabu
semua fungsi pembangkit bilangan acak bersifat deterministik (karena jelas ditentukan seed / nilai awalnya), maka termasuk pseudo-random juga~

@Kevin Blaze Coolerz
hmm, kira2 prosesnya seperti gini:
- pertama nilai seed ditentukan terlebih dahulu, bisa dilakukan secara otomatis dengan randomize() dimana nilai seed ditentukan dari clock CPU, atau secara manual dengan random_set_seed(seed)
- lalu nilai random berikutnya dihitung dengan fungsi random()
- jika kita langsung menggunakan fungsi random(), fungsi tsb sebetulnya memanggil fungsi randomize() terlebih dahulu

jadi, untuk keperluan kriptografi, pake fungsi random_set_seed(seed) terlebih dahulu

Note: nilai seed berada pada rentang 32-bit integer (-2147483648 ~ 2147483647)
avatar
Asuna
Global Moderator
Global Moderator

100%
Jumlah posting : 1711
Points : 1901
Join date : 10.01.13

Lihat profil user

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by Kevin Blaze Coolerz on Tue 12 Mar 2013, 16:53

@asuna:
ooh, I see Very Happy thx atas penjelasan ny

gk di buat gmk ny nih? Razz
avatar
Kevin Blaze Coolerz
Admin
Admin

100%
Jumlah posting : 3323
Points : 3795
Join date : 06.01.13
Age : 22
Lokasi : Palembang

Lihat profil user http://kevin-blaze-coolerz.blogspot.com/

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by Asuna on Tue 12 Mar 2013, 17:09

^
tinggal coba contoh sederhana ini aja:

Code:
random_set_seed(12345678)
show_message(random(10))
show_message(random(10))
show_message(random(10))
show_message(random(10))
show_message(random(10))
avatar
Asuna
Global Moderator
Global Moderator

100%
Jumlah posting : 1711
Points : 1901
Join date : 10.01.13

Lihat profil user

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by Kevin Blaze Coolerz on Wed 13 Mar 2013, 19:05

^
hmm, stelah di coba, trnyata hasil nya random membingungkan, fungsi set_seed seakan" gk brguna Hammer

ak kira kalo seed = X, maka nilai random akan mendekati X

*setelah baca ulang koment kamu

semua fungsi pembangkit bilangan acak bersifat deterministik (karena jelas ditentukan seed / nilai awalnya)

seed = nilai awal, jdi GM itu sdh menentukan default utk seed ny ya? Very Happy
knp kmu set seed ny jdi 12345678, dan padahal yg di pke di script cma random(10) ?

btw ak jdi bingung lgi Hammer
avatar
Kevin Blaze Coolerz
Admin
Admin

100%
Jumlah posting : 3323
Points : 3795
Join date : 06.01.13
Age : 22
Lokasi : Palembang

Lihat profil user http://kevin-blaze-coolerz.blogspot.com/

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by Asuna on Wed 13 Mar 2013, 22:23

^
seems you don't understand what seed really means
coba run ulang, untuk nilai seed yang sama, deret bilangan randomnya mestinya sama juga
avatar
Asuna
Global Moderator
Global Moderator

100%
Jumlah posting : 1711
Points : 1901
Join date : 10.01.13

Lihat profil user

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by zebrakelabu on Thu 14 Mar 2013, 16:20

contohnya kev, mungkin kamu pernah main minecraft ato semacamnya (android ada yang pocket edition dan free)

waktu generate world, kita dikasi pilihan isian World Generator seed. Kalo kita biarkan kosong maka minecraft akan membuatkan dunia yang benar2 random. Kalo kita isikan sesuatu (misalnya nama kamu) maka isian ini akan diconvert menjadi seed bagi pembuatan dunia game. Dengan isian yang sama di hp lain maka dunianya bisa tetap sama bentuknya, walau digenerate secara random.
avatar
zebrakelabu
Admin
Admin

100%
Jumlah posting : 933
Points : 960
Join date : 06.01.13
Lokasi : Jakarta

Lihat profil user http://www.project25games.com

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by Kevin Blaze Coolerz on Thu 14 Mar 2013, 17:59

Asuna wrote:^
seems you don't understand what seed really means
coba run ulang, untuk nilai seed yang sama, deret bilangan randomnya mestinya sama juga
tdi emg blum ngerti, tpi pas baca komen om adit skrg jdi ngerti Very Happy terima kasih tong feng

zebrakelabu wrote:contohnya kev, mungkin kamu pernah main minecraft ato semacamnya (android ada yang pocket edition dan free)

waktu generate world, kita dikasi pilihan isian World Generator seed. Kalo kita biarkan kosong maka minecraft akan membuatkan dunia yang benar2 random. Kalo kita isikan sesuatu (misalnya nama kamu) maka isian ini akan diconvert menjadi seed bagi pembuatan dunia game. Dengan isian yang sama di hp lain maka dunianya bisa tetap sama bentuknya, walau digenerate secara random.

blum prnh main Hammer
tpi ak ngerti kok mksd ny Very Happy thx om atas penjelasan ny
avatar
Kevin Blaze Coolerz
Admin
Admin

100%
Jumlah posting : 3323
Points : 3795
Join date : 06.01.13
Age : 22
Lokasi : Palembang

Lihat profil user http://kevin-blaze-coolerz.blogspot.com/

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by faris_mfaf on Wed 30 Mar 2016, 04:09

Ou gitu toh.. makasih baru tahu.. ditunggu selanjutnya

faris_mfaf
Newbie
Newbie

100%
Jumlah posting : 3
Points : 2
Join date : 29.03.16

Lihat profil user

Kembali Ke Atas Go down

Re: Pseudo-random Number Generator

Post by Sponsored content


Sponsored content


Kembali Ke Atas Go down

Topik sebelumnya Topik selanjutnya Kembali Ke Atas


 
Permissions in this forum:
Anda tidak dapat menjawab topik