Рюкзак системалари

Таъриф-4. A={a₁, a₂, …, a_n} рюкзак вектори ўсувчан (тез ўсувчан) деб аталади, агар ихтиёрий j=2, 3, …, n лар учун a_ja_j-1 (мос равишда ) шартлар ўринли бўлса.
Кўриниб турибдики, тез ўсувчан векторлар ўсувчан ҳам бўла олади. А вектор учун max A=max(a_j  1 ≤ j ≤ n) дейлик. x номанфий сон бўлсин. [х] орқали энг катта ≤ х бутун сонни белгилайлик.
Бутун x ва m>2 сонлар учун x ни m бўлганда энг кичик номанфий қолдиқни (х mod m) орқали белгилаймиз. Кўриш мумкинки,
(х, mod m) = х — [х/т]  т .
Ушбу муносабатни х=(х, mod m) + [x/m]  т тарзида ҳам ёзиш мумкин.
Энди модул бўйича кўпайтиришнинг икки вариантини аниқлаймиз. А рюкзак вектори ва m>max А бутун сони ва шундай натурал t<m сонини оламизки, t ва m лар ўзаро туб, яъни энг катта умумий бўлувчи (t, m)=1 га тенг. Агар, шундай В = (b₁, b₂, ..., b_n) вектор компонентлари барча i=1, 2, …, n лар учун
b_i = (ta_i, mod m), для i = 1,..., п ,
формула билан ҳосил қилинган бўлса, у холда В вектор А вектордан m модулга ва t кўпайтувчига нисбатан модул бўйича кўпайтириш орқали ҳосил қилинган деб аталади.
(t, m)=1 шарт шундай тескари t^-1 =u соннинг мавжудлигини кафолатлайдики, шарт ўринли бўлади. Бу холат В дан t ва u ларга нисбатан модул бўйича кўпайтириш орқали А ни ҳосил қилиш мумкинлигини англатади (t>max B, чунки b_i ларнинг ҳаммаси mod m бўйича олинади).
Агар юқоридаги t>max А шарт ўзига нисбатан кучлироқ бўлган шарт билан алмаштирилса, у холда В вектор А дан m ва t га нисбатан кучли модул бўйича кўпайтириш орқали ҳосил қилинган дейилади. Бу ерда муносабатнинг ўринли бўлиши шарт эмас ва А вектор В дан t ва u ларга нисбатан модул бўйича кўпайтириш орқали ҳосил қилинади.
Криптосистема ишлаб чиқувчи A, t, m ва В ларни шундай танлайдики, А вектор тез ўсувчан, В вектор эса А дан m ва t га нисбатан кучли модул бўйича кўпайтириш орқали ҳосил қилинади. В вектор шифрлаш калити сифатида қабул қилинади ва B вектордан ҳосил қилинган  сонлар узунлиги n га тенг бўлган иккилик саноқ системасидаги блоклар сифатида кқабул қилувчига узатилади. Бу маълумотни тутиб қолувчи шахс (B, ) бошланғич маълумотлар учун рюкзак ҳақидаги масалани чеишига тўғри келади. Криптосистемани ишлаб чиқувчи эса =(u, mod m) ни ҳисоблаб, рюкзак масаласини (А, ) бошланғич маълумотлар учун ечади. Буни қуйидаги лемма ёрдамида кўрсатиш мумкин. .