Анализ класса семейств легко вычислимых перестановок

В работе изучены свойства класса семейств легко вычислимых перестановок, определенных в терминах конечного кольца. Актуальность задачи обусловлена возможностью применения этих классов перестановок при построении высокоскоростных вычислительно стойких поточных шифров....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2008
Автори:	Скобелев, В.Г., Зайцева, Э.Е.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2008
Назва видання:	Кибернетика и системный анализ
Теми:	Кибернетика
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/44249
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Анализ класса семейств легко вычислимых перестановок / В.Г. Скобелев, Э.Е. Зайцева // Кибернетика и системный анализ. — 2008. — № 5. — С.12-24 . — Бібліогр.: 14 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-44249
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-442492025-02-23T18:53:46Z Анализ класса семейств легко вычислимых перестановок Скобелев, В.Г. Зайцева, Э.Е. Кибернетика В работе изучены свойства класса семейств легко вычислимых перестановок, определенных в терминах конечного кольца. Актуальность задачи обусловлена возможностью применения этих классов перестановок при построении высокоскоростных вычислительно стойких поточных шифров. 2008 Article Анализ класса семейств легко вычислимых перестановок / В.Г. Скобелев, Э.Е. Зайцева // Кибернетика и системный анализ. — 2008. — № 5. — С.12-24 . — Бібліогр.: 14 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44249 681.3 + 519.21 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Кибернетика Кибернетика
spellingShingle	Кибернетика Кибернетика Скобелев, В.Г. Зайцева, Э.Е. Анализ класса семейств легко вычислимых перестановок Кибернетика и системный анализ
description	В работе изучены свойства класса семейств легко вычислимых перестановок, определенных в терминах конечного кольца. Актуальность задачи обусловлена возможностью применения этих классов перестановок при построении высокоскоростных вычислительно стойких поточных шифров.
format	Article
author	Скобелев, В.Г. Зайцева, Э.Е.
author_facet	Скобелев, В.Г. Зайцева, Э.Е.
author_sort	Скобелев, В.Г.
title	Анализ класса семейств легко вычислимых перестановок
title_short	Анализ класса семейств легко вычислимых перестановок
title_full	Анализ класса семейств легко вычислимых перестановок
title_fullStr	Анализ класса семейств легко вычислимых перестановок
title_full_unstemmed	Анализ класса семейств легко вычислимых перестановок
title_sort	анализ класса семейств легко вычислимых перестановок
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2008
topic_facet	Кибернетика
url	https://nasplib.isofts.kiev.ua/handle/123456789/44249
citation_txt	Анализ класса семейств легко вычислимых перестановок / В.Г. Скобелев, Э.Е. Зайцева // Кибернетика и системный анализ. — 2008. — № 5. — С.12-24 . — Бібліогр.: 14 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT skobelevvg analizklassasemejstvlegkovyčislimyhperestanovok AT zajcevaée analizklassasemejstvlegkovyčislimyhperestanovok
first_indexed	2025-11-24T13:31:52Z
last_indexed	2025-11-24T13:31:52Z
_version_	1849678745282019328
fulltext	ÓÄÊ 681.3 + 519.21 Â.Ã. ÑÊÎÁÅËÅÂ, Ý.Å. ÇÀÉÖÅÂÀ ÀÍÀËÈÇ ÊËÀÑÑÀ ÑÅÌÅÉÑÒÂ ËÅÃÊÎ ÂÛ×ÈÑËÈÌÛÕ ÏÅÐÅÑÒÀÍÎÂÎÊ Êëþ÷åâûå ñëîâà: ïîòî÷íûå øèôðû, ôðàêòàëû, êîíå÷íûå êîëüöà, ëåãêî âû÷èñ- ëèìûå ïåðåñòàíîâêè. ÂÂÅÄÅÍÈÅ Â ïîñëåäíåå âðåìÿ çíà÷èòåëüíîå âíèìàíèå óäåëÿåòñÿ ïðèëîæåíèþ õàîòè÷åñêèõ äèíàìè÷åñêèõ ñèñòåì ê ðåøåíèþ çàäà÷ çàùèòû èíôîðìàöèè [1], â ÷àñòíîñòè ïðè ïîñòðîåíèè ïîòî÷íûõ øèôðîâ [2]. Îáùàÿ ñõåìà íåñòàöèîíàðíîãî ïîòî÷íîãî øèôðà ïðåäñòàâëåíà íà ðèñ. 1. Ïðåäïîëàãàåòñÿ, ÷òî çàäàí ãåíåðàòîð ÷èñåë, ïðèíàäëåæà- ùèõ ìíîæåñòâó N m , è êëàññ àëãîðèòìîâ A � �{ }Ai i mN , ïðåäñòàâëåííûõ â íåÿâíîì âèäå. Ïðè ãåíåðàöèè ÷èñëà i m�N øèôðîâàíèå î÷åðåäíîãî ôðàãìåíòà èñõîäíîãî òåêñòà îñóùåñòâëÿåòñÿ àëãîðèòìîì Ai . Âàæíîé õàðàêòåðèñòè- êîé øèðîêîãî êëàññà õàîòè- ÷åñêèõ íåëèíåéíûõ äèíàìè- ÷åñêèõ ñèñòåì ÿâëÿåòñÿ íàëè- ÷èå ñòðàííûõ àòòðàêòîðîâ. Ê íèì îòíîñÿòñÿ è ôðàêòàëû, ò.å. îòîáðàæåíèÿ, ïîðîæäàþ- ùèå íåðåãóëÿðíûå ñàìîïî- äîáíûå ñòðóêòóðû [3–5]. Â [6] ïðåäëîæåíà ñëåäóþùàÿ ñõåìà ïîòî÷íîãî øèôðà, îñíîâàííîãî íà ïðèìåíåíèè ôðàêòàëüíûõ îòîáðàæåíèé. Ñîîáùåíèå (èëè èçîáðàæå- íèå) ïðåäñòàâëÿåòñÿ bmp-ôàéëîì, êîòîðûé ïîñëåäîâàòåëüíî îáðàáàòûâàåòñÿ ïèêñåë çà ïèêñåëîì. Ïðè îáðàáîòêå êàæäîãî ïèêñåëà ðåàëèçóåòñÿ èòåðàöèîííûé ïðîöåññ, îïðåäåëÿåìûé ïðèìåíÿåìûì ôðàêòàëüíûì îòîáðàæåíèåì. Ïðè âûïîëíåíèè (ëèáî íàðóøåíèè) íåêîòîðîãî çàäàííîãî óñëîâèÿ îñóùåñòâëÿåòñÿ îïðåäåëÿåìàÿ íîìåðîì ïîñëåäíåé èòåðàöèè ïåðåñòàíîâêà íà ìíîæåñòâå öâåòîâ. Îáðàáîòàííûé ôàéë è ïðåä- ñòàâëÿåò ñîáîé øèôðòåêñò. Êîððåêòíîñòü óêàçàííîãî ïîäõîäà âûòåêàåò èç îáðàòè- ìîñòè ïåðåñòàíîâîê. Ïðåäëîæåííàÿ ñõåìà ðåàëèçîâàíà äëÿ îäíîãî èç íàèáîëåå èçó- ÷åííûõ ôðàêòàëüíûõ îòîáðàæåíèé — îòîáðàæåíèÿ Ìàíäåëüáðîòà [5], ò.å. îòîáðà- æåíèÿ f : C C� (C — ìíîæåñòâî êîìïëåêñíûõ ÷èñåë), îïðåäåëÿåìîãî ðàâåíñòâîì f z z c( ) � �2 (c — êîíñòàíòà) (ðèñ. 2: à — êîìïëåêñíàÿ ïëîñêîñòü; á — èçîáðàæåíèå íà äèñïëåå). Ïàðàìåòðû øèôðà, îïðåäåëÿþùèå ÷èñëî èòåðàöèé, — ýòî ðàäèóñ R êðóãà ( , )R O è âåðõíÿÿ ãðàíèöà ÷èñëà K èòåðàöèé, ïðèìåíÿåìûõ ê òî÷êå êîìïëåêñíîé ïëîñêîñòè C . Óñëîâèå ñîñòîèò â âûõîäå îáðàçà çà êðóã ( , )R O â òå÷åíèå K èòåðàöèé. Êëàññ ñåìåéñòâ ïåðåñòàíîâîê îïðåäåëåí ðàâåíñòâàìè: f n n n n n n r r n a a a g g: ( \| \| ) (mod ), ( � � � � � � � � � 0 1 1 2 2 3 3 0 256� � � � � � � � � � � � � � n a a a b b n a n n n n n \| \| ) (mod ) ( \| � � � � 2 2 1 1 3 3 0 3 3 256 � � � � � � � � � � 1 1 2 2 8 256 1 2 1 n na a n \| ) (mod ). ( , , )� , (1) 12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 ÃÅÍÅÐÀÒÎÐ Ìíîæåñòâî àëãîðèòìîâ, ïðåäñòàâëåííûõ â íåÿâíîì âèäå A1 A2 Ai Am Ïîòîê øèôðòåêñòà Ïîòîê îòêðûòîãî òåêñòà Îêíî øèôðîâàíèÿ Ðèñ. 1 © Â.Ã. Ñêîáåëåâ, Ý.Å. Çàéöåâà, 2008 Çäåñü r g b0 0 0, , è r g bn n n, , — ñîîòâåòñòâåííî èñõîäíûå è ïðåîáðàçîâàííûå êîìïîíåíòû öâåòà ïèêñåëà, à � i ia, �Z ( , , )i �1 2 3 — ïàðàìåòðû, èãðàþùèå ðîëü ñåêðåòíîãî êëþ÷à. Ðàññìîòðåííàÿ ñõåìà — ñïåöèàëüíûé ñëó÷àé íåñòàöèîíàðíîãî ïîòî÷íîãî øèôðà, äëÿ êîòîðîãî óïðàâëåíèå âûáîðîì àëãîðèòìà Ai mi( )� N îñó- ùåñòâëÿåòñÿ íà îñíîâå äèíàìè÷åñêèõ ôðàêòàëüíûõ îòîáðàæåíèé. Ïðè ïîñòðîåíèè ñîâðåìåííûõ ñòàíäàðòîâ øèôðîâàíèÿ [7–10] íàáëþäàåòñÿ óñòîé÷èâàÿ òåíäåíöèÿ ê ïðèìåíåíèþ êîíå÷íûõ àëãåáðàè÷åñêèõ ñèñòåì. Ïîýòîìó åñòåñòâåííî ïåðåéòè ê ïåðåñòàíîâêàì, îïðåäåëåííûì â òåðìèíàõ êîíå÷íîãî êîëüöà Z p pk k� �( , , )Z � [7, 11] ( p — ïðîñòîå ÷èñëî, k �N, à îïåðàöèè � è � îïðåäåëåíû ðàâåíñòâàìè a b a b pk� � � (mod ) è a b a b pk � � � (mod ) äëÿ âñåõ a b pk, �Z ). Òà- êèì àíàëîãîì äëÿ (1) ÿâëÿåòñÿ êëàññ ñåìåéñòâ ïåðåñòàíîâîê x x n a an j l j n j l n( ) ( )1 0 1 1 12� � � � � � � � �� O O� � � � �� x x n a an l l j l j n j l n l ( ) ( )� � � � � � � � �0 1 2O O� � � � � � �( , , )n pk1 1� , (2) ãäå x Zt t t l p x x k� �( , , )( ) ( )1 � T ( , , , )t pk� �0 1 1� . Àâòîðàìè áûë ðåàëèçîâàí ïîòî÷íûé øèôð, â êîòîðîì óïðàâëåíèå êëàññîì ïåðåñòàíîâîê (2) â ñëó÷àå, êîãäà p � 2, k � 8 è l � 3, îñóùåñòâëÿåòñÿ îòîáðàæåíèåì Ìàíäåëüáðîòà. Àëãîðèòì ðåàëè- çîâàí â ñðåäå Microsoft Visual C++ ñ èñïîëüçîâà- íèåì MFC App Wizard. Â êà÷åñòâå ïðèìåðîâ ðà- áîòû ïðîãðàììû ïðèâå- äåì ðåçóëüòàòû øèôðîâà- íèÿ òåêñòà è èçîáðàæåíèÿ. Òåêñòîâîìó ôàéëó îáúå- ìîì 64 Êáàéò ñîîòâåòñòâó- åò bmp-ôàéë, èçîáðàæåí- íûé íà ðèñ. 3, à. Çàøèô- ðîâàííûé bmp-ôàéë òîãî æå ðàçìåðà (ðèñ. 3, á) ïå- ðåâîäèòñÿ â øèôðòåêñò. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 13 Ðèñ. 2 à á Òî÷êà êîìïëåêñíîé ïëîñêîñòè Ñîîòâåòñòâóþùèå äðóã äðóãó òî÷êè êîìïëåêñíîé ïëîñêîñòè è èñõîäíîãî òåêñòà Ïðåîáðàçîâàíèå òî÷êè, ñîîòâåòñòâóþùåå íîìåðó ïîñëåäíåé âûïîëíåííîé èòåðàöèè Ðèñ. 3 àá Ãèñòîãðàììû ðàñïðåäåëåíèÿ ÷àñòîò áóêâ â èñõîäíîì (a) è çàøèôðîâàííîì (á) òåê- ñòîâûõ ôàéëàõ ïðåäñòàâëåíû íà ðèñ. 4. Íà ðèñ. 5 ïðèâåäåí ïðèìåð øèôðîâàíèÿ èçîáðàæåíèÿ: à — èñõîäíîå; á — çàøèôðîâàííîå. Ïåðñïåêòèâíîñòü è ýôôåêòèâíîñòü ïðåäëîæåííîãî ïîäõîäà îáîñíîâûâàåò àê- òóàëüíîñòü èññëåäîâàíèÿ êëàññîâ ñåìåéñòâ ëåãêî âû÷èñëèìûõ ïåðåñòàíîâîê, îïðå- äåëåííûõ â òåðìèíàõ êîëüöà Z pk . Öåëü íàñòîÿùåé ðàáîòû — èññëåäîâàíèå êëàññà ñåìåéñòâ ëåãêî âû÷èñëèìûõ ïåðåñòàíîâîê, ÿâëÿþùèõñÿ åñòåñòâåííûì îáîáùåíèåì êëàññà (2). Ñòðóêòóðà ðàáî- òû ñëåäóþùàÿ: ðàçä. 1 ñîäåðæèò îñíîâíûå îïðåäåëåíèÿ; â ðàçä. 2 îõàðàêòåðèçîâàíà ñòðóêòóðà èññëåäóåìîãî êëàññà ñåìåéñòâ ëåãêî âû÷èñëèìûõ ïåðåñòàíîâîê, îïðå- äåëåííûõ â òåðìèíàõ êîëüöà Z pk ; â ðàçä. 3 èññëåäîâàíà ñëîæíîñòü èäåíòèôèêàöèè ñåìåéñòâà ïåðåñòàíîâîê, ïðèíàäëåæàùèõ ðàññìàòðèâàåìîìó êëàññó. Çàêëþ÷åíèå ñîäåðæèò ðÿä âûâîäîâ. 1. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß Ïóñòü S — êîíå÷íîå ìíîæåñòâî, à PS — ìíîæåñòâî âñåõ ïåðåñòàíîâîê ìíî- æåñòâà S . Åñëè S S l i l i� � � �1 1( ), ãäå \| \|S i �1 ( )i l�N è f � ( , , )f fl1 � , ãäå fi S i �P ( )i l�N , ïðè÷åì f ( ) ( ( ), , ( ))s � f s f sl l1 1 � äëÿ âñåõ s � �( , , )s s Sl1 � , òî ïåðåñòà- íîâêó f �PS íàçîâåì l-ðàçëîæèìîé. Îáîçíà÷èì P S l s� ìíîæåñòâî âñåõ l-ðàçëîæè- ìûõ ïåðåñòàíîâîê ìíîæåñòâà S . Ñëåäóÿ [12], áóäåì ñ÷èòàòü, ÷òî îáúåì ïàìÿòè �S , íåîáõîäèìîé äëÿ õðàíåíèÿ ëþáîãî ýëåìåíòà ìíîæåñòâà S , ðàâåí O S(log \| \| ) (\| \| )S � � . Ïåðåñòàíîâêó f S�P íàçîâåì ëåãêî âû÷èñëèìîé, åñëè äëÿ ëþáîãî 14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 Ðèñ. 5 à á Ðèñ. 4 0 0,02 1 25319 37 55 73 91 109 235217199163145127 181 0,04 0,06 0,08 0,1 0,12 0,14 0,16 0 0,002 1 25319 37 55 73 91 109 235217199163145127 181 0,004 0,006 0,008 0,01 0,012 à á ýëåìåíòà s S� àñèìïòîòè÷åñêàÿ åìêîñòíàÿ è âðåìåíí�ÿ ñëîæíîñòü àëãîðèòìà A j , ðåàëèçóþùåãî ïåðåñòàíîâêó f , ñîîòâåòñòâåííî ðàâíà V O Sf � (log \| \| ) (\| \| )S � � è T O Sf � (log \| \| )2 (\| \| )S � � . Ïóñòü P S ec — ìíîæåñòâî âñåõ ëåãêî âû÷èñëèìûõ ïåðåñòàíîâîê f S�P . Óòâåðæäåíèå 1. Ïóñòü S S l i l i� � � �1 1( ), ãäå \| \| ( )S ii l� �1 N è f ii S ec l i � �P ( )N . Òîãäà f � �( , , )f fl S ec 1 � P . Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî fi S ec i �P äëÿ âñåõ i l�N . Àñèìïòîòè÷åñ- êàÿ âðåìåíí�ÿ è åìêîñòíàÿ ñëîæíîñòü âû÷èñëåíèÿ îáðàçà ëþáîãî ýëåìåíòà s Si i� (i l�N ) ðàâíà ñîîòâåòñòâåííî T O Sf ii � (log \| \| )2 è V O Sf ii � (log \| \| ). Òàê êàê âû÷èñ- ëåíèå f ( )s ( ( , , ) )s � �s s Sl1 � ìîæíî ñâåñòè ê íåçàâèñèìûì âû÷èñëåíèÿì f si i( ) ( )i l�N , òî T T O S O S i l f i i l i i l if � � � � � � � � � � �� 1 2 1 1 log \| \| log \| \|� � � � � � � � � � � � � � � � � � 2 2O S S(log \| \| ) (\| \| ) , ÷òî è òðåáîâàëîñü ïîêàçàòü. Ïîñêîëüêó s � ( , , )s sl1 � è V O Sf ii � (log \| \| ) (i l�N ), òî V O V O S O Sf i l i l iif � � � � � � � � � � � � � � � � � � � � � 1 1 log \| \| (log \| \| ) (\| \| )S � � . Óòâåðæäåíèå äîêàçàíî. Ñåìåéñòâî ëåãêî âû÷èñëèìûõ ïåðåñòàíîâîê S � �{ }f j j N ( )f j S ec�P íàçîâåì ëåãêî âû÷èñëèìûì, åñëè ñóùåñòâóåò òàêîé àëãîðèòì ïîñëåäîâàòåëüíîé ãåíåðàöèè ýëåìåíòîâ ñåìåéñòâà S , ÷òî: 1) ãåíåðàöèÿ àëãîðèòìà A f1 îñóùåñòâëÿåòñÿ çà âðåìÿ T O S� (log \| \| ) (\| \| )S � � ; 2) ïðåîáðàçîâàíèå àëãîðèòìà A f j ( )j �N â àëãîðèòì A f j� 1 îñóùåñòâëÿåòñÿ çà âðåìÿ O S(log \| \| )2 (\| \| )S � � . Ïóñòü Z p inv k — ìíîæåñòâî âñåõ îáðàòèìûõ ýëåìåíòîâ êîëüöà Z pk , ò.å. (Z p inv k , )� — ìóëüòèïëèêàòèâíàÿ ãðóïïà êîëüöà Z pk . Îòìåòèì, ÷òî êðèòåðèé ïðèíàäëåæíîñòè ýëåìåí- òà a pk�Z ìíîæåñòâó Z p inv k èìååò âèä a a p p inv k� � ��Z 0 (mod ) (ñì., íàïðèìåð, [13]). Ïóñòü l ( )2 � �l k — òàêîå ôèêñèðîâàííîå ÷èñëî, ÷òî ( ) (mod )l pk p inv k� �2 Z . Çàôèêñèðóåì ýëåìåíòû � �i i i p inva k , , �Z ( )i l�N êîëüöà Z pk . Ïîëîæèì A ni ( ) � � � �j l j j n i i na a 1 2� � �� O ( , )i nl� �N N . Îïðåäåëèì îäíîïàðàìåòðè÷åñêèå ñåìåéñòâà àôôèííûõ îòîáðàæåíèé S ( ) ( ){ : \| }i n i p p f nk k� � �Z Z N ( )i l�N ðàâåíñòâîì f x x n p A n x nn i i n k i pk ( ) ( ) (mod ) ( ) ( , )� � � �� Z N . (3) Òàê êàê � i p inv k�Z ( )i l�N , òî fn i pk ( ) �PZ ( , )i nl� �N N . Ãåíåðàöèÿ àëãîðèòìà A f i 1 ( ) ( )i l�N îñóùåñòâëÿåòñÿ çà âðåìÿ � �T O k p f i 1 ( ) ( log )� � , à âðåìåíí�ÿ è åìêîñò- íàÿ ñëîæíîñòü àëãîðèòìà A f i 1 ( ) ( )i l�N ðàâíà ñîîòâåòñòâåííî � �T O k p f i 1 2 ( ) (( log ) )� � è � �V O k p f i 1 ( ) ( log )� � . Ïðè âû÷èñëåííûõ çíà÷åíèÿõ � �i n i n, ( )i l�N ïðåîáðàçîâà- íèå àëãîðèòìà A fn i( ) â àëãîðèòì A f n i � 1 ( ) ( )i �N îñóùåñòâëÿåòñÿ çà âðåìÿ T f n i � � 1 ( ) � �� O k p(( log ) )2 , à âðåìåíí�ÿ è åìêîñòíàÿ ñëîæíîñòü àëãîðèòìà A f n i � 1 ( ) ( )i l�N ðàâ- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 15 íà ñîîòâåòñòâåííî � �T O k p f n i � � � 1 2 ( ) (( log ) ) è � �V O k p f n i � � � 1 ( ) ( log ). Ñëåäîâàòåëüíî, êàæäîå ñåìåéñòâî ïåðåñòàíîâîê S ( )i ( )i l�N ëåãêî âû÷èñëèìîå. Çàôèêñèðóåì ïåðåñòàíîâêó h l �PN . Îïðåäåëèì ñåìåéñòâî S( , , , )� � a h îòîáðà- æåíèé f Z Zn p l p l k k: � ( )n �N ñëåäóþùèì îáðàçîì: äëÿ âñåõ x Z� �( , , )x xl p l k1 � T f xn n h n l h l f x f xn n( ) ( ( ), , ( ))( ) ( ) ( ) ( ) � 1 1 � T . ßñíî, ÷òî f Z Zn l s ec pk l pk l � �� P P ( )n �N . Ïðåäìåòîì èññëåäîâàíèÿ è ÿâëÿåòñÿ êëàññ K òàêèõ ( )3 1� �l -ïàðàìåòðè÷åñêèõ ñåìåéñòâ ïåðåñòàíîâîê S( , , , )� � a h , ÷òî h l �PN , � � �( , , ) ( )� �1 � l p inv l kZ , � � � �( , , ) ( )� �1 � l p inv l kZ è a Z� �( , , ) ( )a al p inv l k1 � . Òàê êàê l l k( )2 � � — ôèêñèðî- âàííîå ÷èñëî, òî èç óòâåðæäåíèÿ 1 âûòåêàåò, ÷òî K — ëåãêî âû÷èñëèìûé êëàññ ñå- ìåéñòâ ïåðåñòàíîâîê. Ñõåìíàÿ ðåàëèçàöèÿ êëàññà K ïðåäñòàâëåíà íà ðèñ. 6. 16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 )1( 1x )( 1 l x )1( nx )(l nx )(lhn )1(nh Ïåðåñòàíîâêà êîìïîíåíò âåêòîðà nx Ïåðåñòàíîâêà h Çàäåðæêà �1 �2 �l Çàäåðæêà n 1� n 2� n l� )1( 1 nh n n x�� )(lh n n l n x�� a1 al �1 �2 �l Çàäåðæêà n 1� n 2� n l� na 11 �� Íàâåøèâàíèå áåãóùåé «�1» Ñóììàòîð A1(n) A2(n) Al (n) n A1(n) n A2(n) n Al (n) n (mod p k ) n1 Èíèöèàëèçàöèÿ n � 1 Çàäåðæêà n lla �� Èíèöèàëèçàöèÿ Ðèñ. 6 2. ÑÒÐÓÊÒÓÐÀ ÊËÀÑÑÀ K Îòìåòèì ñëåäóþùèå ñâîéñòâà ïåðåñòàíîâîê fn i ec pk ( ) �P Z ( , )i nl� �N N , îïðåäå- ëåííûõ ðàâåíñòâîì (3). Óòâåðæäåíèå 2. Ïóñòü � � �1 � � � �� l p inv kZ è a a al p inv k1 � � � �� Z . Â ýòîì ñëó÷àå: 1) f f i j i j i n n j l ( ) ( ) ( , , )� � !N òîãäà è òîëüêî òîãäà, êîãäà � �i n j n� ; 2) äëÿ êàæäîãî çíà÷åíèÿ n �N ìíîæåñòâî íåïîäâèæíûõ òî÷åê ïåðåñòàíîâêè fn i( ) ( )i l�N ñîâïàäàåò ñî ìíîæåñòâîì ðåøåíèé óðàâíåíèÿ ( ) (mod ) ( )1 2O � �i n k nx n p l a� � � �� . (4) Äîêàçàòåëüñòâî. Ïóñòü � � �1 � � � �� l p inv kZ è a a al p inv k1 � � � �� Z . Òîãäà ðàâåíñòâà (3) ïðèíèìàþò âèä f x x n p l a in i i n k n l ( ) ( ) (mod ) ( ) ( )� � � �� 2 N . (5) Ñëåäîâàòåëüíî, f f x f x f xn i n j p n i n j k ( ) ( ) ( ) ( )( ) ( ( ) ( ))� � " � � �Z � " � � � �( ) (( ) )x x p i n j n i n j n kZ � � � �O � 0 , ÷òî è òðåáîâàëîñü ïîêàçàòü. Ïóñòü x pk�Z — íåïîäâèæíàÿ òî÷êà ïåðåñòàíîâêè fn i( ) ( )i l�N . Ïîëîæèì f x xn i( ) ( ) � â ðàâåíñòâå (5). Ïîëó÷èì (4), ÷òî è òðåáîâàëîñü ïîêàçàòü. Óòâåðæäåíèå äîêàçàíî. Ñëåäñòâèå 1. Ïóñòü � � �1 � � � �� l p inv kZ , a a al p inv k1 � � � �� Z , 1 0O � i n ! , n pk(mod ) ! 0 è r r1 2, — òàêèå ìàêñèìàëüíûå íàòóðàëüíûå ÷èñëà, ÷òî 1O � i n � � 0 1(mod )p r è n p l pk r (mod ) ( ) (mod )� � �2 0 2 . Åñëè r r1 2� , òî ïåðåñòàíîâêà fn i( ) íå èìååò íåïîäâèæíûõ òî÷åê. Èñòèííîñòü ñëåäñòâèÿ 1 âûòåêàåò èç òîãî, ÷òî ïðè ñäåëàííûõ ïðåäïîëîæåíèÿõ óðàâíåíèå (4) íå èìååò ðåøåíèé. Ïóñòü � — ôóíêöèÿ Ýéëåðà. Òàê êàê �( )p p pk k k� � �1, òî ïîêàçàòåëÿìè (ïî ìî- äóëþ pk ) ýëåìåíòîâ ìíîæåñòâà Z p inv k ìîãóò áûòü òîëüêî ÷èñëà p �1, pi è ( )p pi� �1 ( )i k� �N 1 . Óòâåðæäåíèå 3. Åñëè a a al p inv k1 � � � �� Z , òî ïåðåñòàíîâêà f p i k�( ) ( ) ( )i l�N èìååò íåïîäâèæíûå òî÷êè òîãäà è òîëüêî òîãäà, êîãäà l p� �2 0(mod ). Äîêàçàòåëüñòâî. Ïîëîæèì a a al p inv k1 � � � �� Z è n pk� �( ) â (3). Ïîëó÷èì f x x p l a p i k k�( ) ( ) ( ) ( )� ��O 1 2� � . (6) Ïîëîæèì f x x p i k�( ) ( ) ( ) � â (6). Ïîëó÷èì p l ak� � �1 2 0� �( ) . Ïîñëåäíåå ðàâåíñòâî èñòèííî òîãäà è òîëüêî òîãäà, êîãäà l p� �2 0(mod ). Óòâåðæäåíèå äîêàçàíî. Îáîçíà÷èì ÷åðåç � i è � i ( )i l�N ïîêàçàòåëè (ïî ìîäóëþ pk ) ýëåìåíòîâ � i è � i ñîîòâåòñòâåííî. Ïîëîæèì [ , , ]� � �1 � l � è � � 1, , ]� l � è [ , ]� �� . Èç (3) âûòåêàåò, ÷òî äëÿ âñåõ i l�N f x x m p A m m m i k i� � � � � � � � �( ) ( ) (mod ) )( ) ( ) (� N , (7) ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 17 f x x m p a a m i i m k j l j i� � � � � � � � � � � � � ( ) ( ) (mod )� � �( ) O 1 2 � � �(m N ), (8) f x x m p a a mm i k j l j i� � � � � � � � � � � � � �� ( ) ( ) (mod )( ) O (� � 1 2 N ) . (9) Èç (7)–(9) âûòåêàåò, ÷òî: 1) ïåðåñòàíîâêà f m i � � ( ) ( )i l�N íå èìååò íåïîäâèæíûõ òî÷åê òîãäà è òîëüêî òîãäà, êîãäà ( )(mod ) ( )m p A mk i� � !� �� 0; 2) ïåðåñòàíîâêà f m i � � ( ) ( )i l�N òîæäåñòâåííàÿ òîãäà è òîëüêî òîãäà, êîãäà ( )(mod ) ( )m p A mk i� � �� 0; 3) åñëè � � �j l j ia a 1 2 0O � ( )i l�N , òî ìíîæåñòâî íåïîäâèæíûõ òî÷åê ïåðåñòàíîâêè f m i � ( ) ñîâïàäàåò ño ìíîæåñòâîì ðåøåíèé óðàâíåíèÿ ( )� i m x � �O1 0� ; 4) åñëè � � �j l j ia a 1 2 0O � , òî fm i � � ( ) ( )i l�N — òîæäåñòâåííàÿ ïåðåñòàíîâêà. Ïðåäñòàâèì ñåìåéñòâî ïåðåñòàíîâîê S K( , , , )� � a h � â ÿâíîì âèäå: x x n p A n n n n h kn � � � 1 1 1 1 1 ( ) ( ) (mod ) ( ),� � � �� x x n p A n n l l n n h l k l n � � � � � 1 ( ) ( ) (mod ) ( ),� (10) ãäå A n a ai j l j j n i i n( ) � � �1 2� � �� O ( , )i nl� �N N , � �i i i p inv a k, , �Z ( )i l�N è h l �PN . Äëÿ ëþáûõ ôèêñèðîâàííûõ ÷èñåë n n0 1, �N ( )n n1 0# ïîëîæèì Sn n n nh n n0 1 1 0 1, \( , , , ) { }� � a f N N� � � . Îáðàçîì ýëåìåíòà x Z 0 0 1 0 � �( , , )( ) ( )x x l p l k� T ïðè äåéñòâèè ñåìåéñòâà Sn n h 0 1, ( , , , )� � a íàçîâåì ïîñëåäîâàòåëüíîñòü Sn n n nh 0 1 1 01 1, ( , , , )( )� � a x x x� � �� , ãäå x f x i i i l n i ix x� � � � �( , , ) ( )( ) ( )1 1 10 � T ( )i n n� � �N 1 0 1 . Áóäåì ãîâîðèòü, ÷òî x Z 0 � p l k — íåïîäâèæíàÿ òî÷êà äëÿ ñåìåéñòâà Sn n h 0 1, ( , , , )� � a òîãäà è òîëüêî òîãäà, êîãäà x xi � 0 äëÿ âñåõ i n n� � �N 1 0 1. Òåîðåìà 1. Ïóñòü p — íå÷åòíîå ïðîñòîå ÷èñëî. Òîãäà äëÿ âñåõ S K( , , , )� � a h � ïîèñê ñåìåéñòâà Sn n h 0 1, ( , , , )� � a ( )n n� 0 , îáëàäàþùåãî çàäàííîé íåïîäâèæíîé òî÷êîé x Z 0 � p l k , ïðè óñëîâèè, ÷òî n n0 1, �N íå ÿâëÿþòñÿ ïîêàçàòåëÿìè (ïî ìîäó- ëþ pk ) íè îäíîãî èç ÷èñåë � �i i p inv k, �N ( )i l�N , ñâîäèòñÿ ê ðåøåíèþ ñèñòåìû ìíî- ãîñòåïåííûõ äèîôàíòîâûõ óðàâíåíèé ñ 2� l íåèçâåñòíûìè ñ ïîñëåäóþùåé ïðîâåðêîé äëÿ êàæäîãî åå ðåøåíèÿ ðàçðåøèìîñòè 2� l çàäà÷ äèñêðåòíîãî ëîãàðèôìèðîâàíèÿ. Äîêàçàòåëüñòâî. Ïóñòü x Z 0 � p l k — íåïîäâèæíàÿ òî÷êà äëÿ ñåìåéñòâà Sn n h 0 1, ( , , , )� � a . Òîãäà f x xn i i0 1 1 0� � � �( ) äëÿ âñåõ i n n� � �N 1 0 1. Èç (10) ïîëó÷èì, ÷òî äëÿ âñåõ i n n� � �N 1 0 1 ( )(mod ) ( ) ( )n i p A n i x xk j j n i h j n i 0 0 1 0 1 1 0 0 1 � � � � � � � � � � � �� 0 ( ) ( )j lj �N . (11) 18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 Ïîëîæèâ â (11) u jj j n l� �� 0 ( )N , (12) � �j j n lj� �0 ( )N , (13) ïîëó÷èì ñèñòåìó ìíîãîñòåïåííûõ äèîôàíòîâûõ óðàâíåíèé ñ 2� l íåèçâåñòíûìè u j , � j ( )j l�N . Êàæäîå ðåøåíèå ýòîé ñèñòåìû äèîôàíòîâûõ óðàâíåíèé ïðèâî- äèò ê 2� l çàäà÷àì äèñêðåòíîãî ëîãàðèôìèðîâàíèÿ, îïðåäåëÿåìûì (12) è (13). Ðå- øåíèå ýòîé ñèñòåìû çàäà÷ äèñêðåòíîãî ëîãàðèôìèðîâàíèÿ è îïðåäåëÿåò èñêîìîå ñåìåéñòâî Sn n h 0 1, ( , , , )� � a . Òåîðåìà äîêàçàíà. Îòìåòèì, ÷òî âêëþ÷åíèå ïåðåñòàíîâêè h l �PN â ÷èñëî ïàðàìåòðîâ, îïðåäåëÿ- þùèõ ñåìåéñòâî ïåðåñòàíîâîê Sn n h 0 1, ( , , , )� � a , öåëåñîîáðàçíî ïî ñëåäóþùèì ïðè- ÷èíàì. Âî-ïåðâûõ, ïðèìåíåíèå êîíñòðóêöèè, ïðåäëîæåííîé â [14], äàåò âîçìîæ- íîñòü ñèñòåìàòè÷åñêè ñòðîèòü ïåðåñòàíîâêè h l �PN ïîðÿäêà eO l( ) ( )l � � , ÷òî ïðèâîäèò ê ñóùåñòâåííîìó ðîñòó ïîðÿäêà ïåðåñòàíîâîê f n ( )n �N , ôîðìèðóþùèõ ñåìåéñòâî Sn n h 0 1, ( , , , )� � a . Âî-âòîðûõ, ñóùåñòâåííî óñëîæíÿåòñÿ ñèñòåìà ìíî- ãîñòåïåííûõ äèîôàíòîâûõ óðàâíåíèé, êîíñòðóèðóåìûõ ïðè äîêàçàòåëüñòâå òåîðå- ìû 1. Â-òðåòüèõ, ðàçðóøàåòñÿ ðåãóëÿðíîñòü ïðåäñòàâëåíèÿ ìíîæåñòâà íåïîäâèæ- íûõ òî÷åê ñåìåéñòâà Sn n h 0 1, ( , , , )� � a ( )n n0 1� . Ñëåäóþùàÿ òåîðåìà ïîêàçûâàåò, ÷òî äëÿ êîëüöà Z 2k ìîæíî âûäåëèòü äîñòà- òî÷íî øèðîêèé êëàññ ñåìåéñòâ Sn n h 0 1, ( , , , )� � a , íå èìåþùèõ íåïîäâèæíûõ òî÷åê. Òåîðåìà 2. Ïóñòü p � 2, � i �1 ( )i l�N , l — íå÷åòíîå ÷èñëî è k # 3 . Òîãäà äëÿ âñåõ S K( , , , )� � a e � (e l �PN — òîæäåñòâåííàÿ ïåðåñòàíîâêà) íè îäíî ñåìåéñòâî S n n e 0 1, ( , , , )� � a ( )n n k 0 1 2� � íå èìååò íåïîäâèæíûõ òî÷åê. Äîêàçàòåëüñòâî. Ïóñòü p � 2, � i �1 ( )i l�N , l — íå÷åòíîå ÷èñëî, k # 3 è e l �PN — òîæäåñòâåííàÿ ïåðåñòàíîâêà. Ïðåäïîëîæèì ïðîòèâíîå, ò.å. ÷òî ñóùåñòâóåò íåïîäâèæíàÿ òî÷êà x Z0 2 � k l äëÿ ñåìåéñòâà S n n e 0 1, ( , , , )� � a ( )n n k 0 1 2� � . Èç (10) ïîëó÷èì, ÷òî äëÿ âñåõ i n n� � �N 1 0 1 ( ) (mod ) ( ) ( )n i A n i jk j l0 01 2 1 0� � � � � �� N . Òàê êàê ai i inv k, � �Z 2 ( )i l�N , òî ai i, � ( )i l�N — íå÷åòíûå ÷èñëà, à ïîñêîëüêó l — íå÷åòíîå ÷èñëî, òî A ni ( ) ! 0 ( )i l�N äëÿ âñåõ n �N. Ñëåäîâàòåëüíî, n A ni� ( ) ! 0 ( )i l�N äëÿ âñåõ n n�N 1 . Ïîëó÷åííîå ïðîòèâîðå÷èå îçíà÷àåò, ÷òî ïðåäïîëîæåíèå ëîæíîå. Îòñþäà âûòåêàåò, ÷òî íè îäíî ñåìåéñòâî Sn n e 0 1, ( , , , )� � a ( )n n k 0 1 2� � íå èìååò íåïîäâèæíûõ òî÷åê. Òåîðåìà äîêàçàíà. 3. ÈÄÅÍÒÈÔÈÊÀÖÈß ÑÅÌÅÉÑÒÂÀ Sn n h 0 1, ( , , , )� � a Ðàññìîòðèì çàäà÷è èäåíòèôèêàöèè ñåìåéñòâà ïåðåñòàíîâîê Sn n h 0 1, ( , , , )� � a ïðè óñëîâèè, ÷òî ýêñïåðèìåíòàòîðó äîñòóïíû íåêîòîðûå òî÷êè ñúåìà èíôîðìàöèè è/èëè óïðàâëåíèÿ àëãîðèòìîì, ðåàëèçóþùèì ïåðåñòàíîâêè f Nn n( )� . Òåîðåìà 3. Ïóñòü èçâåñòíû çíà÷åíèÿ âåêòîðîâ ïàðàìåòðîâ a è �. Åñëè â ìî- ìåíò n0 �N ýêñïåðèìåíòàòîð ìîæåò óïðàâëÿòü àëãîðèòìîì, ðåàëèçóþùèì ïåðå- ñòàíîâêó f n0 , è íàáëþäàòü ñîîòâåòñòâóþùèé âûõîä, òî èäåíòèôèêàöèÿ âåêòîðà ïàðàìåòðîâ � ñâîäèòñÿ ê íåçàâèñèìîìó ðåøåíèþ l çàäà÷ äèñêðåòíîãî ëîãà- ðèôìèðîâàíèÿ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 19 Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî èçâåñòíû çíà÷åíèÿ âåêòîðîâ ïàðàìåòðîâ a,� è â ìîìåíò n0 �N ýêñïåðèìåíòàòîð ìîæåò óïðàâëÿòü àëãîðèòìîì, ðåàëèçóþ- ùèì ïåðåñòàíîâêó f n0 è íàáëþäàòü ñîîòâåòñòâóþùèé âûõîä. Âûáåðåì â êà÷åñòâå âõîäà àëãîðèòìà, ðåàëèçóþùåãî ïåðåñòàíîâêó f n0 , âåêòîð xn l 0 1 1� ( , , )� �� T . Èç ñèñòåìû (10) ïîëó÷èì ñëåäóþùóþ ñèñòåìó óðàâíåíèé îòíîñè- òåëüíî íåèçâåñòíûõ � �1 , ,� l p inv k �Z : � � 1 1 1 0 1 0 0 0 n n k l n x n p A n� � ( ) (mod ) ( ),O � �� 0 0 1 0 0� � � � x n p A n n l k l ( ) (mod ) ( ).O � (14) Ðåøåíèå ñèñòåìû (14) ñâîäèòñÿ ê íåçàâèñèìîìó ðåøåíèþ l çàäà÷ äèñêðåòíîãî ëîãàðèôìèðîâàíèÿ. Òåîðåìà äîêàçàíà. Òåîðåìà 4. Ïóñòü p — íå÷åòíîå ïðîñòîå ÷èñëî è èçâåñòíû çíà÷åíèÿ âåêòîðîâ ïàðàìåòðîâ a è �. Åñëè â ìîìåíò n0 �N, ãäå n pk p inv k0 (mod )�Z , ýêñïåðèìåíòàòîð ìîæåò íàáëþäàòü âõîä è ñîîòâåòñòâóþùèé âûõîä àëãîðèòìà, ðåàëèçóþùåãî ïåðå- ñòàíîâêó f n0 , òî èäåíòèôèêàöèÿ âåêòîðà ïàðàìåòðîâ � ñâîäèòñÿ ê íåçàâèñèìîìó ðå- øåíèþ l çàäà÷ äèñêðåòíîãî ëîãàðèôìèðîâàíèÿ. Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî p — íå÷åòíîå ïðîñòîå ÷èñëî, èçâåñòíû çíà- ÷åíèÿ âåêòîðîâ ïàðàìåòðîâ a, � è â ìîìåíò n0 �N ( (mod ) )n pk p inv k0 �Z ýêñïåðè- ìåíòàòîð ìîæåò íàáëþäàòü âõîä è ñîîòâåòñòâóþùèé âûõîä àëãîðèòìà, ðåàëèçóþùå- ãî ïåðåñòàíîâêó f n0 . Èç ñèñòåìû (10) ïîëó÷èì ñëåäóþùóþ ñèñòåìó óðàâíåíèé îòíîñèòåëüíî íåèç- âåñòíûõ � �1 , ,� l p inv k�Z : � � � j l j j n n j l j j n a a a =1 =1 O� � � �� 0 02 1 1 1 , 0 02O � �al l n l� �� , (15) ãäå � �i k n i i n n h in p x x n � � � ( (mod ) ) ( )( ) ( ) 0 1 10 0 0 0 � �O ( )i l�N . Òàê êàê $ � � � �� O O O a a a a a a a a a a a p l l l l l l k 1 2 1 2 1 2 1 12 � � � � � � � �� ( 2)�Z p inv k , òî ñèñòåìà (15) ýêâèâàëåíòíà ñèñòåìå a c a c n l n l 1 1 0 0 � � � � , . �� (16) Ðåøåíèå ñèñòåìû (16) ñâîäèòñÿ ê íåçàâèñèìîìó ðåøåíèþ l çàäà÷ äèñêðåòíîãî ëîãàðèôìèðîâàíèÿ. Òåîðåìà äîêàçàíà. 20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 Ñëåäñòâèå 2. Ïóñòü p — íå÷åòíîå ïðîñòîå ÷èñëî è èçâåñòíû çíà÷åíèÿ âåêòî- ðîâ ïàðàìåòðîâ � è �. Åñëè â ìîìåíò n0 �N, ãäå n pk p inv k0 (mod )�Z , ýêñïåðèìåíòà- òîð ìîæåò íàáëþäàòü âõîä è ñîîòâåòñòâóþùèé âûõîä àëãîðèòìà, ðåàëèçóþùåãî ïå- ðåñòàíîâêó f n0 , òî èäåíòèôèêàöèÿ âåêòîðà ïàðàìåòðîâ a ñâîäèòñÿ ê ðåøåíèþ ëè- íåéíîé ñèñòåìû óðàâíåíèé. Äîêàçàòåëüñòâî. Èäåíòèôèêàöèÿ âåêòîðà ïàðàìåòðîâ a ñâîäèòñÿ ê ðåøåíèþ ëèíåéíîé ñèñòåìû óðàâíåíèé (15) îòíîñèòåëüíî íåèçâåñòíûõ a al p inv k1 , ,� �Z . Ñëåäñòâèå äîêàçàíî. Ñëåäóþùàÿ òåîðåìà ïîêàçûâàåò, ÷òî ñëîæíîñòü çàäà÷ èäåíòèôèêàöèè ñóùåñ- òâåííî âîçðàñòàåò äàæå äëÿ ñåìåéñòâà ïåðåñòàíîâîê (2) â ñëó÷àå êîëüöà Z 2k , åñëè ýòî ñåìåéñòâî âñòðîåíî â ïîòî÷íûé øèôð, ïîñòðîåííûé íà îñíîâå äèíàìè÷åñêîãî ôðàêòàëà, ýêñïåðèìåíòàòîð èìååò òîëüêî âîçìîæíîñòü àíàëèçèðîâàòü èñõîäíûé òåêñò è øèôðòåêñò, è òðåáóåòñÿ èäåíòèôèöèðîâàòü äâà èç òðåõ âåêòîðîâ � �, , a ïà- ðàìåòðîâ. Òåîðåìà 5. Ïóñòü â øèôð, ïîñòðîåííûé íà îñíîâå äèíàìè÷åñêîãî ôðàêòàëà, âñòðîåíî ñåìåéñòâî ïåðåñòàíîâîê (2) íàä êîëüöîì Z 2k ( )k # 3 , ãäå l ( )3 � �l k — íå- ÷åòíîå ÷èñëî. Òîãäà èäåíòèôèêàöèÿ âåêòîðà ïàðàìåòðîâ ( , )a � ñåìåéñòâà (2) ñâî- äèòñÿ ê ðåøåíèþ ýêñïîíåíöèàëüíîãî ÷èñëà çàäà÷ äèñêðåòíîãî ëîãàðèôìèðîâàíèÿ. Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî èçâåñòíû ñîîòâåòñòâóþùèå ïàðû ( , )x x0 n , ( )n k� � N 2 1 èñõîäíîãî òåêñòà è øèôðòåêñòà. Èç (2) âûòåêàåò, ÷òî n a a c n n j l j n j� � � � �� 2 1 1� �1 =1 O � � � � � � � � � , 2� � �� l n l j l j n j la a cO =1 � � � � � � � � � � � , (17) ãäå c x xi n i i� ( ) ( )O 0 ( )i l�N . Ïåðåéäåì îò (17) ê ýêâèâàëåíòíîé ñèñòåìå. Äëÿ ýòîãî ïåðâîå óðàâíåíèå îñòàâèì áåç èçìåíåíèé, à i-å ( , , )i l� 2 � , óìíîæåííîå íà ýëå- ìåíò O( )l k inv� �2 2 Z , ñëîæèì ñ ñóììîé âñåõ óðàâíåíèé ñèñòåìû (17). Ïîëó÷èì ñèñòåìó n a a a c n l a n n l n l n j � � � � � � � � � ( ) , ( ) � � � � 1 2 2 1 2 22 2 1O O O O � � � � =1 O O l j l n c l c n l a � � �� ( ) , ( ) � � 2 2 2 2 � l j l j lc l c� � � � � =1 O� �( ) .2 (18) Ðåøèì âòîðîå óðàâíåíèå îòíîñèòåëüíî n an � �� 2 2 . Òàê êàê 2 2 2 �Z Zk k inv \ è ( , )2 2 2k � , òî äëÿ ðàçðåøèìîñòè ýòîãî óðàâíåíèÿ äîñòàòî÷íî, ÷òîáû 2 1 � �j l jc O O( )l c�2 2� . Ïîëîæèì � � � % �j l jc l c c 1 2 22 2O( )� � . Ñðàâíåíèå O( )l n an� �2 2 2� � �� % �c k 2 12(mod ) èìååò îäíî ðåøåíèå ïî ìîäóëþ 2 1k� è äâà ðåøåíèÿ ïî ìîäóëþ 2k : n a n a n n k � � � � � � � � 2 2 2 2 2 2 12 � � � � & ' ' � , , ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 21 ãäå �2 2 12� % � �Oc l( ) . Àíàëîãè÷íî i-å óðàâíåíèå ( , , )i l� 3 � ñèñòåìû (18) èìååò äâà ðåøåíèÿ: n a n a i n i i i n i i k � � � � � � � � � � � � & ' ' � , ,2 1 åñëè 2 2 1 � � �j l j ic l cO( )� . Èç ïåðâîãî óðàâíåíèÿ ñèñòåìû (18) âûòåêàåò, ÷òî n a c n an n � � � � �� 1 1 1 2 2� � � � � �� n a l n l� , ò.å. n a c n a c n i l i n i l i k � � � � � � � � 1 1 1 2 1 1 1 2 12 � � � � � � � � & ' ' ' � � � , .' Òàêèì îáðàçîì, ñèñòåìà (17) èìååò 2 1l� ðåøåíèé, ò.å. ïîñòðîåíî 2 1l� ñèñòåì âèäà n a z n a z n l n l l � � �� 1 1 1� � � � , , (19) ãäå z c c i l i i l i k 1 1 2 1 2 12� � � � � � � � �{ , }� � ; zi i i k� � �{ , }� � 2 1 ( , , )i l� 2 � . Äëÿ ðåøåíèÿ ñèñòåìû (19) ðàññìîòðèì ñëåäóþùóþ âõîä-âûõîäíóþ ïàðó ( , )% %x x0 n ( )% � � n kN 2 1 . Ñèñòåìà (17) ïðèíèìàåò âèä % � � � � � � � � � %� % � %n a a cn n j l j n n j� � � � �� 2 1 1� �1 =1 O , �� % � � � � � � � � � %� % � %n a a c l n n l j l j n n j l2 � �O =1 , � � (20) ãäå çíà÷åíèÿ n è %n èçâåñòíû, èñõîäÿ èç àëãîðèòìà. Ðåøèì (20) îòíîñèòåëüíî % � %n ai n n i� �� ( )i l�N ïî àíàëîãèè ñ òåì, êàê îïèñàíî âûøå. Â ðåçóëüòàòå ïîëó- ÷èì 2 1l� ñèñòåì âèäà % � % % � % � � � % � % n a z n a z i n n l n n l l � � �� 1 1 , , ò.å. ïîëó÷åííàÿ ñèñòåìà èìååò òó æå ñòðóêòóðó, ÷òî è ñèñòåìà (19). Ðåøèì ñèñòåìó (19) îòíîñèòåëüíî � i n ia� ( )i l�N . Êàæäîå óðàâíåíèå ñèñòåìû (19) ïîðîæäàåò ( , )n k w2 2� óðàâíåíèé âèäà � i n i ia u� � , ãäå u z n z n z ni i i k w i k� � �� { � , � , , � }� � � � 1 1 1 1 1 1 12 2 , n nw� 2 1� , n k inv 1 2 �Z , à z zi w i� 2 � � ( )i l�N . Ñëåäîâàòåëüíî, êîëè÷åñòâî ðåøåíèé ñèñòåì (19) è (17) ðàâíî ñîîòâåòñòâåííî l w�2 è 2 2 21 1l w w ll l� � �� . Àíàëîãè÷íî ïîëó÷àåì, ÷òî ñèñòåìà (20) èìååò l w l� %� �2 1 ðåøåíèé, ãäå ( , )% � %n k w2 2 . 22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 Ïîèñê çíà÷åíèé � i è ai ( )i l�N ñâîäèòñÿ ê ðåøåíèþ l w w l3 2 12� � %� � �( ) ñèñòåì óðàâíåíèé âèäà u u h u h � � � � � � � � � � � � 1 2 , . (21) Âîçìîæíû ñëåäóþùèå ÷åòûðå ñëó÷àÿ. Ñëó÷àé 1. Ïóñòü u, � — îáðàòèìûå ýëåìåíòû êîëüöà Z 2 k . Òîãäà h1 è h2 — îá- ðàòèìûå ýëåìåíòû. Èç ïåðâîãî óðàâíåíèÿ ñèñòåìû (21) íàõîäèì u h u� �� 1 . Îòñþäà ñëåäóåò, ÷òî h u h1 2� � �� , ò.å. u h h� � � 1 2 1 � . (22) Èç óðàâíåíèÿ (22) íàõîäèì u, à èç âòîðîãî óðàâíåíèÿ ñèñòåìû (21) íàõîäèì �, ò.å. � �� h u2 � . (23) Ñëó÷àé 2. Ïóñòü u — îáðàòèìûé, à � — íåîáðàòèìûé ýëåìåíò êîëüöà Z 2 k . Òîãäà h1 è h2 — íåîáðàòèìûå ýëåìåíòû. Èç ïåðâîãî óðàâíåíèÿ ñèñòåìû (21) íàõî- äèì u h u� �� 1 . Îòñþäà ñëåäóåò, ÷òî h u h1 2� � �� , ò.å. h u h2 1� � � . (24) Ïóñòü ( , )h qk 2 2 2� # . Óðàâíåíèå (24) ðàçðåøèìî, åñëè q h\| 1. Ïðè ýòîì ÷èñëî ðåøåíèé ðàâíî q. Çíà÷åíèÿ � íàõîäèì èç óðàâíåíèÿ (23). Ñëåäîâàòåëüíî, ñèñòåìà (22) èìååò q ðåøåíèé. Ñëó÷àé 3. Ïóñòü u — íåîáðàòèìûé, à � — îáðàòèìûé ýëåìåíò êîëüöà Z 2 k . Òîãäà h1 è h2 — íåîáðàòèìûå ýëåìåíòû. Ïóñòü u u� 2 1 � � , ãäå u1 — îáðàòèìûé ýëåìåíò. Òîãäà 2 2 1 2 1 1 1 1 2 k k u u h u h � � � � � � � � � � � � � � , , (25) ãäå k1 � � �� ( ) , k2 � �� . Ñèñòåìà (25) ðàçðåøèìà, åñëè 2 1 1 k h\| è 2 2 2 k h\| . Ïðè ýòîì ïîðîæäàåòñÿ 2 1 2k k� ñèñòåì ñðàâíåíèé âèäà u u h u h k k k k 1 1 1 1 2 2 2 1 2 � � � � � � � � � % � % � � � � (mod ), (mod ), (26) ãäå h h k 1 1 2 1� % � , h h k 2 2 2 2� % � . Êàæäàÿ èç ñèñòåì (26) èìååò îäíî ðåøåíèå, à ñèñ- òåìà (25) — 2 1 2k k� ðåøåíèé. Ñëó÷àé 4. Ïóñòü u è � — íåîáðàòèìûå ýëåìåíòû êîëüöà Z pk . Òîãäà h1 è h2 — íåîáðàòèìûå ýëåìåíòû. Ïóñòü u u� 2 1 � � , ãäå u1 — îáðàòèìûé ýëåìåíò, �� 1, �1 — îáðàòèìûé ýëåìåíò. Òîãäà 2 2 1 2 1 1 1 1 1 1 2 k k u u h u h � � � � � � � � � � � � � � , , (27) ãäå k1 � � � �� ( ) , k2 � � �� . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 23 Ñèñòåìà (27) ðàçðåøèìà, åñëè 2 1 1 k h\| è 2 2 2 k h\| . Ïðè ýòîì ïîðîæäàåòñÿ 2 1 2k k� ñèñòåì ñðàâíåíèé âèäà u u h u h k k k k 1 1 1 1 1 1 2 2 2 1 2 � � � � � � � � � % � % � � � � (mod ), (mod ), (28) ãäå h h k 1 1 2 1� % � , h h k 2 2 2 2� % � . Êàæäàÿ èç ñèñòåì (28) èìååò îäíî ðåøåíèå, à ñèñ- òåìà (27) — 2 1 2k k� ðåøåíèé. Èòàê, äëÿ èäåíòèôèêàöèè âåêòîðà ( , )a � íåîáõîäèìî ðåøèòü ýêñïîíåíöèàëüíîå ÷èñëî çàäà÷ äèñêðåòíîãî ëîãàðèôìèðîâàíèÿ. Òåîðåìà äîêàçàíà. ÇÀÊËÞ×ÅÍÈÅ Â ðàáîòå èçó÷åíû ñâîéñòâà êëàññà ñåìåéñòâ ëåãêî âû÷èñëèìûõ ïåðåñòàíîâîê, îïðåäåëåííûõ â òåðìèíàõ êîíå÷íîãî êîëüöà. Àêòóàëüíîñòü çàäà÷è îáóñëîâëåíà âîçìîæíîñòüþ ïðèìåíåíèÿ ýòèõ êëàññîâ ïåðåñòàíîâîê ïðè ïîñòðîåíèè âûñîêî- ñêîðîñòíûõ âû÷èñëèòåëüíî ñòîéêèõ ïîòî÷íûõ øèôðîâ. Ïîêàçàíî, ÷òî çàäà÷è èäåíòèôèêàöèè äëÿ êëàññà ñåìåéñòâ ïåðåñòàíîâîê S( , , , )� � a h ñâîäÿòñÿ ê ðåøåíèþ ñèñòåì ìíîãîñòåïåííûõ äèîôàíòîâûõ óðàâíåíèé è ñèñòåì çàäà÷ äèñêðåòíîãî ëîãàðèôìèðîâàíèÿ. Ñëåäîâàòåëüíî, ýòè çàäà÷è òðóäíûå, ÷òî îáîñíîâûâàåò âû÷èñëèòåëüíóþ ñòîéêîñòü ïîòî÷íîãî øèôðà, ïîñòðîåííîãî íà îñíîâå óïðàâëåíèÿ äèíàìè÷åñêèì ôðàêòàëîì ýòèì êëàññîì ïåðåñòàíîâîê. Ïîñòðîåíèå è ñðàâ- íèòåëüíûé àíàëèç òàêèõ êëàññîâ ñåìåéñòâ ïåðåñòàíîâîê ïðåäñòàâëÿåò îäíî èç âîçìîæ- íûõ íàïðàâëåíèé äàëüíåéøèõ èññëåäîâàíèé. Äðóãîå íàïðàâëåíèå èññëåäîâàíèé ñâÿçà- íî ñ ïîñòðîåíèåì êëàññîâ ëåãêî âû÷èñëèìûõ ïåðåñòàíîâîê íàä êîíå÷íûì êîëüöîì, óïðàâëÿåìûõ òðàåêòîðèÿìè õàîòè÷åñêèõ äèíàìè÷åñêèõ ñèñòåì ñ íåòðèâèàëüíûì ìíî- æåñòâîì àòòðàêòîðîâ, òàêèõ êàê ñèñòåìû Ëîðåíöà Ðåñëåðà, Ñïðîòòà è ò.ä. [1]. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ê ó ç í å ö î â Ñ . Ï . Äèíàìè÷åñêèé õàîñ. — Ì.: Ôèçìàòëèò, 2001. — 296 ñ. 2. Ñ ê î á å ë å â Â . Ã . Íåëèíåéíûå àâòîìàòû íàä êîíå÷íûì êîëüöîì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 6. — Ñ. 29–42. 3. Ò ó ð á è í À . Ô . , Ï ð à ö å â è ò û é Í . Â . Ôðàêòàëüíûå ìíîæåñòâà, ôóíêöèè, ðàñïðåäåëåíèÿ. — Êèåâ: Íàóê. äóìêà, 1992. — 208 ñ. 4. Ï ð à ö ü î â è ò è é Ì . Â . Ôðàêòàëüíèé ï³äõ³ä ó äîñë³äæåííÿõ ñèíãóëÿðíèõ ðîçïîä³ë³â. — Êè¿â: ÍÏÓ ³ì. Ì.Ï. Äðàãîìàíîâà, 1998. — 296 ñ. 5. Ï à é ò ã å í Õ . - Î . , Ð è õ ò å ð Ï . Õ . Êðàñîòà ôðàêòàëîâ. Îáðàçû êîìïëåêñíûõ äèíàìè÷åñêèõ ñèñòåì. — Ì.: Ìèð, 1993. — 176 ñ. 6. Ç à é ö å â à Ý . Å . , Ñ ê î á å ë å â Â . Ã . Øèôðû íà îñíîâå ôðàêòàëîâ // Òð. ÈÏÌÌ ÍÀÍ Óêðàèíû. — 2006 — Âûï. 12 — Ñ. 63–68. 7. Õ à ð è í Þ . Ñ . è ä ð . Ìàòåìàòè÷åñêèå è êîìïüþòåðíûå îñíîâû êðèïòîëîãèè. — Ìèíñê: Íîâîå çíàíèå, 2003. — 382 ñ. 8. À ë ô å ð î â À . Ï . , Ç ó á î â À . Þ . , Ê ó ç ü ì è í À . Ñ , × å ð å ì ó ø ê è í À . Â . Îñíîâû êðèïòî- ãðàôèè. — Ì.: Ãåëèîñ ÀÐÂ, 2002. — 480 ñ. 9. Á à á è ÷ å â Ñ . Ã . , Ã î í ÷ à ð î â Â . Â . , Ñ å ð î â Ð . Å . Îñíîâû ñîâðåìåííîé êðèïòîãðàôèè. — Ì.: Ãîðÿ÷àÿ ëèíèÿ — Òåëåêîì, 2002. — 175 ñ. 10. Ø í à é å ð Á . Ïðèêëàäíàÿ êðèïòîãðàôèÿ. Ïðîòîêîëû, àëãîðèòìû, èñõîäíûå òåêñòû íà ÿçûêå Ñè. — Ì.: Òðèóìô, 2003. — 816 ñ. 11. Ê î ñ ò ð è ê è í À . È . Ââåäåíèå â àëãåáðó. — Ò. 1–3. — Ì.: Íàóêà, 1999–2000. — 912 c. 12. À õ î À . , Õ î ï ê ð î ô ò Ä æ . , Ó ë ü ì à í Ä æ . Ïîñòðîåíèå è àíàëèç âû÷èñëèòåëüíûõ àëãîðèòìîâ. — Ì.: Ìèð, 1979. — 536 ñ. 13. Ñ ê î á å ë å â Â . Â . Îá îáðàòèìûõ ìàòðèöàõ íàä êîëüöîì Z pk // Òð. ÈÏÌÌ ÍÀÍ Óêðàèíû. — 2006. — 13. — Ñ. 185–192. 14. Ñ ê î á å ë å â Â . Ã . Ïîñòðîåíèå íèæíèõ ýêñïîíåíöèàëüíûõ îöåíîê // Äîï. ÍÀÍ Óêðà¿íè. — 1997. — ¹ 3. — Ñ. 115–117. Ïîñòóïèëà 11.06.2007 24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5

Анализ класса семейств легко вычислимых перестановок

Репозитарії

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