Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами

Для криптосхемы Меркля—Хеллмана шифрования ранцами разработан алгоритм формирования обычной последовательности из сверхвозрастающей, основанный на введенных понятиях непрямых модульных преобразований и частичных инверсий, в котором для формирования «лазейки» применяются удвоенные последовательности...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автор:	Винничук, С.Д.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2013
Назва видання:	Электронное моделирование
Теми:	Математические методы и модели
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/100843
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами / С.Д. Винничук // Электронное моделирование. — 2013. — Т. 35, № 3. — С. 3-22 . — Бібліогр.: 2 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-100843
record_format	dspace
spelling	irk-123456789-1008432016-05-28T03:02:08Z Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами Винничук, С.Д. Математические методы и модели Для криптосхемы Меркля—Хеллмана шифрования ранцами разработан алгоритм формирования обычной последовательности из сверхвозрастающей, основанный на введенных понятиях непрямых модульных преобразований и частичных инверсий, в котором для формирования «лазейки» применяются удвоенные последовательности весов предметов. Показано, что при таком подходе для k-кратно итерируемой ранцевой системы каждому элементу сверхвозрастающей последовательности может соответствовать 2^k вариантов элемента обычной последовательности, а число вариантов обычной последовательности, при всех одинаковых параметрах модульных преобразований, может достигать 2^kL, где L — число бит в блоке информации. При этом обратная задача определения сверхвозрастающей последовательности по обычной может быть сведена к задаче целочисленного линейного программирования как вариантная при большом числе вариантов. Для криптосхеми Меркля—Хеллмана шифрування рюкзаками розроблено алгоритм формування звичайної послідовності із надзростаючої, що грунтується на введених поняттях непрямих модульних перетворень і часткових інверсій, в якому при формуванні «люка» використовуються подвоєні послідовності ваг предметів. Показано, що при такому підході для k-кратно ітерованої системи кожному з елементів надзростаючої послідовності може відповідати 2^k варіантів елемента звичайної послідовності, а число варіантів звичайної послідовності при всіх однакових параметрах модульних перетворень, може досягати 2^kL,де L —число біт в блоці інформації. При цьому обернена задача визначення надзростаючої послідовності по звичайній може бути зведена до задачі цілочисельного лінійного програмування як варіантна при значному числі варіантів. The algorithm for forming the normal sequence of eccessively ascending one, based on the introduced concepts of indirect modular transformations and partial inversions with the «loophole» formation on the basis of duplicate sequences of the items weights has been developed as part of the Merkle-Hellman cryptoscheme of knapsack encryption . It is shown that under such an approach 2^k options of the element of normal sequence may correspond to each element above the ascending sequence for the k-fold iterated backpack system, and the number of options of normal sequence, with all the same parameters of the modular transformations, may achieve 2^kL, where L is the number of bits in the data block. In this case, the inverse problem of determining the excessively ascending sequence of the normal one can be reduced to the problem of integer linear programming only as a variant with the great number of options. 2013 Article Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами / С.Д. Винничук // Электронное моделирование. — 2013. — Т. 35, № 3. — С. 3-22 . — Бібліогр.: 2 назв. — рос. 0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/100843 621.391.7 + 681.3.067 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Математические методы и модели Математические методы и модели
spellingShingle	Математические методы и модели Математические методы и модели Винничук, С.Д. Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами Электронное моделирование
description	Для криптосхемы Меркля—Хеллмана шифрования ранцами разработан алгоритм формирования обычной последовательности из сверхвозрастающей, основанный на введенных понятиях непрямых модульных преобразований и частичных инверсий, в котором для формирования «лазейки» применяются удвоенные последовательности весов предметов. Показано, что при таком подходе для k-кратно итерируемой ранцевой системы каждому элементу сверхвозрастающей последовательности может соответствовать 2^k вариантов элемента обычной последовательности, а число вариантов обычной последовательности, при всех одинаковых параметрах модульных преобразований, может достигать 2^kL, где L — число бит в блоке информации. При этом обратная задача определения сверхвозрастающей последовательности по обычной может быть сведена к задаче целочисленного линейного программирования как вариантная при большом числе вариантов.
format	Article
author	Винничук, С.Д.
author_facet	Винничук, С.Д.
author_sort	Винничук, С.Д.
title	Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами
title_short	Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами
title_full	Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами
title_fullStr	Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами
title_full_unstemmed	Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами
title_sort	метод удвоения последовательности весов предметов в задаче меркля—хеллмана шифрования ранцами
publisher	Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
publishDate	2013
topic_facet	Математические методы и модели
url	http://dspace.nbuv.gov.ua/handle/123456789/100843
citation_txt	Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами / С.Д. Винничук // Электронное моделирование. — 2013. — Т. 35, № 3. — С. 3-22 . — Бібліогр.: 2 назв. — рос.
series	Электронное моделирование
work_keys_str_mv	AT vinničuksd metodudvoeniâposledovatelʹnostivesovpredmetovvzadačemerklâhellmanašifrovaniârancami
first_indexed	2025-07-07T09:24:45Z
last_indexed	2025-07-07T09:24:45Z
_version_	1836979622828310528
fulltext	ÓÄÊ 621.391.7 + 681.3.067 Ñ.Ä. Âèííè÷óê, ä-ð òåõí. íàóê Èí-ò ïðîáëåì ìîäåëèðîâàíèÿ â ýíåðãåòèêå èì. Ã.Å. Ïóõîâà ÍÀÍ Óêðàèíû (Óêðàèíà, 03164, Êèåâ, óë. Ãåíåðàëà Íàóìîâà, 15, òåë. (044) 4249171, e-mail: vynnychuk@i.ua) Ìåòîä óäâîåíèÿ ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ â çàäà÷å Ìåðêëÿ—Õåëëìàíà øèôðîâàíèÿ ðàíöàìè Äëÿ êðèïòîñõåìû Ìåðêëÿ—Õåëëìàíà øèôðîâàíèÿ ðàíöàìè ðàçðàáîòàí àëãîðèòì ôîð- ìèðîâàíèÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè èç ñâåðõâîçðàñòàþùåé, îñíîâàííûé íà ââåäåí- íûõ ïîíÿòèÿõ íåïðÿìûõ ìîäóëüíûõ ïðåîáðàçîâàíèé è ÷àñòè÷íûõ èíâåðñèé, â êîòîðîì äëÿ ôîðìèðîâàíèÿ «ëàçåéêè» ïðèìåíÿþòñÿ óäâîåííûå ïîñëåäîâàòåëüíîñòè âåñîâ ïðåä- ìåòîâ. Ïîêàçàíî, ÷òî ïðè òàêîì ïîäõîäå äëÿ k-êðàòíî èòåðèðóåìîé ðàíöåâîé ñèñòåìû êàæäîìó ýëåìåíòó ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè ìîæåò ñîîòâåòñòâîâàòü 2k âàðèàíòîâ ýëåìåíòà îáû÷íîé ïîñëåäîâàòåëüíîñòè, à ÷èñëî âàðèàíòîâ îáû÷íîé ïîñëåäî- âàòåëüíîñòè, ïðè âñåõ îäèíàêîâûõ ïàðàìåòðàõ ìîäóëüíûõ ïðåîáðàçîâàíèé, ìîæåò äîñòè- ãàòü 2kL, ãäå L — ÷èñëî áèò â áëîêå èíôîðìàöèè. Ïðè ýòîì îáðàòíàÿ çàäà÷à îïðåäåëåíèÿ ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè ïî îáû÷íîé ìîæåò áûòü ñâåäåíà ê çàäà÷å öåëî÷èñ- ëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ êàê âàðèàíòíàÿ ïðè áîëüøîì ÷èñëå âàðèàíòîâ. Äëÿ êðèïòîñõåìè Ìåðêëÿ—Õåëëìàíà øèôðóâàííÿ ðþêçàêàìè ðîçðîáëåíî àëãîðèòì ôîðìó- âàííÿ çâè÷àéíî¿ ïîñë³äîâíîñò³ ³ç íàäçðîñòàþ÷î¿, ùî ãðóíòóºòüñÿ íà ââåäåíèõ ïîíÿòòÿõ íåïðÿ- ìèõ ìîäóëüíèõ ïåðåòâîðåíü ³ ÷àñòêîâèõ ³íâåðñ³é, â ÿêîìó ïðè ôîðìóâàíí³ «ëþêà» âèêîðèñòî- âóþòüñÿ ïîäâîºí³ ïîñë³äîâíîñò³ âàã ïðåäìåò³â. Ïîêàçàíî, ùî ïðè òàêîìó ï³äõîä³ äëÿ k-êðàòíî ³òåðîâàíî¿ ñèñòåìè êîæíîìó ç åëåìåíò³â íàäçðîñòàþ÷î¿ ïîñë³äîâíîñò³ ìîæå â³äïîâ³äàòè 2k âàð³àíò³â åëåìåíòà çâè÷àéíî¿ ïîñë³äîâíîñò³, à ÷èñëî âàð³àíò³â çâè÷àéíî¿ ïîñë³äîâíîñò³ ïðè âñ³õ îäíàêîâèõ ïàðàìåòðàõ ìîäóëüíèõ ïåðåòâîðåíü, ìîæå äîñÿãàòè 2kL, äå L — ÷èñëî á³ò â áëîö³ ³íôîðìàö³¿. Ïðè öüîìó îáåðíåíà çàäà÷à âèçíà÷åííÿ íàäçðîñòàþ÷î¿ ïîñë³äîâíîñò³ ïî çâè÷àéí³é ìîæå áóòè çâåäåíà äî çàäà÷³ ö³ëî÷èñåëüíîãî ë³í³éíîãî ïðîãðàìóâàííÿ ÿê âàð³àíòíà ïðè çíà÷íîìó ÷èñë³ âàð³àíò³â. Ê ë þ ÷ å â û å ñ ë î â à: êðèïòîãðàôèÿ ñ îòêðûòûì êëþ÷îì, êðèïòîñõåìà Ìåðêëÿ—Õåëëìàíà, øèôðîâàíèå ðàíöàìè. Ïîñòàíîâêà çàäà÷è. Ïåðâûì èçâåñòíûì ñïîñîáîì àñèììåòðè÷åñêîãî øèô- ðîâàíèÿ ñ îòêðûòûì êëþ÷îì áûë ñïîñîá øèôðîâàíèÿ ðàíöàìè [1, 2]. Ïðè òàêîì ñïîñîáå øèôðîâàííàÿ èíôîðìàöèÿ ðàçáèâàëàñü íà áëîêè ðàâíîé äëèíû, ãäå êàæäîìó áèòó èíôîðìàöèè, ðàâíîìó åäèíèöå, ñòàâèëñÿ â ñîîò- ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 3 МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ � Ñ.Ä. Âèííè÷óê, 2013 âåòñòâèå îïðåäåëåííûé âåñ ïðåäìåòà. Øèôðîâàííîå ñîîáùåíèå äëÿ áëîêà èíôîðìàöèè ôèêñèðîâàííîé äëèíû ÿâëÿëîñü ñóììîé âåñîâ ïðåäìåòîâ, êîòîðûì â áëîêå ñîîòâåòñòâóþò áèòû, ðàâíûå åäèíèöå. Â îáùåì âèäå çàäà÷à îïðåäåëåíèÿ âåñà ïðåäìåòîâ ïî èõ èçâåñòíîìó ñóììàðíîìó âåñó ñ÷èòàåòñÿ ÷ðåçâû÷àéíî ñëîæíîé è îòíîñèòñÿ ê êëàññó NP-ïîëíûõ. Ïðè ýòîì äëÿ âîçìîæíîñòè ðàñøèôðîâàíèÿ èíôîðìàöèè òðå- áóåòñÿ ñïåöèàëüíûé ñïîñîá ïîñòðîåíèÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè. Òàêîé ñïîñîá áûë ïðåäëîæåí Ð. Ìåðêëåì [2] êàê îäíîñòîðîííÿÿ ôóíêöèÿ ñ «ëà- çåéêîé», â êîòîðîé ñâåðõâîçðàñòàþùàÿ ïîñëåäîâàòåëüíîñòü âåñîâ { }v i i L �1 òàêàÿ, ÷òî ñóììà âåñîâ ïåðâûõ k ïðåäìåòîâ ìåíüøå âåñà k + 1-ãî ïðåäìåòà (1� �k L) ïðåîáðàçóåòñÿ ê îáû÷íîé{ }wi i L �1 â ðåçóëüòàòå ìîäóëüíîãî ïðåîá- ðàçîâàíèÿ (îïðåäåëåíèÿ îñòàòêà îò äåëåíèÿ) w v n mi i� ( ) (mod ), i L� �1 , (1) ãäå n è m — êîíñòàíòû ìîäóëüíîãî ïðåîáðàçîâàíèÿ; L — äëèíà èíôîðìà- öèîííîãî áëîêà (÷èñëî äâîè÷íûõ ñèìâîëîâ). Òîãäà äëÿ ïðîèçâîëüíîãî ñëîâà A a a aL� ( , ,..., )1 2 ìîæíî îïðåäåëèòü ñóììàðíûé âåñ ïî ïðàâèëó W A a wi i i L ( ) � � � 1 . (2) Îïðåäåëåíèå ñëîâà A ïî ñóììå W (A) âîçìîæíî íà îñíîâàíèè îáðàòíîãî ìîäóëüíîãî ïðåîáðàçîâàíèÿ (ÎÌÏ) v w n m w d mi i i� ��( )(mod ) ( )(mod )1 , i L� �1 , (3) è îïðåäåëåíèÿ âåñà V A( ) ïî ýëåìåíòàì ñâåðõâîçðàñòàþùåé ïîñëåäîâà- òåëüíîñòè: V A W A d m a w d m a vi i i i L i i i L ( ) ( ( ) )(mod ) ( )(mod )� � � � � � � 1 1 . (4) Áåññïîðíîå ïðåèìóùåñòâî òàêîãî ñïîñîáà øèôðîâàíèÿ — åãî ïðîñ- òîòà è ñêîðîñòü. Ñîîòíîøåíèÿ (1)—(4) — ïðîñòåéøèé âàðèàíò çàøèôðî- âàíèÿ è ðàñøèôðîâàíèÿ äëÿ êðèïòîñõåìû Ìåðêëÿ—Õåëëìàíà. Ïðè òàêîì ïîäõîäå èñïîëüçóåòñÿ åäèíîîáðàçíîå ìîäóëüíîå ïðåîáðàçîâàíèå ñâåðõ- âîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè âåñîâ â îáû÷íóþ, è äëÿ ðàñêðûòèÿ êîäà äîñòàòî÷íî îïðåäåëèòü ÷èñëà d è m. Çàäà÷à îïðåäåëåíèÿ d è m ìîæåò áûòü ñâåäåíà ê çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ [2], äëÿ êîòîðîé õà- ðàêòåðíà ïîëèíîìèàëüíàÿ ñëîæíîñòü, òîãäà êàê ñïîñîá ðàñêðûòèÿ ãðóáîé ñèëîé èìååò ýêñïîíåíöèàëüíóþ ñëîæíîñòü. Ñ.Ä. Âèííè÷óê 4 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 Ïîñëå ðàñêðûòèÿ ïðîñòåéøåé êðèïòîñõåìû (1)—(4) áûëî ïðåäëîæåíî ìíîæåñòâî äðóãèõ åå âàðèàíòîâ, êîòîðûå òàêæå áûëè ðàñêðûòû. Â íàñòîÿ- ùåå âðåìÿ òàêîé ñïîñîá øèôðîâàíèÿ, íåñìîòðÿ íà åãî ïðîñòîòó è ñêî- ðîñòü, ïðàêòè÷åñêè íå èñïîëüçóåòñÿ. Áîëåå òîãî, â ñòàòüå Ó. Äèôôè, îïóá- ëèêîâàííîé â [2], ðå÷ü èäåò î «êðàõå ðàíöåâîé ñèñòåìû», è, ïî ìíåíèþ àâòîðà, «íèêòî íå äîëæåí âîçëàãàòü áîëüøèõ íàäåæä íà ðàíöåâóþ ñèñòå- ìó, åñëè ïîä åå ôóíêöèîíèðîâàíèå íå ïîäâåäåíà íàìíîãî áîëåå ãëóáîêàÿ òåîðèÿ, ÷åì òà, êîòîðàÿ èìååòñÿ â íàñòîÿùåå âðåìÿ». Âåðîÿòíî, òàêàÿ òåîðèÿ äîëæíà ïðåïÿòñòâîâàòü ôîðìèðîâàíèþ çàäà÷è ëèíåéíîãî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ. Èìåííî òàêîé ïîäõîä ðåà- ëèçîâàí â ïðåäëàãàåìûõ ñïîñîáàõ ïîëó÷åíèÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè âåñîâ èç ñâåðõâîçðàñòàþùåé ñ èñïîëüçîâàíèåì íåïðÿìûõ ìîäóëüíûõ ïðå- îáðàçîâàíèé (ÍÌÏ), à òàêæå ÷àñòè÷íûõ èíâåðñèé (×È), ïðè êîòîðûõ «ëà- çåéêà» ôîðìèðóåòñÿ íà îñíîâàíèè óäâîåííûõ ïîñëåäîâàòåëüíîñòåé (ÓÏ) âåñîâ ïðåäìåòîâ. Óäâîåííûå ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ è èõ ñâîéñòâà. Îïðåäåëåíèå 1. Óäâîåííàÿ ïîñëåäîâàòåëüíîñòü âåñîâ ïðåäìåòîâ — ýòî ïîñëåäîâàòåëüíîñòü, â êîòîðîé âåñ ïðèñâàèâàåòñÿ êàê áèòó 1, òàê è áèòó 0. Â ñëó÷àå ÓÏ ïðàâèëî îïðåäåëåíèÿ âåñà ðàíöà ïðè çàøèôðîâàíèè áëîêà èíôîðìàöèè äëèíîé L áèò ñîñòîèò â ñëåäóþùåì: êàæäîìó i-ìó èíôîðìàöèîííîìó áèòó ñòàâèòñÿ â ñîîòâåòñòâèå ÷èñëî (âåñ wi , i L� �1 ), êàê äëÿ áèòà èíôîðìàöèè, ðàâíîãî åäèíèöå (wi1), òàê è äëÿ áèòà, ðàâíîãî íóëþ (wi 0). Òîãäà ñóììàðíûé âåñ ïðåäìåòîâ, ñîîòâåòñòâóþùèõ ñëîâó À, áóäåò îïðåäåëÿòüñÿ ïî ôîðìóëå, áîëåå ñëîæíîé, ÷åì (2): W A w w a w a wi a i a i i i L i i i L i i ( ) ( )� � � � � � � � � � �0 0 1 1 1 1 0 1 1 . (5) Â îáùåì âèäå äàííûå, èñïîëüçóåìûå â ÓÏ, ïðåäñòàâëåíû â òàáë. 1. Î÷åâèäíî, ÷òî ÓÏ òðåáóþò óâåëè÷åíèÿ â äâà ðàçà îáúåìà äàííûõ ïðè çàøèôðîâàíèè è ðàñøèôðîâàíèè èíôîðìàöèè, ÷òî íå ÿâëÿåòñÿ ïîëîæè- òåëüíûì ôàêòîì. Îäíàêî îíè ïîçâîëÿþò ïðîâîäèòü ðÿä äîïîëíèòåëüíûõ îïåðàöèé íàä äàííûìè, ÷òî â áîëüøèíñòâå ñëó÷àåâ íåâîçìîæíî äëÿ òðàäè- öèîííûõ ðàíöåâûõ ñèñòåì. Ïîêàæåì ýòî íà ïðèìåðàõ. Ïóñòü çàäàíà íåêîòîðàÿ ñâåðõâîçðàñòàþùàÿ ïîñëåäîâàòåëüíîñòü { }v i i L �1. Ïðîñòåéøèé âàðèàíò åå ïðåäñòàâëåíèÿ â âèäå ÓÏ ñëåäóþùèé: âñåì áèòàì ñî çíà÷åíèåì 0 ñîîòâåòñòâóåò çíà÷åíèå 0, à áèòàì ñî çíà÷åíèåì 1 — çíà÷å- íèå ñîîòâåòñòâóþùåãî ýëåìåíòà ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè. Îáîçíà÷èì òàêóþ ïîñëåäîâàòåëüíîñòü Ï20. Ìåòîä óäâîåíèÿ ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ â çàäà÷å Ìåðêëÿ—Õåëëìàíà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 5 Óäâîåííûé îáúåì äàííûõ â ÓÏ ïî ñðàâíåíèþ ñî ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòüþ ïîçâîëÿåò ðåàëèçîâàòü ðÿä ïðåîáðàçîâàíèé. Îïè- øåì èõ è ïîêàæåì íà ïðèìåðå ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè {4, 5, 10, 20}, ïîñëåäîâàòåëüíîñòü Ï20 êîòîðîé ïðåäñòàâëåíà â òàáë. 1. Ïðåîáðàçîâàíèå Ï1. ×àñòè÷íàÿ èíâåðñèÿ. Âî âñåõ ñëó÷àÿõ, êîãäà äëÿ ïîñëåäîâàòåëüíîñòè Ï20 íåíóëåâîé ýëåìåíò ñîîòâåòñòâóåò áèòó 0, áóäåì ñ÷èòàòü, ÷òî äëÿ ñîîòâåòñòâóþùåãî áèòà èíôîðìàöèè âûïîëíÿåòñÿ èíâåðñèÿ. Îòíîñèòåëüíî âñåé ÓÏ ìîæåò îñóùåñòâëÿòüñÿ êàê ïîëíàÿ èí- âåðñèÿ (ÏÈ) (êàæäûé èç íåíóëåâûõ ýëåìåíòîâ ÓÏ ñîîòâåòñòâóåò áèòó 0), òàê è ×È, êîãäà èñïîëüçîâàíà èíâåðñèÿ òîëüêî äëÿ ÷àñòè ýëåìåíòîâ. Îá- ùåå ÷èñëî âàðèàíòîâ ×È ðàâíÿåòñÿ 2L. Òàêóþ ñôîðìèðîâàííóþ ïîñëåäî- âàòåëüíîñòü âåñîâ îáîçíà÷èì Ï21. Ïðèìåð ×È äëÿ ïîñëåäîâàòåëüíîñòè Ï20 ïðèâåäåí â òàáë. 1. Ïðåîáðàçîâàíèå Ï2. Ïåðåñòàíîâêà óðîâíåé. Ñòîëáöû ÓÏ ïðîèç- âîëüíî ìåíÿþòñÿ ìåñòàìè. Òàêîé ñïîñîá ïåðåñòàíîâêè èñïîëüçîâàëñÿ è ðàíåå äëÿ ýëåìåíòîâ ñâåðõâîçðàñòàþùèõ è îáû÷íûõ ïîñëåäîâàòåëüíîñ- òåé. Ñôîðìèðîâàííóþ ïîñëåäîâàòåëüíîñòü âåñîâ îáîçíà÷èì Ï22. Âàðèàíò ïåðåñòàíîâîê äëÿ ïîñëåäîâàòåëüíîñòè Ï21 ïðèâåäåí â òàáë. 1. Ïðåîáðàçîâàíèå Ï3. Ñèíõðîííîå óâåëè÷åíèå âåñà. Ê ýëåìåíòàì ïðî- èçâîëüíîãî ñòîëáöà ÓÏ îäíîâðåìåííî ïðèáàâëÿåì îäíî è òî æå ÷èñëî, ò.å. ñèíõðîííî íà îäíî è òî æå ÷èñëî óâåëè÷èâàåì âåñ îäíîãî áèòà. Â ðåçóëüòàòå ïðåîáðàçîâàíèÿ Ï3 ïðè çàøèôðîâàíèè âåñ ðàíöà è â äàëüíåéøåì áóäåò óíèêàëüíûì, òàê êàê äëÿ ïðîèçâîëüíîãî èíôîðìàöèîí- íîãî ñëîâà ñîîòâåòñòâóþùàÿ åìó ñóììà âñåãäà áóäåò ñèíõðîííî óâåëè÷è- âàòüñÿ íà îäíî è òî æå ÷èñëî, êîòîðîå îáîçíà÷èì S1. Ïîëó÷åííóþ íîâóþ ïîñëåäîâàòåëüíîñòü îáîçíà÷èì Ï23. Òàêîå ïðåîáðàçîâàíèå ìîæíî ïðèìå- íÿòü ê ïðîèçâîëüíîìó ÷èñëó ñòîëáöîâ ÓÏ. Íàïðèìåð, åñëè äëÿ ÓÏ Ï21 âåñ ñòîëáöîâ ñèíõðîííî óâåëè÷èòü ñîîòâåòñòâåííî íà âåëè÷èíó 8, 10, 3, 4 (S1 = = 8 + 10 + 3 + 4 = 25), òî ïîëó÷èì íîâóþ ÓÏ Ï23 (ñì. òàáë. 1). Â ðåçóëüòàòå âûïîëíåííûõ ïðåîáðàçîâàíèé íà÷àëüíàÿ ñâåðõâîçðàñ- òàþùàÿ ïîñëåäîâàòåëüíîñòü Ï20 ïåðåñòàëà áûòü ñâåðõâîçðàñòàþùåé åùå äî åå ïðåîáðàçîâàíèÿ íà îñíîâå ìîäóëüíîé àðèôìåòèêè. Ïðåîáðàçóåì ïîñëåäîâàòåëüíîñòü Ï23 íà îñíîâå ìîäóëüíîé àðèô- ìåòèêè. Ïðåîáðàçîâàíèå Ï4. Ïðÿìûå ìîäóëüíûå ïðåîáðàçîâàíèÿ (ÏÌÏ) ÓÏ ðåàëèçóþòñÿ ñ ïîìîùüþ çàâèñèìîñòè (1), äëÿ êîòîðîé ñëåäóåò âûáðàòü âçàèìíî ïðîñòûå ÷èñëà m è n. Óäâîåííóþ ïîñëåäîâàòåëüíîñòü, ïîëó÷åííóþ ïîñëå ÏÌÏ (1), îáîçíà- ÷èì Ï24. Çàìåòèì, ÷òî ïðè âûáîðå ÷èñëà m ñëåäóåò èñõîäèòü èç òîãî, ÷òî âåñ ÷èñëà m áîëüøå ëþáîãî èç âåñîâ ñîîòâåòñòâóþùèõ èíôîðìàöèîííûõ Ñ.Ä. Âèííè÷óê 6 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 Ìåòîä óäâîåíèÿ ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ â çàäà÷å Ìåðêëÿ—Õåëëìàíà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 7 Íîìåð áèòà wi0 äëÿ áèòà 0 wi1 äëÿ áèòà 1 Îáùèé âèä äàííûõ 1 w10 w11 2 w20 w21 � � � l wl 0 wl1 Îáùèé âèä ïîñëåäîâàòåëüíîñòè Ï20 ïðè w vi i1 � 1 0 v1 2 0 v2 � � � l 0 vl Ïðèìåð ïîñëåäîâàòåëüíîñòè Ï20 1 0 4 2 0 5 3 0 10 4 0 20 Âàðèàíò ðàçìåùåíèÿ ýëåìåíòîâ ïîñëåäîâàòåëüíîñòè Ï21 1 4 0 2 0 5 3 0 10 4 20 0 Ïîñëåäîâàòåëüíîñòü Ï22 ïîñëå ïåðåñòàíîâîê â ïîñëåäîâàòåëüíîñòè Ï21 1 0 10 2 0 5 3 20 0 4 4 0 Ïîñëåäîâàòåëüíîñòü Ï23 1 12 8 2 10 15 3 3 13 4 24 4 Ïîñëåäîâàòåëüíîñòü Ï24 ïîñëå ïðåîáðàçîâàíèÿ Ï23 ñîãëàñíî (1) 1 42 28 2 35 19 3 44 12 4 17 14 Òàáëèöà 1. Âàðèàíòû ÓÏ ñëîâ, ò.å. ÷èñëî m ïðåâûñèò ñóììó âñåõ áîëüøèõ çíà÷åíèé â ñòðîêàõ. Ïîýòîìó äëÿ ïîñëåäîâàòåëüíîñòè Ï23 (ñì. òàáë. 1) ÷èñëî m âûáåðåì èç óñëîâèÿ m > 12 + 15 + 13 +24, ò.å. m > 64, íàïðèìåð m = 67, è âçàèìíî ïðîñ- òîå ñ íèì ÷èñëî n = 37. Â ðåçóëüòàòå ïðåîáðàçîâàíèé ïîëó÷èì ÓÏ Ï24 (ñì. òàáë.1). Ïðåîáðàçîâàíèå Ï5. Ñèíõðîííîå èçìåíåíèå âåñà ïîñëå ÏÌÏ. Îò ýëåìåíòîâ ïðîèçâîëüíîãî ñòîëáöà ÓÏ ìîæíî îäíîâðåìåííî âû÷åñòü îäíî è òî æå ÷èñëî, ò.å. ñèíõðîííî íà îäíî è òî æå ÷èñëî èçìåíèòü âåñ áèòà ïðè åãî çíà÷åíèÿõ 0 è 1. Òàêóþ ÓÏ îáîçíà÷èì Ï25, à îáùóþ âåëè÷èíó ñóììàðíîãî ñèíõðîííî- ãî èçìåíåíèÿ âåñîâ — S2. Ïóñòü äëÿ Ï24 (ñì. òàáë. 1) ïðåîáðàçîâàíèå Ï5 ðåàëèçóåòñÿ ïîñðåäñòâîì âû÷èòàíèÿ èç áèòîâ 1—4 ñîîòâåòñòâåííî ÷èñåë 17, 15, 6 è 12. Äëÿ ïðèâåäåííîãî ïðèìåðà S2 = 17 + 15 + 6 + 12 = 50. Ïîëó- ÷åííàÿ ÓÏ Ï25 ïðåäñòàâëåíà â òàáë. 1. Ñóììàðíûé âåñ êîäîâîãî ñëîâà äëÿ ïðîèçâîëüíîãî èíôîðìàöèîííîãî áëîêà óìåíüøåí íà âåëè÷èíó S2 = 50, ÷òî ñëåäóåò ó÷èòûâàòü ïðè ðàñøèô- ðîâàíèè èíôîðìàöèè. Ñëåäóåò çàìåòèòü, ÷òî ïðåîáðàçîâàíÿ Ï1, Ï3 è Ï5 ìîæíî ðåàëèçîâàòü òîëüêî ïðè èñïîëüçîâàíèè ÓÏ. Ðàññìîòðèì ïðèìåðû çàøèôðîâàíèÿ è ðàñøèôðîâàíèÿ èíôîðìàöèè ïðè èñïîëüçîâàíèè Ï25, ïðåäñòàâëåííîé â òàáë. 1, äëÿ èíôîðìàöèîííûõ áëîêîâ 1001 è 0010 . Èíôîðìàöèîííûé áëîê 1001. Çàøèôðîâàíèå èíôîðìàöèè: 1001 11 + 20 + 38 +2 = 71. Èíôîðìàöèîííûé áëîê 1001. Ðàñøèôðîâàíèå èíôîðìàöèè: Ø à ã 1. 71 + S2 = 71 + 50 = 121. Ñ.Ä. Âèííè÷óê 8 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 Íîìåð áèòà wi0 äëÿ áèòà 0 wi1 äëÿ áèòà 1 Ïîñëåäîâàòåëüíîñòü Ï25 ïîñëå èçìåíåíèÿ äàííûõ â ïîñëåäîâàòåëüíîñòè Ï24 1 25 11 2 20 4 3 38 6 4 5 2 Ñïåöèàëüíûé âàðèàíò ïîñëåäîâàòåëüíîñòè Ï25 1 14 0 2 16 0 3 32 0 4 3 0 Îêîí÷àíèå òàáëèöû Ø à ã 2. (121 � 37–1)(mod 67) = (121� 29)(mod 67) = 25. Ø à ã 3. 25 – S1 = 25 – 25 = 0. Ø à ã 4. Ðàñøèôðîâàíèå ñóììû 0 ñ èñïîëüçîâàíèåì äàííûõ ïîñëåäî- âàòåëüíîñòè Ï22 (ñì. òàáë. 1). Ïîñëåäîâàòåëüíîñòü ðàñøèôðîâàíèÿ ïðåä- ñòàâëåíà â òàáë. 2. Èíôîðìàöèîííûé áëîê 0010. Çàøèôðîâàíèå èíôîðìàöèè: 0010 25 + 20 + 6 + 5 = 56. Èíôîðìàöèîííûé áëîê 0010. Ðàñøèôðîâàíèå èíôîðìàöèè: Ø à ã 1. 56 + S2 = 56 + 50 = 106. Ø à ã 2. (106 � 37–1)(mod 67) = (106 � 29)(mod 67) = 59. Ø à ã 3. 59 – S1 = 59 – 25 = 34. Ø à ã 4. Ðàñøèôðîâàíèå ñóììû 34 (ñì. òàáë. 2) ñ èñïîëüçîâàíèåì äàííûõ ïîñëåäîâàòåëüíîñòè Ï22 èç òàáë. 1. Ìåòîä óäâîåíèÿ ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ â çàäà÷å Ìåðêëÿ—Õåëëìàíà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 9 Íîìåð áèòà Óñëîâèå îïðåäåëåíèÿ çíà÷åíèÿ áèòà Çíà÷åíèå áèòà Ðàñøèôðîâàíèå ñóììû 0 4 0 < 20 1 3 0 < 10 0 2 0 < 5 0 1 0 < 4 1 Ðàñøèôðîâàíèå ñóììû 34 4 34 > 20 (34 – 20 = 14) 0 3 14 > 10 (14 – 10 = 4) 1 2 4 < 5 0 1 4 = 4 (4 – 4 = 0) 0 Ðàñøèôðîâàíèå ñóììû 39 4 39 > 20 (39 – 20 = 19) 0 3 19 > 10 (19 – 10 = 9) 1 2 9 > 5 (9 – 5 = 4) 1 1 4 = 4 (4 – 4 = 0) 0 Ðàñøèôðîâàíèå ñóììû 5 4 5 < 20 1 3 5 < 10 0 2 5 = 5 (5 � 5) = 0 1 1 0 < 4 1 Òàáëèöà 2. Ïîñëåäîâàòåëüíîñòè ðàñøèôðîâàíèÿ Òåïåðü ðàññìîòðèì ñïåöèàëüíûé âàðèàíò ÓÏ — Ï25, â êîòîðîì îêà- æóòñÿ ðàâíûìè íóëþ ëèáî �wi 0, ëèáî �wi1, i l� �1 (ñì. òàáë. 1). Êàê âèäíî èç òàáë. 3, èç äàííûõ ïîñëåäîâàòåëüíîñòè Ï24 âû÷èòàþòñÿ ñîîòâåòñòâåííî ÷èñëà 28, 19, 12 è 14 (S2 = 28 + 19 + 12 + 14 = 73). Åñëè ê òàêîé ïîñëåäîâà- òåëüíîñòè ïðèìåíèòü ÏÈ (ïåðåñòàíîâêó çíà÷åíèé âåñîâ, ñîîòâåòñòâóþ- ùèõ çíà÷åíèÿì áèòîâ 0 è 1), òî ïîëó÷èì ÓÏ, àíàëîãè÷íóþ Ï20, êîòîðàÿ îäíîçíà÷íî ñîîòâåòñòâóåò îáû÷íîé ïîñëåäîâàòåëüíîñòè (14, 16, 32, 3). Òàêèì îáðàçîì, îò ÓÏ ìîæíî ïåðåõîäèòü ê îáû÷íûì ïîñëåäîâàòåëüíîñòÿì, ó÷èòû- âàÿ ýòî ïðè ðàñøèôðîâàíèè èíôîðìàöèè. Ïîêàæåì, ÷òî èñïîëüçóÿ îáû÷íûå ïîñëåäîâàòåëüíîñòè, ïîñòðîåííûå òà- êèì ñïîñîáîì, ìîæíî êàê çàøèôðîâàòü, òàê è ðàñøèôðîâàòü èíôîðìàöèþ. Èíôîðìàöèîííûé áëîê 1001. Çàøèôðîâàíèå èíôîðìàöèè: 1001 14 + 0 + 0 +3 = 17. Èíôîðìàöèîííûé áëîê 1001. Ðàñøèôðîâàíèå èíôîðìàöèè: Ø à ã 1. 17 + S2 = 17 + 73 = 90. Ø à ã 2. (90 � 37–1)(mod 67) = (90 � 29)(mod 67) = 64. Ø à ã 3. 64 – S1 = 64 – 25 = 39. Ø à ã 4. Ðàñøèôðîâàíèå ñóììû 39 (ñì. òàáë. 2) ñ èñïîëüçîâàíèåì äàí- íûõ ïîñëåäîâàòåëüíîñòè Ï22 (ñì. òàáë. 1). Ø à ã 5. Ïîëíàÿ èíâåðñèÿ (ñîãëàñíî òàáë. 3) äëÿ ïîëó÷åííîãî ñëîâà: 0110 1001. Èíâåðòèðîâàííîå ñëîâî ñîâïàëî ñ èñõîäíûì. Èíôîðìàöèîííûé áëîê 0010. Çàøèôðîâàíèå èíôîðìàöèè: 0010 0 + 0 + 32 + 0 = 32. Èíôîðìàöèîííûé áëîê 0010. Ðàñøèôðîâàíèå èíôîðìàöèè: Ø à ã 1. 32 + S2 = 32 + 73 = 105. Ø à ã 2. (105 � 37–1)(mod 67) =(105 � 29)(mod 67) = 30. Ñ.Ä. Âèííè÷óê 10 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 Íîìåð ñòðîêè Ïîñëåäîâàòåëüíîñòü Ïðåîáðàçîâàíèå Âåñ áèòîâ 1 2 3 4 1 Îáû÷íàÿ Ìîäóëü ðàçíîñòè w w wi i i * \| \|� �1 0 14 16 32 3 2 Îáû÷íàÿ ÎÌÏ ñòðîêè 1 ( )(mod )w di 67 ( )d � 29 4 62 57 20 3 Èñõîäíàÿ ñâåðõâîçðàñ- òàþùàÿ ïîñëåäîâàòåëü- íîñòü vi 4 5 10 20 4 Îáû÷íàÿ 67 – vi = m – vi 63 62 57 47 Òàáëèöà 3. Àíàëèç ìîäóëüíûõ ïðåîáðàçîâàíèé Ø à ã 3. 30 – S1 = 30 – 25 = 5. Ø à ã 4. Ðàñøèôðîâàíèå ñóììû 5 (ñì. òàáë. 2) ñ èñïîëüçîâàíèåì äàí- íûõ ïîñëåäîâàòåëüíîñòè Ï22 (ñì. òàáë. 1). Ø à ã 5. Ïîëíàÿ èíâåðñèÿ (ñîãëàñíî òàáë. 3) äëÿ ïîëó÷åííîãî ñëîâà: 1101 0010. Èíâåðòèðîâàííîå ñëîâî ñîâïàëî ñ èñõîäíûì. Ïðèâåäåííûå ïðèìåðû ïîçâîëÿþò óáåäèòüñÿ, ÷òî òàêîé ñïîñîá øèô- ðîâàíèÿ âîçìîæåí, íî ïðè ðàñøèôðîâàíèè ìîæåò ïîòðåáîâàòüñÿ ïîëíàÿ èëè ÷àñòè÷íàÿ èíâåðñèÿ. Îäíàêî îñòàåòñÿ íåÿñíûì, óâåëè÷èâàåòñÿ ëè ïðè ýòîì âîçìîæíîñòü ðàñêðûòèÿ ñïîñîáà øèôðîâàíèÿ. Èç òàáë. 1 âèäíî, ÷òî äëÿ ïîñëåäîâàòåëüíîñòè Ï20, Ï21, Ï22 è Ï23 ïîñòîÿííûì ÿâëÿåòñÿ ìîäóëü ðàçíîñòè ýëåìåíòîâ îäíîãî è òîãî æå ñòîëá- öà. Òàêîé ìîäóëü ðàçíîñòè ïîçâîëÿåò ñðàçó îïðåäåëÿòü çíà÷åíèå îäíîãî èç ýëåìåíòîâ ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè. Ïîýòîìó èñïîëüçîâà- íèå òîëüêî ïðåîáðàçîâàíèé Ï1—Ï3 íåëüçÿ ñ÷èòàòü óñèëåíèåì ñïîñîáà øèôðîâàíèÿ ðàíöàìè. Ïðîàíàëèçèðóåì äàëåå, ÷òî ïðè ýòîì äîáàâëÿåò ìîäóëüíîå ïðåîáðàçîâàíèå ÓÏ. Äëÿ ïîñëåäîâàòåëüíîñòåé Ï24 è Ï25 (ñì. òàáë. 1) õàðàêòåðíî îäèíàêî- âîå çíà÷åíèå ìîäóëÿ ðàçíîñòè ýëåìåíòîâ îäíîãî ñòîëáöà: w w wi i i \| \|� �1 0 . Ïîýòîìó ëîãè÷íî ïðîâåðèòü âîçìîæíîñòü ïîëó÷åíèÿ ýëåìåíòîâ ñâåðõâîç- ðàñòàþùåé ïîñëåäîâàòåëüíîñòè (4, 5, 10, 20) ïî îáû÷íîé ïîñëåäîâàòåëü- íîñòè (14, 16, 32, 3) ñ èñïîëüçîâàíèåì ÎÌÏ (3) (ñì. òàáë. 3). Èç äàííûõ òàáë. 3 ñëåäóåò, ÷òî òîëüêî äëÿ îïðåäåëåííîé ÷àñòè ñëó÷àåâ (áèòû 1, 4) òàêèì ñïîñîáîì ìîæíî íàéòè ýëåìåíòû ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè v i . Äëÿ äðóãîé ÷àñòè ñëó÷àåâ (áèòû 2, 3) áóäóò îïðå- äåëåíû ðàçíîñòè m – v i , à ýòî íå ïîçâîëÿåò ðàñøèôðîâàòü èíôîðìàöèþ, èñïîëüçóÿ òîëüêî ÎÌÏ. Ñëåäîâàòåëüíî, ïðåîáðàçîâàíèÿ Ï1—Ï5 ïðè èñ- ïîëüçîâàíèè ÓÏ ïîçâîëÿþò ñòðîèòü íîâûå îáû÷íûå ïîñëåäîâàòåëüíîñòè ïî ñâåðõâîçðàñòàþùèì, äëÿ êîòîðûõ íå ñóùåñòâóåò ÎÌÏ, âîññòàíàâëè- âàþùåãî âñå ýëåìåíòû ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè. Íåïðÿìûå ìîäóëüíûå ïðåîáðàçîâàíèÿ. Êàê âèäíî èç òàáë. 3, ïðè ïîñòðîåíèè îáû÷íûõ ïîñëåäîâàòåëüíîñòåé ïî ñâåðõâîçðàñòàþùèì ñ èñ- ïîëüçîâàíèåì ÓÏ è èõ ïðåîáðàçîâàíèé Ï1—Ï5 âîçìîæíû ñëó÷àè, êîãäà ïðè îäíîêðàòíîì èñïîëüçîâàíèè ÏÌÏ (1) ôîðìèðóåòñÿ òàêàÿ îáû÷íàÿ ïî- ñëåäîâàòåëüíîñòü, ÷òî åå ÎÌÏ (3) ïîçâîëÿåò íàéòè ëèáî ýëåìåíòû ñâåðõâîç- ðàñòàþùåé ïîñëåäîâàòåëüíîñòè v i , ëèáî ðàçíîñòè m – v i . Â ïîñëåäíåì ñëó÷àå òðåáóåòñÿ îòäåëüíîå ðàññìîòðåíèå, â ñâÿçè ñ ÷åì ââåäåíî ïîíÿòèå ÍÌÏ. Îïðåäåëåíèå 2. Íåïðÿìûì ìîäóëüíûì ïðåîáðàçîâàíèåì áóäåì íàçû- âàòü ïðåîáðàçîâàíèå âèäà w m v n m* ( )(mod )� � , (6) ãäå 0 < v < m. Ìåòîä óäâîåíèÿ ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ â çàäà÷å Ìåðêëÿ—Õåëëìàíà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 11 Ñîãëàñíî îïðåäåëåíèþ 2 â ðåçóëüòàòå ïðåîáðàçîâàíèé áàçîâîé ñâåðõ- âîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè â ðÿäå ñëó÷àåâ ïîëó÷åíû êàê ÏÌÏ (1), òàê è ÍÌÏ (6) (òàáë. 4). Âûÿñíèì óñëîâèÿ, ïðè êîòîðûõ âîçíèêàþò ÍÌÏ â ñëó÷àÿõ ïðåîáðàçîâàíèé Ï1—Ï5. Ïóñòü çàäàí íåêîòîðûé ýëåìåíò ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëü- íîñòè, íàïðèìåð y = 10. Äëÿ ïîñëåäîâàòåëüíîñòåé Ï20—Ï23 (ñì. òàáë. 1) åìó ñîîòâåòñòâóåò ïàðà ÷èñåë 0 è y =10. Äîïóñòèì, ÷òî ê ýòèì ÷èñëàì îäíîâðåìåííî ïðèáàâëÿåòñÿ îäíî è òî æå ÷èñëî õ. Ïîëó÷åííûå ÷èñëà ïðå- îáðàçóåì ñîãëàñíî (1), íàéäåì ìîäóëü èõ ðàçíîñòè è ñðàâíèì òàêèå âå- ëè÷èíû ñî çíà÷åíèåì w02 ÏÌÏ ÷èñëà y = 10, ãäå w y0 37 67� �( ) (mod ) � � �( ) (mod )10 37 67 35, m w� � � �0 67 35 32. Ðåçóëüòàòû òàêèõ ïðåîáðàçîâàíèé äëÿ ðàçëè÷íûõ çíà÷åíèé õ ïðèâåäå- íû â òàáë. 4, èç êîòîðîé âèäíî, ÷òî ïðè õ = 0, 2, 4 wi * îïðåäåëÿåòñÿ êàê ÏÌÏ, à ïðè õ = 1, 3, 5 — êàê ÍÌÏ. Ñëåäîâàòåëüíî, íà èçìåíåíèå ìîäóëÿ ðàçíîñòè ðåçóëüòàòîâ ÏÌÏ ýëåìåíòîâ â ÓÏ ìîæåò ïîâëèÿòü ñèíõðîííîå èçìåíåíèå âåñîâ. Ïîýòîìó ìîæíî ïðåäïîëîæèòü, ÷òî ïîëó÷åíèå ðåçóëü- òàòà ÍÌÏ (6) äëÿ ýëåìåíòà y âîçìîæíî ïðè íàõîæäåíèè õîòÿ áû îäíîãî çíà÷åíèÿ õ, òàêîãî, ïðè êîòîðîì ñïðàâåäëèâî íåðàâåíñòâî (( ) ) (mod ) ( ) (mod )y x n m x n m � . (7) Â ðåçóëüòàòå àíàëèçà ðàçëè÷íûõ çíà÷åíèé y, x, m, n, d óñòàíîâëåíî, ÷òî äëÿ âñåõ ñëó÷àåâ ìîäóëü ðàçíîñòè \|(( ) ) (mod ) ( ) (mod )\|x y n m x n m � \| ðàâ- íÿåòñÿ ( ) (mod )y n m èëè m y n m�( ) (mod ). Èñêëþ÷åíèåì ÿâëÿåòñÿ ñëó÷àé y = d = n–1, êîãäà äëÿ ëþáîãî çíà÷åíèÿ x ðàçíîñòü ðàâíÿåòñÿ åäèíèöå, êðîìå ñëó÷àÿ, êîãäà x + y = m. Ñëåäîâàòåëüíî, ïîäáîðîì ÷èñëà x âñåãäà ìîæíî äîáèòüñÿ òîãî, ÷òîáû ìîäóëü ðàçíîñòè ðàâíÿëñÿ m y n m�( )(mod ). Ñëåäóåò çàìåòèòü, ÷òî ïðè ÎÌÏ (2) ÷èñëà m y n m�( ) (mod ) âñåãäà ïîëó÷èì (( ( ) (mod )) ) (mod ) ( ( ) (mod ))(mod )m y n m d m md y n d m m� � � � � � � � � � � �( ( ) (mod ))(mod ) ( )(mod ) ( )(mod )y n d m m m y n d m m y m m y. Ñ.Ä. Âèííè÷óê 12 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 Ïðåîáðàçîâàíèå Âåñ áèòà ïðè èçìåíåíèè ýëåìåíòà ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè íà âåëè÷èíó õ 0 1 2 3 4 5 ÏÌÏ ïðè v xi � : w vi i1 37 67� ( )(mod ) 0 37 7 44 14 51 v xi � 10 10 11 12 13 14 15 ÏÌÏ ïðè v xi � 10 : w vi i2 37 67� ( )(mod ) 35 5 42 12 49 19 Ìîäóëü ðàçíîñòè w w wi i i * \| \|� �1 2 35 32 35 32 35 32 Òàáëèöà 4. Àíàëèç ÏÌÏ ïðè ñèíõðîííîì èçìåíåíèè âåñîâ áèòà Òàêèì îáðàçîì, èñïîëüçóÿ ÓÏ, ìîæíî ïîëó÷èòü ÍÌÏ êàê ðàçíîñòü ÏÌÏ. Ïîñòðîåíèå îáû÷íîé ïîñëåäîâàòåëüíîñòè ñ èñïîëüçîâàíèåì îäíî- êðàòíîé ÍÌÏ. Ðàññìîòðèì âàðèàíòû ïîñòðîåíèÿ ñïîñîáîâ øèôðîâàíèÿ, êîòîðûå, â êîíå÷íîì èòîãå, äàþò âîçìîæíîñòü ïîëó÷èòü îäíó îáû÷íóþ ïî- ñëåäîâàòåëüíîñòü êàê ïîëíûé àíàëîã ïîñëåäîâàòåëüíîñòè Ï20. Ïðè ýòîì âîçìîæíû ðàçëè÷íûå âàðèàíòû íà÷àëüíûõ ïðåîáðàçîâàíèé Ï1—Ï5 ñâåðõ- âîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè íà îñíîâå ÓÏ. Àëãîðèòì ïîñòðîåíèÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè îñíîâàí íà îïðå- äåëåíèè îäíîãî èç êîðíåé íåðàâåíñòâà (7). Øàãè àëãîðèòìà ïðèâåäåíû â òàáë. 5 è 6. Íà îñíîâàíèè àíàëèçà äàííûõ òàáë. 5 ìîæíî ñäåëàòü ñëåäóþ- ùèå âûâîäû. 1. Ñïîñîá ïîñòðîåíèÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè ïî ñâåðõâîçðàñ- òàþùåé ïîçâîëÿåò èñïîëüçîâàòü ïðåîáðàçîâàíèÿ ÓÏ, ïðè êîòîðûõ ðåçóëü- òàò ÍÌÏ ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè (wi * = �wi 0, i � �1 6) ìîæíî ïîëó÷èòü êàê ðàçíîñòü ðåçóëüòàòîâ îáû÷íûõ ÏÌÏ ýëåìåíòîâ ñòîëáöà ÓÏ. 2. Ýëåìåíòàì ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè ñîîòâåòñòâóþò çíà÷åíèÿ èíôîðìàöèîííîãî áèòà, ðàâíîãî åäèíèöå, à ýëåìåíòàì ïîëó÷åí- íîé îáû÷íîé ïîñëåäîâàòåëüíîñòè — çíà÷åíèÿ èíôîðìàöèîííîãî áèòà, ðàâíîãî íóëþ. Ïîýòîìó ïðè òðàäèöèîííîì ñïîñîáå øèôðîâàíèÿ, êîãäà âåñ ðàíöà îïðåäåëÿåòñÿ êàê ñóììà âåñîâ îáû÷íîé ïîñëåäîâàòåëüíîñòè, êîòî- ðûå ñîîòâåòñòâóþò ðàâíûì åäèíèöå çíà÷åíèÿì èíôîðìàöèîííûõ áèò áëî- êà, ê ðàñøèôðîâàííîìó äâîè÷íîìó òåêñòó ñëåäóåò ïðèìåíÿòü ÏÈ, ò.å. çàìåíó èíôîðìàöèîííûõ ñèìâîëîâ, ðàâíûõ íóëþ, åäèíèöåé è íàîáîðîò. 3. Ðàñøèôðîâàíèå òåêñòà âîçìîæíî ïðè èñïîëüçîâàíèè ÏÌÏ. Âûâîä 3 âûòåêàåò èç ñëåäóþùèõ ïðåîáðàçîâàíèé äëÿ ñóììàðíîãî âåñà W: W a w a m v n mi i i L i i i L � � � � � � � �* ( ( ) (mod ) 1 1 � � � � �� s m a v n m s m a wi i i i i L i L 0 0 11 ( )(mod ) , ãäå s0 — ÷èñëî íóëåé â èíôîðìàöèîííîì áëîêå, êîòîðûé ñîîòâåòñòâóåò èíôîðìàöèîííîìó áëîêó (c1, c2, …, cL) äëèíîé L, ( ) (mod ) (mod )W d m s m a w d mi i i L � � � �� 0 1 � � � �� a w d m m a vi i i L i i i L ( ) (mod ) (mod ) 1 1 � �� (mod )m Ìåòîä óäâîåíèÿ ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ â çàäà÷å Ìåðêëÿ—Õåëëìàíà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 13 � � � �� m a v mi i i L 1 (mod ). Íà îñíîâàíèè àíàëèçà äàííûõ òàáë. 6 ìîæíî ñäåëàòü ñëåäóþùèå âûâîäû. 1. Íàéäåííûå çíà÷åíèÿ xi îáåñïå÷èâàþò âûïîëíåíèå íåðàâåíñòâà � �w wi i0 1, i L� �1 , (8) êàê â ñëó÷àå ÍÌÏ, òàê è ïðè èíâåðñèÿõ, êîãäà íóëåâûå çíà÷åíèÿ xi ÿâëÿþò- ñÿ íàèìåíüøèìè èç âîçìîæíûõ, äëÿ êîòîðûõ âûïîëíÿåòñÿ íåðàâåíñòâî (8). Ðàçëè÷íàÿ ïðèðîäà ÷èñåë xi ïðè íàëè÷èè èíâåðñèé è áåç íèõ ïðèâîäèò ê òîìó, ÷òî ïðè âñåõ èíâåðñèÿõ w w wi i i0 0� � � * , i = 2, 3, 5. 2. Ýëåìåíòàì ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè ñîîòâåòñòâóþò çíà÷åíèÿ èíôîðìàöèîííîãî áèòà, ðàâíîãî åäèíèöå (i = 1, 4, 6) è íóëþ (i = = 2, 3, 5), à ýëåìåíòàì ïîëó÷åííîé îáû÷íîé ïîñëåäîâàòåëüíîñòè — òîëüêî çíà÷åíèÿ áèòà, ðàâíûå íóëþ. Ïîýòîìó ïðè òðàäèöèîííîì ñïîñîáå øèôðî- âàíèÿ, êîãäà âåñ ðàíöà îïðåäåëÿåòñÿ êàê ñóììà âåñîâ îáû÷íîé ïîñëåäî- âàòåëüíîñòè ñîãëàñíî (2) ê ðàñøèôðîâàííîìó äâîè÷íîìó òåêñòó äëÿ ðÿäà áèò ñëåäóåò ïðèìåíÿòü ×È. Ñ.Ä. Âèííè÷óê 14 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 Íîìåð ñòðîêè Øàã àëãîðèòìà Ïåðå- ìåííàÿ Ýëåìåíòû ïîñëåäîâàòåëüíîñòåé äëÿ áèòîâ 1 2 3 4 5 6 0 Èñõîäíàÿ ñâåðõâîçðàñòàþùàÿ ïî- ñëåäîâàòåëüíîñòü vi, i = 1 � 6 ÓÏ äëÿ èñõîäíîé ñâåðõâîçðàñòàþùåé vi vi0 vi1 1 0 1 2 0 2 4 0 4 8 0 8 16 0 16 32 0 32 1 Îïðåäåëåíèå êîðíåé íåðàâåíñòâà (7) ïðè ÏÌÏ wik = (vik 84) (mod 131), k � 0 1, , i � �1 6 xi 1 3 1 3 3 1 2 Cèíõðîííîå óâåëè÷åíèå âåñîâ áèò íà êîðíè íåðàâåíñòâà (7), v ik1 � � v xik i, i � �1 6, k � 0 1, v i1 0 v i11 1 2 3 5 1 5 3 11 3 19 1 33 3 ÏÌÏ wik = (v1ik 84) (mod 131) äëÿ ýëåìåíòîâ ñòðîêè 2 wi0 84 121 84 121 121 84 wi1 37 27 27 7 24 21 4 Ñèíõðîííîå óìåíüøåíèå âåñîâ áèò: �wi0= wi0 – wi1, �wi1= wi1–wi1 = 0, i � �1 6 �wi0 47 94 57 114 97 63 �wi1 0 0 0 0 0 0 5 ÍÌÏ wi = 131 – (vi 84) (mod 131) = �wi0, i � �1 6 wi 47 94 57 114 97 63 6 Îáû÷íàÿ ïîñëåäîâàòåëüíîñòü âåñîâ wi = �wi0 = wi , i � �1 6 w i 47 94 57 114 97 63 Òàáëèöà 5. Ñïîñîá ïîñòðîåíèÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè ïî ñâåðõâîçðàñòàþùåé íà îñíîâå ÍÌÏ äëÿ Ï20 3. Ðàñøèôðîâàíèå øèôðîòåêñòà íåâîçìîæíî ïðè èñïîëüçîâàíèè òîëü- êî ÎÌÏ. Âûâîä 3 âûòåêàåò èç ñëåäóþùèõ ñîîáðàæåíèé. Ñóììàðíûé âåñ ðàíöà äëÿ ñëîâà À ÿâëÿåòñÿ ñóììîé ïðîèçâåäåíèé ýëåìåíòîâ îáû÷íîé ïîñëåäîâà- òåëüíîñòè íà çíà÷åíèå áèò ñëîâà: W a wi i k L � � � 1 . Ýòà ñóììà ìîæåò áûòü ïðåäñòàâëåíà â âèäå � � � � � � �W a w a m v n m a v n ms i i k L i i i i ei1 0 ( ( ) (mod )) (( ) (mod )�� ei 1 ), ãäå èíäåêñ ei îïðåäåëÿåò óñëîâèå âûïîëíåíèÿ èíâåðñèè äëÿ ³-ãî ýëåìåíòà ïîñëåäîâàòåëüíîñòè (ei = 1, åñëè ïðåîáðàçîâàíèå íå âûïîëíÿëîñü, ei = 0, Ìåòîä óäâîåíèÿ ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ â çàäà÷å Ìåðêëÿ—Õåëëìàíà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 15 Íîìåð ñòðîêè Øàã àëãîðèòìà Ïåðå- ìåííàÿ Ýëåìåíòû ïîñëåäîâàòåëüíîñòåé äëÿ áèòîâ 1 2 3 4 5 6 0 Èñõîäíàÿ ñâåðõâîçðàñòàþùàÿ ïî- ñëåäîâàòåëüíîñòüvi, i = 1�6 vi 1 2 4 8 16 32 ÓÏ äëÿ èñõîäíîé ñâåðõâîçðàñòàþùåé vi0 vi1 0 1 0 2 0 4 0 8 0 16 0 32 1 ×È äëÿ áàçîâîé ÓÏ �vi0 �vi1 0 1 2 0 4 0 0 8 16 0 0 32 2 Îïðåäåëåíèå êîðíåé íåðàâåíñòâà (7) ïðè ÏÌÏ wik = (vik 84)(mod 131), k � � 0 1, , i � �1 6 xi 1 0 0 3 0 1 3 Cèíõðîííîå óâåëè÷åíèå âåñîâ áèò íà ÷èñëî xi: v v xik ik i1 � � , i � �1 6, k � 0 1, , S1 27� v i1 0 v i11 1 2 2 0 4 0 3 11 16 0 1 33 4 ÏÌÏ wik = (v1ik 84) (mod 131), k � 0 1, , i � �1 6, äëÿ ýëåìåíòîâ ñòðîêè 3 wi0 wi1 84 37 37 0 74 0 121 7 34 0 84 21 5 Ñèíõðîííîå óìåíüøåíèå âåñîâ áèò: �wi0= wi0 – wi1, �wi1= wi1 – wi1 = 0, i � � �1 6, S 2 65� �wi0 �wi1 47 0 37 0 74 0 114 0 34 0 63 0 6 ÍÌÏ wi = 131–(vi 84) (mod 131) i � � �1 6 wi * 47 94 57 114 97 63 7 Îáû÷íàÿ ïîñëåäîâàòåëüíîñòü wi = = �wi0 � wi *, i � �1 6 w i 47 37 74 114 34 63 Òàáëèöà 6. Ñïîñîá ïîñòðîåíèÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè ïî ñâåðõâîçðàñòàþùåé íà îñíîâå ÍÌÏ äëÿ Ï20 ñ èñïîëüçîâàíèåì ×È åñëè îíî âûïîëíåíî). Òîãäà ïðè èñïîëüçîâàíèè îáû÷íîãî ÎÌÏ ïîëó÷èì ( ) (mod ) ( ( ) (mod )) (( ) (mod )W d m a m v n m a v n mi i i i ee ii � � � � 0� � � � � � � � � � 1 d m) (mod ) � � � � � � � � � �� a v a v mi i i i ee ii 01 (mod ), (9) ãäå ïîñëåäíåå âûðàæåíèå â ñêîáêàõ ìîæåò áûòü êàê ïîëîæèòåëüíûì, òàê è îòðèöàòåëüíûì ÷èñëîì. Ýòî âûðàæåíèå îòîáðàæàåò ñóììó ýëåìåíòîâ ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè òîëüêî òîãäà, êîãäà ïåðâàÿ èç ñóìì â ñêîáêàõ ðàâíà íóëþ. Äëÿ òàêîãî âàðèàíòà øèôðîâàíèÿ èíôîðìàöèè òàêæå ñóùåñòâóåò ñïî- ñîá ðàñøèôðîâàíèÿ íà îñíîâå ÓÏ. Ïóñòü èçâåñòíà îáû÷íàÿ ïîñëåäîâà- òåëüíîñòü { }wi i n �1. Òîãäà ñóììàðíûé âåñ S, ñîîòâåòñòâóþùèé ñëîâó À, ñîãëàñíî îáîçíà÷åíèÿì ïåðåìåííûõ, ïðèíÿòûì â òàáë. 6, ìîæíî çàïèñàòü â âèäå S w w wi a i a i ai i i � � � � � � � � � � 1 0 1 1 0 . Êàê âèäíî èç òàáë. 6, ýëåìåíòàì îáû÷íîé ïîñëåäîâàòåëüíîñòè ñòðîêè 7 ñîîòâåòñòâóþò ýëåìåíòû ÓÏ, ïðåäñòàâëåííûå â ñòðîêå 5. Ïåðåõîä îò ñòðîêè 7 ê ñòðîêå 5 íå èçìåíÿåò çíà÷åíèÿ ñóììàðíîãî âåñà S. Ðàññìîòðèì ÓÏ, ïðåäñòàâëåííóþ â ñòðîêå 4 òàáë. 6. Ïðè ýòîì ïåðåõîäå ñóììàðíûé âåñ S âîçðàñòåò íà âåëè÷èíó S2 = 65, êîòîðàÿ ðàâíÿåòñÿ ñóììå ýëåìåíòîâ wi1, à îáùàÿ ñóììà óâåëè÷èòñÿ íà ÷èñëî S2 è áóäåò ðàâíà S + S2 : S S S w wi a i i n i 01 2 0 1 1 1 � � � � � � . Ýëåìåíòû ÓÏ ñòðîêè 3 ìîæíî ïîëó÷èòü ñ ïîìîùüþ ÎÌÏ ñòðîêè 4. Ýòî çíà- ÷èò, ÷òî åãî ìîæíî ïðèìåíèòü è ê ñóììå ýëåìåíòîâ. Òîãäà èç (8) ïîëó÷èì (( ) ) (mod )S S d m w w di c i i n i � � � � � � � � � � � � � � � � � � �2 0 1 1 1 (mod )m v v Si c i ci i � � � � � �1 11 1 0 0 02. Åñëè îò ñóììû S02 âû÷åñòü ñóììó S1 (ýëåìåíòû v i 0 — êîðíè íåðàâåíñòâà (8)), òî ïîëó÷èì âåñ S03, ðàññ÷èòàííûé ïî ñâåðõâîçðàñòàþùåé ïîñëåäîâà- òåëüíîñòè, ïðåîáðàçîâàííîé íà îñíîâå ×È: S v v v x v xi a i a i i a i i ai i i 03 1 1 0 0 1 1 01 1� � � � � � � � � � � � �( ) ( ) i � � 0 Ñ.Ä. Âèííè÷óê 16 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 � � � � � � � � � �v v x S Si a i a i i n i i 1 10 0 1 1 1 02 1. Òåïåðü èíôîðìàöèîííîå ñëîâî ìîæíî ðàñøèôðîâàòü, èñïîëüçóÿ èçâåñò- íûå äàííûå îá ÓÏ, ïîëó÷åííîé â ðåçóëüòàòå ×È èñõîäíîé ñâåðõâîç- ðàñòàþùåé ïîñëåäîâàòåëüíîñòè, ïðåäñòàâëåííîé â òàáë. 6. Ñëåäîâàòåëüíî, ïðè ðàñøèôðîâàíèè èíôîðìàöèè ñ ïîìîùüþ óâåëè- ÷åíèÿ èñõîäíîé ñóììû S íà S2 ñòàíîâèòñÿ âîçìîæíûì ÎÌÏ ïîëó÷åííîé ñóììû, ïîñëå ÷åãî åå óìåíüøåíèå íà S1 îáðàçóåò ñóììó ýëåìåíòîâ ñâåðõ- âîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè ïðè ×È. Òàêèì îáðàçîì, èñïîëüçîâà- íèå ñóìì S1 è S2 ôîðìèðóåò «ëàçåéêó» äëÿ îäíîêðàòíûõ ÍÌÏ ñ èñïîëü- çîâàíèåì ×È. Ðàññìîòðèì ïðèìåð çàøèôðîâàíèÿ è ðàñøèôðîâàíèÿ èíôîðìàöèè ñ èñïîëüçîâàíèåì îáû÷íîé ïîñëåäîâàòåëüíîñòè äëÿ áëîêà 100111. Èíôîðìàöèîííûé áëîê 100111. Çàøèôðîâàíèå èíôîðìàöèè: 100111 47, 37, 74, 114, 34, 63, S = 47 + 114 + 34 + 63 = 258. Èíôîðìàöèîííûé áëîê 100111. Ðàñøèôðîâàíèå èíôîðìàöèè: Ø à ã 1. S03 = S02 + S1 = 258 + 63 = 323. Ø à ã 2. S02 = (( S + S2) 39) (mod 131) = (323�39) (mod 131) = 21. Ø à ã 3. S03 = S02 – S1 = 21 – 5 = 16. Ø à ã 4. Ðàñøèôðîâàíèå ñóììû 16 ñ èñïîëüçîâàíèåì ïîñëåäîâàòåëü- íîñòè Ï21 (òàáë. 7). Åñëè áû ïðè ðàñøèôðîâàíèè áûëà èñïîëüçîâàíà èñõîä- íàÿ ñâåðõâîçðàñòàþùàÿ ïîñëåäîâàòåëüíîñòü, òî ïîòðåáîâàëàñü áû èíâåðñèÿ áèò 1, 4 è 6. Íà îñíîâàíèè èçëîæåííîãî ìîæíî ñäåëàòü âûâîä î òîì, ÷òî â ñëó÷àå øèôðîâàíèÿ íà îñíîâå îáû÷íûõ ïîñëåäîâàòåëüíîñòåé, ïîñòðîåííûõ ñ ïîìîùüþ ×È è ÍÌÏ, äëÿ ðàñøèôðîâàíèÿ øèôðîòåêñòà òðåáóåòñÿ çíàíèå ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè, ñóìì S1 è S2 è âàðèàíòà ×È. Ìåòîä óäâîåíèÿ ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ â çàäà÷å Ìåðêëÿ—Õåëëìàíà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 17 Íîìåð áèòà Óñëîâèå îïðåäåëåíèÿ çíà÷åíèÿ áèòà Çíà÷åíèå áèòà 6 16 < 32 1 5 16 < = 16 (16 � 16 = 0) 1 4 0 < 8 1 3 0 < 4 0 2 0 < 2 0 1 0 < 1 1 Òàáëèöà 7. Ðàñøèôðîâàíèå ñóììû 16 Èñïîëüçîâàíèå îäíîêðàòíûõ èíâåðñèé è îäíîêðàòíûõ ÍÌÏ ïðè ôîðìèðîâàíèè ÎÌÏ. Âûøå áûëî óêàçàíî, ÷òî ïðè èñïîëüçîâàíèè òîëü- êî îäíîêðàòíûõ ÍÌÏ â ñëó÷àå ôîðìèðîâàíèÿ îáû÷íîé ïîñëåäîâàòåëü- íîñòè âîçíèêàåò íåîáõîäèìîñòü ÏÈ ðàñøèôðîâàííîãî èíôîðìàöèîííîãî ñîîáùåíèÿ. Òàêîå óòâåðæäåíèå âûòåêàåò èç îïðåäåëåíèÿ ÍÌÏ ïðè åãî ðåàëèçàöèè ÷åðåç ÓÏ, êîãäà â ðåçóëüòàòå ÏÌÏ ïîëó÷åíû òàêèå ïðåîáðà- çîâàííûå ÷èñëà, ñðåäè êîòîðûõ ìåíüøèì áóäåò ÷èñëî, ñîîòâåòñòâóþùåå íà÷àëüíîìó ýëåìåíòó, óâåëè÷åííîìó íà êîðåíü íåðàâåíñòâà (7), à áîëü- øèì — ñîîòâåòñòâóþùåå êîðíþ íåðàâåíñòâà (7). Ñëåäîâàòåëüíî, îäíî- êðàòíîå ÍÌÏ âñåõ ýëåìåíòîâ ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè ïðè âîäèò ê íåîáõîäèìîñòè èíâåðñèè êàæäîãî áèòà èíôîðìàöèè, ò.å. ê ÏÈ. Â ñëó÷àå èñïîëüçîâàíèÿ ÍÌÏ è ×È íà îñíîâå ÓÏ ðàñøèôðîâàíèå çà- øèôðîâàííîé èíôîðìàöèè âîçìîæíî, íî ïðè ýòîì òðåáóåòñÿ áîëåå ïîëíàÿ èíôîðìàöèÿ, ÷åì ñâåðõâîçðàñòàþùàÿ ïîñëåäîâàòåëüíîñòü. Äåéñòâèòåëü- íî, êàê âèäíî èç òàáë. 7, èñïîëüçîâàíèå òîëüêî ñâåðõâîçðàñòàþùåé ïîñëå- äîâàòåëüíîñòè ïðèâîäèò ê òîìó, ÷òî ïîñëå ðàñøèôðîâàíèÿ âìåñòî èíôîð- ìàöèîííîãî áëîêà 100111 ïîëó÷àåì áëîê 000010, ò.å. ðàñøèôðîâàííàÿ èíôîðìàöèÿ îòëè÷àåòñÿ îò íà÷àëüíîé â ïåðâîì, ÷åòâåðòîì è øåñòîì áèòå. Òàêèì æå áóäåò îòëè÷èå äëÿ ëþáîãî äðóãîãî èíôîðìàöèîííîãî áëîêà, ò.å. â òåõ áèòàõ èíôîðìàöèè, â êîòîðûõ íå áûëà ïðèìåíåíà ×È. Ñëåäîâàòåëüíî, ïðè èñïîëüçîâàíèè ×È íåéòðàëèçóåòñÿ äåéñòâèå ÍÌÏ îòíîñèòåëüíî èíâåðñèè èíôîðìàöèîííûõ áèò äàííûõ. Â òî æå âðåìÿ, äëÿ îáû÷íûõ ïîñëåäîâàòåëüíîñòåé, ïîëó÷åííûõ ñ èñïîëüçîâíèåì îäíîãî ÍÌÏ, íåîáõîäèìà ïîëíàÿ èíâåðñèÿ áèò èíôîðìàöèîííîãî áëîêà. Ñóòü ìåõàíèçìà äåéñòâèÿ ×È çàêëþ÷àåòñÿ â ñëåäóþùåì. Ïðè èíâåð- ñèè áèòà äàííûõ çíà÷åíèå ðàçíîñòè ÷èñåë áîëüøå íóëÿ, ïîëó÷åííûõ ïî- ñðåäñòâîì ÏÌÏ ÓÏ, äîñòèãàåòñÿ ïðè õ³ = 0 è ðÿäå äðóãèõ çíà÷åíèé õ³. Ïîýòîìó ïðè èíâåðñèè è ÏÌÏ ýëåìåíòîâ ÓÏ ïðîèñõîäèò äâîéíàÿ èíâåð- ñèÿ, â ñâÿçè ñ ÷åì ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå. Óòâåðæäåíèå. Íåîáõîäèìîñòü èíâåðñèè èíôîðìàöèîííîãî áèòà ïîñ- ëå åãî ðàñøèôðîâàíèÿ íà îñíîâå ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè îïðåäåëÿåòñÿ ñóììîé ïî ìîäóëþ äâà îáùåãî ÷èñëà ìîäóëüíûõ ïðåîá- ðàçîâàíèé è ÷èñëà èíâåðñèé äëÿ ýòîãî áèòà, êîòîðûå áûëè èñïîëüçîâàíû ïðè ôîðìèðîâàíèè îáû÷íîé ïîñëåäîâàòåëüíîñòè ïî ñâåðõâîçðàñòàþùåé. Ñîãëàñíî ýòîìó óòâåðæäåíèþ âîçìîæíûì ÿâëÿåòñÿ ñëåäóþùèé ñïî- ñîá ðàñøèôðîâàíèÿ òåêñòà: ïîñëå âûïîëíåíèÿ âñåõ ýòàïîâ ðàñøèôðîâàíèÿ âïëîòü äî èñïîëüçîâàíèÿ ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè íåîá- õîäèìàÿ èíâåðñèÿ äëÿ áèò èíôîðìàöèîííîãî áëîêà ðåàëèçóåòñÿ ïîñðåäñò- âîì ïîáèòîâîãî ñëîæåíèÿ ïî ìîäóëþ äâà ïîëó÷åííîãî ñëîâà ñ íåêîòîðûì áàëàíñèðóþùèì ñëîâîì äëèíîé, ðàâíîé äëèíå áëîêà. Òàêîé ñïîñîá âîç- Ñ.Ä. Âèííè÷óê 18 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 ìîæåí, òàê êàê ñóììà ïî ìîäóëþ äâà äëÿ ÷èñëà èíâåðñèé (çíà÷åíèå 0 èëè 1), ïîáèòîâîå äâîè÷íîå äîáàâëåíèå êîòîðîé â ñëó÷àå çíà÷åíèÿ 1 ðåàëèçóåò èíâåðñèþ, à ïðè ñóììå, ðàâíîé 0, íå èçìåíÿåò ðåçóëüòàòà. Ïîýòîìó ïðè îáû÷íîé ïîñëåäîâàòåëüíîñòè Ï25 (ñì. â òàáë. 3) áàëàíñèðóþùèì ñëîâîì áóäåò 1111. Äëÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè Ï21 (ñì. òàáë. 7) áàëàíñè- ðóþùåå ñëîâî — 100101. Ïîâòîðíîå èñïîëüçîâàíèå ÍÌÏ. Äëÿ ïîñòðîåíèÿ îáû÷íîé ïîñëåäî- âàòåëüíîñòè ïî ñâåðõâîçðàñòàþùåé ìîæíî èñïîëüçîâàòü êðàòíûå ÏÌÏ è ÍÌÏ è êðàòíûå èíâåðñèè. Ïîêàæåì ýòî íà ïðèìåðå ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè Ï20 (ñì. òàáë. 1), øàãè àëãîðèòìà ïîñòðîåíèÿ êîòî- ðîé ïðèâåäåíû â òàáë. 8. Äëÿ ðàññìàòðèâàåìîãî âàðèàíòà ïîñòðîåíèÿ îáû÷íîé ïîñëåäîâàòåëü- íîñòè ÍÌÏ ïðèìåíÿþòñÿ ÷åòíîå ÷èñëî ðàç êî âñåì èíôîðìàöèîííûì áèòàì. Ïðè êðàòíîì äâóì ÷èñëå ÍÌÏ ðåàëèçóåòñÿ äâîéíàÿ èíâåðñèÿ: 0 1 0 è 1 0 1. Â ýòîì ñëó÷àå íå òðåáóþòñÿ äîïîëíèòåëüíûå îïåðà- öèè èíâåðñèè ïðè ðàñøèôðîâàíèè áèò èíôîðìàöèè, ò.å. íå òðåáóåòñÿ õðàíåíèå áàëàíñèðóþùåãî ñëîâà. Â ðàññìîòðåííîì ïðèìåðå ñóììû S1 è S2 îïðåäåëÿëèñü íà êàæäîì óðîâíå èòåðèðîâàíèÿ. Èìåííî îíè (à òàêæå áà- ëàíñèðóþùåå ñëîâî) ÿâëÿþòñÿ ðåçóëüòàòîì ôîðìèðîâàíèÿ «ëàçåéêè», ïîç- âîëÿþùåé ðàñøèôðîâàòü èíôîðìàöèþ. Ïðèâåäåííûå ïðèìåðû ïîñòðîåíèÿ îáû÷íûõ ïîñëåäîâàòåëüíîñòåé èç ñâåðõâîçðàñòàþùèõ íå ÿâëÿþòñÿ óíèêàëüíûìè. Äëÿ ïðîâåðêè êîððåêò- íîñòè ïîäõîäà ðàçðàáîòàíî íåñêîëüêî êîìïüþòåðíûõ ïðîãðàìì, ðåàëè- çóþùèõ ôîðìèðîâàíèå îáû÷íûõ ïîñëåäîâàòåëüíîñòåé èç ñëó÷àéíûõ âà- ðèàíòîâ ñâåðõâîçðàñòàþùèõ ñ ïîñëåäóþùåé ïðîâåðêîé âñåõ âàðèàíòîâ çàøèôðîâàíèÿ è ðàñøèôðîâàíèÿ. Ïî ðåçóëüòàòàì èõ ðàáîòû ïîëó÷åíî äîïîëíèòåëüíîå óñëîâèå íà ýòàïå ðàñøèôðîâàíèÿ äàííûõ: åñëè íà êàêîì- ëèáî óðîâíå ðàñøèôðîâàíèÿ ñóììà îêàæåòñÿ îòðèöàòåëüíîé, òî åå íåîáõî- äèìî óâåëè÷èòü íà ÷èñëî m1 èç ýòîãî æå óðîâíÿ (îïðåäåëèòü çíà÷åíèå ïî ìîäóëþ m1). Ïðè âûïîëíåíèè ýòîãî óñëîâèÿ âî âñåõ ñëó÷àÿõ ðàñøèôðî- âàííàÿ èíôîðìàöèÿ áûëà ïðàâèëüíîé. Ñëåäóåò çàìåòèòü, ÷òî íà êàæäîì ýòàïå ïðåîáðàçîâàíèÿ îáû÷íîé ïî- ñëåäîâàòåëüíîñòè â ñâåðõâîçðàñòàþùóþ ÎÌÏ ñóììàðíûé âåñ ðàíöà S1 îòîáðàæàåò ðàçíîñòü äâóõ ñóìì, õàðàêòåðèçóþùèõ èíôîðìàöèîííûé áëîê, à íå ñóììó ýëåìåíòîâ ïîñëåäîâàòåëüíîñòè ïðåäûäóùåãî óðîâíÿ (ïðè ìíî- ãîêðàòíîì èòåðèðîâàíèè) èëè ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè. Ïîýòîìó ïðè îïðåäåëåíèè ïîñëåäîâàòåëüíîñòè ïðåäûäóùåãî óðîâíÿ äëÿ ìíîãîêðàòíî èòåðèðóåìûõ ñèñòåì èëè ñâåðõâîçðàñòàþùåé ïîñëåäîâà- òåëüíîñòè íåâîçìîæíî ñôîðìèðîâàòü ñèñòåìó óðàâíåíèé ëèíåéíîãî ïðî- ãðàììèðîâàíèÿ, à òîëüêî åå âàðèàíòû. Ìåòîä óäâîåíèÿ ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ â çàäà÷å Ìåðêëÿ—Õåëëìàíà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 19 Ïðè ôîðìèðîâàíèè îáû÷íûõ ïîñëåäîâàòåëüíîñòåé ñ èñïîëüçîâàíèåì ÍÌÏ è èíâåðñèé êàæäûé áèò äëÿ k-êðàòíî èòåðèðóåìîé ñèñòåìû ìîæåò ïðèíèìàòü 2k ðàçëè÷íûõ çíà÷åíèé. Òåîðåòè÷åñêè ýòî âûòåêàåò èç ñëåäóþ- ùåãî óñëîâèÿ: íà êàæäîì óðîâíå èòåðèðîâàíèÿ íîâîå çíà÷åíèå ýëåìåíòà îáû÷íîé ïîñëåäîâàòåëüíîñòè ìîæåò ïðèíèìàòü îäíî èç äâóõ çíà÷åíèé, ïîëó÷àåìûõ ëèáî ñîãëàñíî (1), ëèáî ñîãëàñíî (6). Ðàññìîòðèì ïðèìåð ïðàêòè÷åñêîãî ïîäòâåðæäåíèÿ òàêîãî òåîðåòè÷åñêîãî ïîëîæåííÿ. Êàæäîå èç ÷èñåë i = 1 � 9 áóäåì ðàññìàòðèâàòü êàê ýëåìåíò ñâåðõâîçðàñ- òàþùåé ïîñëåäîâàòåëüíîñòè ïðè òðåõêðàòíîì èòåðèðîâàíèè äëÿ m1 = 20, n1 = 11, m2 = 60, n2 = 37, m3 = 181, n3 = 101. Ïóñòü èíôîðìàöèÿ î ñïîñîáå Ñ.Ä. Âèííè÷óê 20 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 Íîìåð øàãà Øàã àëãîðèòìà Ïåðåìå- ííàÿ Ýëåìåíòû ïîñëåäîâàòåëüíîñòåé äëÿ áèòîâ 1 2 3 4 5 6 0 Áàçîâàÿ ïîñëåäîâàòåëüíîñòü vi , ³ = 1 � 6 vi 1 2 4 8 16 32 1.1 Ïåðâàÿ èíâåðñèÿ äëÿ ÓÏ vi0 vi1 0 1 2 0 0 4 0 8 16 0 0 32 2.1 Êîðíè (7) è èõ ñóììà S11 = 4 x i1 1 0 1 1 0 1 3.1 ÏÌÏ (m1= 67, n1 = 47, d1 = 10) w1ik = ((vik + xi) n1) (mod m1) è ïîëó- ÷åíèå ñóììû S21 = 92 w i1 0 w i11 47 27 27 0 47 34 47 21 15 0 47 10 4.1 Ïåðâàÿ îáû÷íàÿ ïîñëåäîâàòåëüíîñòü â âèäå ÓÏ w i �1 0 w i �11 20 0 27 0 13 0 26 0 15 0 37 0 1.2 Âòîðàÿ èíâåðñèÿ äëÿ ÓÏ v i2 0 v i2 1 20 0 27 0 13 0 0 26 0 15 37 0 2.2 Êîðíè (7) è èõ ñóììà S12 = 4 x i2 0 0 0 2 2 0 3.2 ÏÌÏ (m1 = 149, n1 = 71, d1 = 21) w2ik = ((vik + xi) n1) (mod m1) è ïîëó÷åíèå ñóììû S22 = 66 w i2 0 w i2 1 79 0 129 0 29 0 142 51 142 15 94 0 4.2 Âòîðàÿ îáû÷íàÿ ïîñëåäîâàòåëüíîñòü â âèäå ÓÏ w i �1 0 w i �11 79 0 129 0 29 0 91 0 127 0 94 0 1.3 Òðåòüÿ èíâåðñèÿ äëÿ ÓÏ v i3 0 v i3 1 0 79 129 0 0 29 91 0 0 127 0 94 2.3 Êîðíè (7) è èõ ñóììà S13 = 13 x i3 5 0 5 0 2 1 3.3 ÏÌÏ (m1 = 563, n1 = 101, d1 = 262) w2ik = ((vik + xi) n1) (mod m1) è ïîëó- ÷åíèå ñóììû S23 = 199 w i3 0 w i3 1 505 39 80 0 505 56 183 0 202 80 101 24 4.3 Òðåòüÿ îáû÷íàÿ ïîñëåäîâàòåëüíîñòü w i 466 80 449 183 122 77 Òàáëèöà 8. Ñïîñîá ïîñòðîåíèÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè ïðè èñïîëüçîâàíèè òðåõêðàòíûõ ìîäóëüíûõ ïðåîáðàçîâàíèé è èíâåðñèè ôîðìèðîâàíèÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè íà êàæäîì óðîâíå ïðåä- ñòàâëÿåòñÿ òàê: èíäåêñó 1 ñîîòâåòñòâóåò ÏÌÏ (ñîãëàñíî (1)), èíäåêñó 0 — ÍÌÏ (ñîãëàñíî (6)). Òîãäà òðåì ÎÌÏ áóäåò ñîîòâåòñòâîâàòü îáîçíà÷åíèå 111, à òðåì ÍÌÏ — 000. Âñåãî òàêèõ âàðèàíòîâ âîñåìü. Çíà÷åíèÿ âåñîâ áèòîâ îáû÷íîé ïîñëåäîâàòåëüíîñòè ïðèâåäåíû â òàáë. 9. Ñëåäîâàòåëüíî, ïðè óñëîâèè, ÷òî ïàðàìåòðû ìîäóëüíûõ ïðåîáðàçî- âàíèé (÷èñëà m è n â ñîîòíîøåíèÿõ (1) è (6)) íåçàâèñèìû îò âàðèàíòà ïðåîáðàçîâàíèé íà êàæäîì èç óðîâíåé èòåðèðîâàíèÿ, îáùåå ÷èñëî âàðèàí- òîâ îáû÷íûõ ïîñëåäîâàòåëüíîñòåé, ïîñòðîåííûõ ïî îäíîé è òîé æå ñâåðõ- âîçðàñòàþùåé, áóäåò ðàâíÿòüñÿ 2kL. Âûâîäû Ïðåäëîæåííûé ñïîñîá ïîëó÷åíèÿ îáû÷íîé ïîñëåäîâàòåëüíîñòè èç ñâåðõ- âîçðàñòàþùåé â çàäà÷å ôîðìèðîâàíèÿ ìíîãîêðàòíî èòåðèðîâàííîé ðàíöå- âîé ñèñòåìû øèôðîâàíèÿ ñ îòêðûòûì êëþ÷îì, îñíîâàí íà îïåðàöèè ÍÌÏ è èíâåðñèÿõ, ïðè êîòîðûõ ïîñòðîåíèå îäíîñòîðîííåé ôóíêöèè ñ «ëàçåé- êîé» ðåàëèçóåòñÿ ñ èñïîëüçîâàíèåì ïîíÿòèÿ óäâîåííîé ïîñëåäîâàòåëü- íîñòè âåñîâ ïðåäìåòîâ, à ïðè ðàñøèôðîâàíèè èíôîðìàöèè äîïîëíèòåëüíî èñïîëüçóåòñÿ áàëàíñèðóþùåå ñëîâî. Íà îñíîâàíèè ïðîâåäåííûõ èññëåäî- âàíèé ìîæíî óòâåðæäàòü, ÷òî ýòîò ñïîñîá ÿâëÿåòñÿ óñèëåíèåì êðèïòîñõåìû Ìåðêëÿ—Õåëëìàíà. Â òî æå âðåìÿ, ïîëó÷åííûå óñèëåíèÿ â çàäà÷å øèôðî- âàíèÿ ðàíöàìè òðåáóþò äîïîëíèòåëüíîãî äåòàëüíîãî êðèïòîãðàôè÷åñêîãî àíàëèçà è îöåíêè êðèïòîñòîéêîñòè. Ìåòîä óäâîåíèÿ ïîñëåäîâàòåëüíîñòè âåñîâ ïðåäìåòîâ â çàäà÷å Ìåðêëÿ—Õåëëìàíà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 21 ×èñëî v Çíà÷åíèå w ýëåìåíòà îáû÷íîé ïîñëåäîâàòåëüíîñòè äëÿ ðàçëè÷íûõ âàðèàíòîâ ïðåîáðàçîâàíèÿ 111 110 101 100 011 010 001 000 1 41 140 46 135 75 106 12 169 2 147 34 121 60 63 118 24 157 3 101 80 167 14 109 72 159 22 4 113 68 155 26 3 178 84 97 5 67 114 20 161 143 38 125 56 6 79 102 8 173 37 144 50 131 7 33 148 54 127 83 98 4 177 8 45 136 42 139 71 110 16 165 9 180 1 88 93 117 64 151 30 Òàáëèöà 9. Âåñà ýëåìåíòîâ îáû÷íîé ïîñëåäîâàòåëüíîñòè äëÿ ýëåìåíòà v ñâåðõâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè The algorithm for forming the normal sequence of eccessively ascending one, based on the intro- duced concepts of indirect modular transformations and partial inversions with the «loophole» formation on the basis of duplicate sequences of the items weights has been developed as part of the Merkle-Hellman cryptoscheme of knapsack encryption . It is shown that under such an ap- proach 2k options of the element of normal sequence may correspond to each element above the ascending sequence for the k-fold iterated backpack system, and the number of options of normal sequence, with all the same parameters of the modular transformations, may achieve 2kL, where L is the number of bits in the data block. In this case, the inverse problem of determining the exces- sively ascending sequence of the normal one can be reduced to the problem of integer linear pro- gramming only as a variant with the great number of options. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Øíàéåð Á. Ïðèêëàäíàÿ êðèïòîãðàôèÿ. Ïðîòîêîëû, àëãîðèòìû, èñõîäíûå òåêñòû íà ÿçûêå Ñè: Ïåð. ñ àíãë. — Ì. : èçä-âî Òðèóìô, 2002. — 816 ñ. 2. Çàùèòà èíôîðìàöèè. Ìàëûé òåìàòè÷åñêèé âûïóñê // ÒÈÈÝÐ. — 1988. —76, ¹ 5. — Ñ. 24—94. Ïîñòóïèëà 21.05.13 ÂÈÍÍÈ×ÓÊ Ñòåïàí Äìèòðèåâè÷, ä-ð òåõí. íàóê, âåä. íàó÷. ñîòð. Èí-òà ïðîáëåì ìîäåëè- ðîâàíèÿ â ýíåðãåòèêå èì. Ã.Å. Ïóõîâà ÍÀÍ Óêðàèíû. Â 1977 ã. îêîí÷èë ×åðíîâèöêèé ãîñóíèâåð- ñèòåò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ðàçðàáîòêà ìåòîäîâ, ìîäåëåé è ïðîãðàììíûõ ñðåäñòâ äëÿ àíàëèçà ðàñïðåäåëèòåëüíûõ ñèñòåì ñæèìàåìîé è íåñæèìàåìîé æèäêîñòåé, àâèàöèîííûå ñèñòåìû êîíäèöèîíèðîâàíèÿ âîçäóõà; ïðîòèâîàâàðèéíàÿ ÷àñòîòíàÿ àâòîìà- òèêà ýëåêòðîýíåðãåòè÷åñêèõ ñèñòåì. Ñ.Ä. Âèííè÷óê 22 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3

Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами

Репозитарії

Схожі ресурси