1.2. Zamonaviy generatorlarning ishlash asoslari
Bunga misol sifatida chiziqli va chiziqsiz kongruent generatorlar ni keltirish mumkin. Tizimli-nazariy yondashuv asosida yaratilgan uzluksiz shifrlash algoritmlarining bardoshliligi, bu algoritmlarda qo‘llanilgan akslantirishlarning nazariy va amaliy bir tomonlilik xususiyatlarining qay darajada ishonchliligini baholash bilan isbotlanadi.
Elementar rekkurent hisoblashlarga asoslangan psevdotasodifiy ketma-ketlik generatorlari ularda qo‘llanilgan akslantirishlarga ko‘ra chiziqli, multiplikativ, chiziqsiz turkumlarga bo‘linadi.
Ulardan yana biri chiziqli va multiplikativ kongruent generatorlardir. chiziqli kongruent generatorlar umumiy holatda xi+1=(axi +s )mod N formula bilan aniqlanuvchi rekkurent hisoblashga asoslangan. Dastlabki berilgan kirish parametrlari asosida ketma-ketliklar hosil qilinadi.
Kirish parametrlari:
17
N – chekli maydon xarakteristikasini ifodalovchi son, a va s - o‘zgarmas
musbat butun sonlar, x0 – boshlang‘ich butun qiymatli son;
Ketma-ketlikni tashkil etuvchi chiqish qiymatlari :
xi+1=(axi +s )mod N, i = 0,1,2,3, …;
Chiziqli kongruent generatorning kirish parametri s=0 bo‘lsa, ya‘ni
xi+1=(axi)mod N, i = 0,1,2,3, …; bo‘lsa, bu generator chiziqli multiplikativ
generator deyiladi.
1-isbot. Ushbu xi+1=(axi +s )mod N, i = 0,1,2,3, …; rekurent formula
bilan aniqlangan psevdotasodifiy ketma-ketlik maksimal N davrga ega bo‘lishi uchun quyidagi:
s va N -o‘zaro tub sonlar, ya‘ni EKUB(s,N)=1;
r soni N sonining bo‘luvchisi va a-1 soni r soniga karrali;
N soni 4 karrali bo‘lsa, a-1 soni ham 4 ga karrali; shartlarning bajarilishi zarur va yetarli [5].
Quyida esa chiziqli va multiplikativ generatorlarning maksimal davrga ega
bo‘lishi bilan bog‘liq ayrim xossalar keltirib o‘tiladi [5].
Bevosita hisoblash bilan ishonch hosil qilish mumkinki, ushbu xi+1=(axi +s )mod N, i = 0,1,2,3, …; tenglik bilan aniqlanuvchi ketma-ketlik umumiy hadi uchun :
-
|
|
|
|
at 1
|
|
x
|
at x
|
|
|
|
c mod N , t 1
|
|
|
t
|
|
0
|
|
a 1
|
|
|
|
|
|
|
formula o‘rinli.
Multiplikativ va chiziqli va kongruent generatorlarning kamchiligi shundaki, PTKK biror bigrammasini z1 ; z2 : z1 xt , z2 xt 1 , bilgan holda, uning boshqa tashkil qiluvchilarini topish imkoniyati mavjud . Haqiqatan ham, ketma-ketlikni barcha tashkil qiluvchi qiymatlari z2 = a z1+ c - k N , k=0,1,… chiziqlar oilasida yotadi.
Chiziqli kongruyent generator hisoblangan Fishman va More generatorida kiruvchi parametr z0 quyidagicha olingan [16]:
z0=23482349.
18
PTSKK esa quyidagi amal orqali hisoblanadi: zi+1=a*zimod(231-1). Bu yerda a holat funksiyasi.
|
