maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2012-3-124-135mais-34Research ArticleОригинальные статьиArticlesО порядке роста числа инъективных и сверхрастущих рюкзачных векторовThe Order in the Growth of the Injective and Super-Increasing Vectors Knapsacks QuantityМуринДмитрий МихайловичMurinD. M.

аспирант, nirum87@mail.ru

аспирант, nirum87@mail.ru

d.murin@secst.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияЯрославский государственный университет им. П.Г. ДемидоваRussian Federation201227022015193124135Copyright © Мурин Д.М., 20152015Мурин Д.М.Murin D.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/34

В 1978 году Р. Меркль и М. Хеллман предложили использовать для построения криптосистем одномерную аддитивную задачу об укладке рюкзака. В основе предложенной криптосистемы лежал класс рюкзаков, обладающих сверхрастущими векторами. Указанный класс является подмножеством множества рюкзаков с инъективными (криптографическими) векторами, допускающих однозначное декодирование (дешифрование). В настоящей работе рассмотрены вопросы о порядке роста числа рюкзаков с инъективными векторами и о порядке роста числа рюкзаков со сверхрастущими векторами при росте максимального элемента рюкзака.

In 1978 R. Mercle and M. Hellman offered to use the subset sum problem for constructing cryptographic systems. The proposed cryptosystems were based on a class of the knapsacks with super-increasing vectors. This class is a subset of the set of knapsacks with injective (cryptographic) vectors that allow the single-valued decoding (decryption) result. In this paper we consider the problems related to the order in the growth of the injective vectors knapsacks quantity and to the order in the growth of knapsacks quantity with the super-increasing vectors through the knapsack maximal element increasing.

инъективные рюкзачные векторысверхрастущие рюкзачные векторыкомпьютерная алгебраinjective vectorssuper-increasing vectorscomputer algebraReferencesMerkle R.C., Hellman M.E. Hiding information and signatures in trap-door knapsacks // IEEE Trans. Inform. Theory. 1978. V. IT-24. P. 525–530.Merkle R.C., Hellman M.E. Hiding information and signatures in trap-door knapsacks // IEEE Trans. Inform. Theory. 1978. V. IT-24. P. 525–530.Саломаа А. Криптография с открытым ключом. М.: Мир, 1995.Саломаа А. Криптография с открытым ключом. М.: Мир, 1995.

The authors declare that there are no conflicts of interest present.