|
Pseudo-tasodifiy ketma-ketlik generatorlariga qo'yiladigan talablar
|
| bet | 7/8 | | Sana | 28.01.2024 | | Hajmi | 358,33 Kb. | | #147686 |
Bog'liq tarjma3.3 Pseudo-tasodifiy ketma-ketlik generatorlariga qo'yiladigan talablar
Pseudo-tasodifiy ketma-ketlik generatorlari ma'lum shartlarni qondirishi kerak. Ularning yordami bilan olingan ketma-ketliklar bir xil taqsimotga ega bo'lishi kerak (yoki hech bo'lmaganda uniformaga yaqin). Bu hosil qilingan ikkilik ketma-ketlikdagi nollar soni ketma-ketlikda mavjud bo'lganlar soniga taxminan teng bo'lishi kerakligini anglatadi. Bundan tashqari, yaratilgan ketma-ketlikni tashkil etuvchi tasodifiy qiymatlar statistik jihatdan mustaqil bo'lishi kerak. Bu shuni anglatadiki, alohida bitlar yoki bitlar guruhlari o'rtasida hech qanday korrelyatsiya bo'lmasligi kerak.
Yaxshi psevdor tasodifiy ketma-ketlik generatori samarali bo'lishi kerak. Bu shuni anglatadiki, u imkon qadar qisqa vaqt ichida uzoq ketma-ketliklarni ishlab chiqarishi kerak. Bu talab real vaqtda ishlaydigan tizimlar uchun ayniqsa muhimdir. Bundan tashqari, kriptografiya masalalarida qo'llaniladigan psevdo-tasodifiy ketma-ketliklarning generatorlari turli xil hujumlarga va nostandart vaziyatlarga chidamli bo'lishi kerak. Bu shuni anglatadiki, tajovuzkor generatorning kirishlari, ichki holati yoki joriy yoki oldingi chiqish qiymati haqida ba'zi ma'lumotlarni bilsa ham, generatorning har qanday joriy, oldingi yoki keyingi chiqishini taxmin qila olmaydi.
Haqiqiy tasodifiy ketma-ketliklar generatorlaridan farqli o'laroq, psevdo-tasodifiy ketma-ketliklar generatori har doim kompyuter tizimining mumkin bo'lgan holatlarining cheklanganligi sababli ma'lum bir davrga ega. U siz xohlagancha katta bo'lishi mumkin, lekin u har doim cheklangan. Ketma-ketlik uzunligi bunday muddatdan oshib ketgandan so'ng, generator tomonidan ishlab chiqarilgan qiymatlar takrorlana boshlaydi. Shuning uchun hosil qilingan ketma-ketlikda aniq naqshlar paydo bo'lishining oldini olish uchun uning davri etarlicha katta bo'lishi kerak.
3.4 Pseudo-tasodifiy ketma-ketlik generatorlariga misollar
3.4.1 O'rta kvadrat algoritmi
Tarixiy jihatdan, birinchi PTKKGlardan biri 1946 yilda J. fon Neyman tomonidan taklif qilingan "kvadratning o'rtasi" algoritmi bo'lib, u quyidagi bosqichlardan iborat:
-razryadli dastlabki o`nlik rotsional soni tanlanadi (bu PTKKG ning boshlang`ich qiymati).
Har bir keyingi qadam uchun bu sonning kvadrati hisoblanadi ( -razryadli son).
Oldingi son kvadratining n ta o'rta raqamlari keyingi tasodifiy n-bit soni sifatida tanlanadi.
Biroq, shu tarzda olingan raqamlar bir-biriga bog'liq bo'lib chiqadi. Bundan tashqari, bu raqamlarning ketma-ketligi kichik davrga ega.
|
| |
