|
Vazirligi mirzo ulug„bek nomidagi
|
səhifə | 26/45 | tarix | 11.12.2023 | ölçüsü | 163,86 Kb. | | #146286 |
| Vazirligi mirzo ulug„bek nomidagiRyukzak masalasi: bu algoritmda S hajmli ryugzak bor. Bizga
w =(w1, w2 ,... wn )
n ta tosh berilgan. Bu toshlarni S ryukzakka solamiz. Bizga
x = (x1, x2 ,... xn )
binar vektor ham beriladi, bu vektor elementlari 0 yoki 1 qiymatni qabul qiladi
xi ∈[0,1] .
Shunda ryukzak quyidagi ko‗rinishga keladi
n
S = ∑ xi wi .
i =1
k
Ta‟rif: Berilgan ketma-ketlikni har bir hadi o‗zidan oldingi hadlar yig‗indisidan katta bo‗lsa, bu ketma-ketlikka o„suvchi ketma-ketlik deyiladi.
wk +1 > ∑ wi
i=1
n
q modul son tanlanadi. Modul son sifatida o‗suvchi ketma-ketlik hadlari yig‗indisidan katta bo‗lgan ixtiyoriy natural son tanlanadi:
q > ∑wi
i=1
q modul bilan o‗zaro tub bo‗lgan ixtiyoriy r natural sonni o‗suvchi ketma- ketlikning har bir hadiga ko‗paytirib, q bo‗yicha modul olinib, hosil qilingan bi ketma-ketlik normal ketma-ketlik deyiladi.
bi = (wi * r) mod q – normal ketma-ketlik. Bu yerda normal ketma-ketlik (b1, b2 ,…bn) ochiq kalit hisoblanadi. O‗suvchi ketma-ketlik (w1, w2 ,…wn) va modul q va r sonlari yopiq kalit hisoblanadi. Xavfsizlik nuqtai nazaridan ketma-ketlik hadlari uzunligi uchun 200 bitdan 400 bitgacha bo‗lgan sonlar olinishi tavsiya etiladi.
Dostları ilə paylaş: |
|
|