Анализ класса семейств легко вычислимых перестановок
В работе изучены свойства класса семейств легко вычислимых перестановок, определенных в терминах конечного кольца. Актуальность задачи обусловлена возможностью применения этих классов перестановок при построении высокоскоростных вычислительно стойких поточных шифров....
Gespeichert in:
| Datum: | 2008 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/44249 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Анализ класса семейств легко вычислимых перестановок / В.Г. Скобелев, Э.Е. Зайцева // Кибернетика и системный анализ. — 2008. — № 5. — С.12-24 . — Бібліогр.: 14 назв. — рос. |
Institution
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
|