Vazirligi mirzo ulug„bek nomidagi

Ryukzak masalasi: bu algoritmda S hajmli ryugzak bor. Bizga
w =(w₁, w₂ ,... w_n )
n ta tosh berilgan. Bu toshlarni S ryukzakka solamiz. Bizga
x = (x₁, x₂ ,... x_n )
binar vektor ham beriladi, bu vektor elementlari 0 yoki 1 qiymatni qabul qiladi
x_i ∈[0,1] _.
Shunda ryukzak quyidagi ko‗rinishga keladi
n
S = _∑ x_i w_{i .}
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 ^{> ∑ w}i
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 > _∑w_i
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 b_i ketma-ketlik normal ketma-ketlik deyiladi.
b_i = (w_i * r) mod q – normal ketma-ketlik. Bu yerda normal ketma-ketlik (b₁, b₂ ,…b_n) ochiq kalit hisoblanadi. O‗suvchi ketma-ketlik (w₁, w₂ ,…w_n) 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.