Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе
Отримано результати щодо впливу операції побітового (модульного) додавання на структуру фактор-групи за певною підгрупою відносно операції модульного (побітового) додавання на множині двійкових векторів залежно від типу вибраної підгрупи. Some results are obtained concerning the influence of bitwise...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84236 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе / Л.В. Ковальчук, О.А. Сиренко // Кибернетика и системный анализ. — 2011. — Т. 47, № 5. — С. 83-97. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84236 |
|---|---|
| record_format |
dspace |
| spelling |
Ковальчук, Л.В. Сиренко, О.А. 2015-07-04T12:51:45Z 2015-07-04T12:51:45Z 2011 Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе / Л.В. Ковальчук, О.А. Сиренко // Кибернетика и системный анализ. — 2011. — Т. 47, № 5. — С. 83-97. — Бібліогр.: 9 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84236 621.391:519.2:519.7 Отримано результати щодо впливу операції побітового (модульного) додавання на структуру фактор-групи за певною підгрупою відносно операції модульного (побітового) додавання на множині двійкових векторів залежно від типу вибраної підгрупи. Some results are obtained concerning the influence of bitwise (modular) addition on the structure of the quotient group of a particular subgroup under the operation of modular (bitwise) addition on the set of binary vectors depending on the type of the chosen subgroup. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе Аналіз перемішуючих властивостей операцій модульного та побітового додавання, визначених на одному носії Analysis of mixing properties of the operations of modular addition and bitwise addition defined on one carrier Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе |
| spellingShingle |
Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе Ковальчук, Л.В. Сиренко, О.А. Системный анализ |
| title_short |
Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе |
| title_full |
Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе |
| title_fullStr |
Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе |
| title_full_unstemmed |
Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе |
| title_sort |
анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе |
| author |
Ковальчук, Л.В. Сиренко, О.А. |
| author_facet |
Ковальчук, Л.В. Сиренко, О.А. |
| topic |
Системный анализ |
| topic_facet |
Системный анализ |
| publishDate |
2011 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Аналіз перемішуючих властивостей операцій модульного та побітового додавання, визначених на одному носії Analysis of mixing properties of the operations of modular addition and bitwise addition defined on one carrier |
| description |
Отримано результати щодо впливу операції побітового (модульного) додавання на структуру фактор-групи за певною підгрупою відносно операції модульного (побітового) додавання на множині двійкових векторів залежно від типу вибраної підгрупи.
Some results are obtained concerning the influence of bitwise (modular) addition on the structure of the quotient group of a particular subgroup under the operation of modular (bitwise) addition on the set of binary vectors depending on the type of the chosen subgroup.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84236 |
| citation_txt |
Анализ перемешивающих свойств операций модульного и побитового сложения, определенных на одном носителе / Л.В. Ковальчук, О.А. Сиренко // Кибернетика и системный анализ. — 2011. — Т. 47, № 5. — С. 83-97. — Бібліогр.: 9 назв. — рос. |
| work_keys_str_mv |
AT kovalʹčuklv analizperemešivaûŝihsvoistvoperaciimodulʹnogoipobitovogosloženiâopredelennyhnaodnomnositele AT sirenkooa analizperemešivaûŝihsvoistvoperaciimodulʹnogoipobitovogosloženiâopredelennyhnaodnomnositele AT kovalʹčuklv analízperemíšuûčihvlastivosteioperacíimodulʹnogotapobítovogododavannâviznačenihnaodnomunosíí AT sirenkooa analízperemíšuûčihvlastivosteioperacíimodulʹnogotapobítovogododavannâviznačenihnaodnomunosíí AT kovalʹčuklv analysisofmixingpropertiesoftheoperationsofmodularadditionandbitwiseadditiondefinedononecarrier AT sirenkooa analysisofmixingpropertiesoftheoperationsofmodularadditionandbitwiseadditiondefinedononecarrier |
| first_indexed |
2025-11-26T18:39:43Z |
| last_indexed |
2025-11-26T18:39:43Z |
| _version_ |
1850768698509361152 |
| fulltext |
ÓÄÊ 621.391:519.2:519.7
Ë.Â. ÊÎÂÀËÜ×ÓÊ, Î.À. ÑÈÐÅÍÊÎ
ÀÍÀËÈÇ ÏÅÐÅÌÅØÈÂÀÞÙÈÕ ÑÂÎÉÑÒÂ
ÎÏÅÐÀÖÈÉ ÌÎÄÓËÜÍÎÃÎ È ÏÎÁÈÒÎÂÎÃÎ ÑËÎÆÅÍÈß,
ÎÏÐÅÄÅËÅÍÍÛÕ ÍÀ ÎÄÍÎÌ ÍÎÑÈÒÅËÅ
Êëþ÷åâûå ñëîâà: êîëüöî âû÷åòîâ, ôàêòîð-ãðóïïà, àëãåáðàè÷åñêèå è ñòàòè-
ñòè÷åñêèå àòàêè, ïåðåìåøèâàþùèå ñâîéñòâà îïåðàöèé.
ÂÂÅÄÅÍÈÅ
Îäíîé èç çàäà÷ ñîâðåìåííîé ïðèêëàäíîé êðèïòîãðàôèè ÿâëÿåòñÿ ñîçäàíèå
êðèïòîãðàôè÷åñêèõ ïðèìèòèâîâ, ñòîéêèõ ê ðàçëè÷íûì àòàêàì, íî ïðîñòûõ è
óäîáíûõ â ðåàëèçàöèè. Â ñâÿçè ñ ýòèì âîçíèêàåò âîïðîñ î íàõîæäåíèè òàêîãî
íàáîðà îïåðàöèé íà ìíîæåñòâå áèòîâûõ âåêòîðîâ (îòêðûòûõ òåêñòîâ), êîòî-
ðûå, ñ îäíîé ñòîðîíû, ëåãêî ðåàëèçóþòñÿ è ïðîãðàììíûì, è àïïàðàòíûì ñïî-
ñîáîì, à ñ äðóãîé — îáëàäàþò «õîðîøèìè ïåðåìåøèâàþùèìè ñâîéñòâà-
ìè» [1–3]. ×åðåäîâàíèå îïåðàöèé ñ òàêèìè ñâîéñòâàìè îáåñïå÷èâàåò ñòîéêîñòü
ïðèìèòèâà ê ðàçëè÷íûì àëãåáðàè÷åñêèì è ñòàòèñòè÷åñêèì àòàêàì, ÷òî ïîçâî-
ëÿåò ñòðîèòü ïðèìèòèâû ñ ïðîñòîé è óäîáíîé â ðåàëèçàöèè ñòðóêòóðîé.
 ðàáîòå [1] ðàññìàòðèâàëîñü äåéñòâèå îïåðàöèè ñëîæåíèÿ (óìíîæåíèÿ)
â êîíå÷íîì ïîëå íà ñìåæíûå êëàññû îòíîñèòåëüíî óìíîæåíèÿ (ñëîæåíèÿ). Áûëî
ïîêàçàíî, ÷òî äåéñòâèå îïåðàöèè ñëîæåíèÿ (óìíîæåíèÿ) íà ýëåìåíòû êëàññîâ
ñìåæíîñòè îòíîñèòåëüíî îïåðàöèè óìíîæåíèÿ (ñëîæåíèÿ) ñóùåñòâåííî ðàçðó-
øàåò ñòðóêòóðó ñîîòâåòñòâóþùåé ôàêòîð-ãðóïïû. Èñõîäÿ èç ïîëó÷åííûõ ðåçóëü-
òàòîâ, â óêàçàííîé ðàáîòå ñäåëàí âûâîä î òîì, ÷òî ïðèìåíåíèå êîìïîçèöèè ýòèõ
îïåðàöèé ïðè ïîñòðîåíèè àëãîðèòìà øèôðîâàíèÿ äåëàåò åãî ñòîéêèì ê êðèïòî-
àíàëèçó íà îñíîâå ãîìîìîðôèçìîâ [1–3]. Îäíàêî â ñîâðåìåííûõ àëãîðèòìàõ
øèôðîâàíèÿ (íàïðèìåð, [4–6, 8]) ãîðàçäî ÷àùå èñïîëüçóåòñÿ êîìïîçèöèÿ äðóãèõ
îïåðàöèé, à èìåííî îïåðàöèé ìîäóëüíîãî è ïîáèòîâîãî ñëîæåíèÿ. Ïîýòîìó íå
ìåíåå àêòóàëüíà è èíòåðåñíà çàäà÷à èññëåäîâàíèÿ ïåðåìåøèâàþùèõ ñâîéñòâ
ãðóïïîâûõ îïåðàöèé ïîáèòîâîãî è ìîäóëüíîãî ñëîæåíèÿ, íîñèòåëåì êîòîðûõ
ÿâëÿåòñÿ ìíîæåñòâî äâîè÷íûõ âåêòîðîâ. Òàêèå ñâîéñòâà àëãåáðàè÷åñêèõ îïåðà-
öèé õàðàêòåðèçèðóþò òàêæå ñòîéêîñòü øèôðîâ ê àòàêàì äèôôåðåíöèàëüíîãî
êðèïòîàíàëèçà [7, 8].
 äàííîé ñòàòüå èññëåäóþòñÿ âîïðîñû, àíàëîãè÷íûå ðàññìîòðåííûì â ðàáî-
òàõ [1, 9]. Ïðèâîäÿòñÿ ðåçóëüòàòû, õàðàêòåðèçóþùèå ïåðåìåøèâàþùèå ñâîéñòâà
îïåðàöèé ïîáèòîâîãî è ìîäóëüíîãî ñëîæåíèÿ. Ïîêàçàíî, ÷òî â çàâèñèìîñòè îò
âûáîðà ïîäãðóïïû â ( , )Vn � îïåðàöèÿ ìîäóëüíîãî ñëîæåíèÿ â (�
2n , �) ìîæåò êàê
ñóùåñòâåííî ðàçðóøàòü ñòðóêòóðó ôàêòîð-ãðóïïû ïî âûáðàííîé ïîäãðóïïå, òàê
è ïîëíîñòüþ åå ñîõðàíÿòü. Òàêæå îòìå÷åíî, ÷òî äëÿ ëþáîé ïîäãðóïïû â (�
2n , �)
îïåðàöèÿ ïîáèòîâîãî ñëîæåíèÿ âñåãäà ñîõðàíÿåò ñòðóêòóðó ñîîòâåòñòâóþùåé
ôàêòîð-ãðóïïû.
ÂÑÏÎÌÎÃÀÒÅËÜÍÛÅ ÎÁÎÇÍÀ×ÅÍÈß È ÐÅÇÓËÜÒÀÒÛ
Ïðè äîêàçàòåëüñòâå îñíîâíûõ ðåçóëüòàòîâ èñïîëüçóþòñÿ ñëåäóþùèå îáîçíà÷å-
íèÿ è óòâåðæäåíèÿ. Çäåñü è äàëåå ïîä ( , )Vn � áóäåì ïîíèìàòü ìíîæåñòâî âåê-
òîðîâ äëèíû n ñ îïåðàöèåé ïîáèòîâîãî ñëîæåíèÿ, à ïîä (�
2n , �) — àääèòèâ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 83
© Ë.Â. Êîâàëü÷óê, Î.À. Ñèðåíêî, 2011
íóþ ãðóïïó êîëüöà âû÷åòîâ �
2n . Êàæäîìó öåëîìó ÷èñëó z n��
2
ïîñòàâèì
â ñîîòâåòñòâèå áèòîâûé âåêòîð äëèíû n , ÿâëÿþùèéñÿ äâîè÷íûì ïðåäñòàâëå-
íèåì ýòîãî ÷èñëà. Òàêèì îáðàçîì, ìíîæåñòâà �
2n è Vn îòîæäåñòâëåíû. Öåëîå
÷èñëî è ñîîòâåòñòâóþùèé åìó äâîè÷íûé âåêòîð îáîçíà÷èì îäèíàêîâî; èç êîí-
òåêñòà áóäåò ïîíÿòíî, êàêîå èìåííî ïðåäñòàâëåíèå èñïîëüçóåòñÿ.
Äëÿ ëþáîãî t � 0 ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ: pt t
� �
�
�
�
���
1
2
1
2 1
;
q pt t�
1 .
Îáîçíà÷åíèå âèäà
... ... ...
��� ����� ���
b a bk k k� 1
0 0
áèò áèò áèò
... 0 0
1 1
... ...
����� ���
a báèò áèò
èñïîëüçóåòñÿ äëÿ áèòîâîãî âåêòîðà äëèíû n a bi i
i
k
i
k
� �
�
�
�
��
1
1
1
, ó êîòîðîãî ñëåâà
èìååòñÿ bk�1 ïðîèçâîëüíûõ áèòîâ, äàëåå ak íóëåâûõ áèòîâ è ò.ä.
Ëåììà 1.  óêàçàííûõ îáîçíà÷åíèÿõ:
à) âñå ïîäãðóïïû â ( , )Vn � èìåþò ñòðóêòóðó
... ... ...
��� ����� ���
b a bk k k� 1
0 0
áèò áèò áèò
... 0 0
2 2
... ...
����� ���
a báèò áèò
0 0
1 1
... ...
����� ���
a báèò áèò
,
ãäå a b ni i
i
k
i
k
� �
�
�
�
��
1
1
1
, ai � 0 , bi � 0 ïðè i k� 2, ..., ; b1 0� , a1 0� , bk� �1 0 ;
á) âñå ïîäãðóïïû â (�
2n , �) èìåþò ñòðóêòóðó
... ...
��� �����
n k k
áèò áèò
0 0
äëÿ íåêîòîðîãî k n� 0, ..., .
Ëåììà 2. 1. Ïóñòü ñëó÷àéíûå âåëè÷èíû x è y ðàâíîâåðîÿòíî ðàñïðåäåëåíû
íà ìíîæåñòâå {0, � , a
1}, a �� . Òîãäà
P x y a P x y a
a
( ) ( )� � � � �
� �1
1
2
1
2
; P x y a P x y a
a
( ) ( )� �
� � � �
1
1
2
1
2
.
2. Ïóñòü ñëó÷àéíûå âåëè÷èíû x è y ðàâíîâåðîÿòíî ðàñïðåäåëåíû íà ãðóïïå
(�
2n , �). Òîãäà
P x y p
n n( )� � � �
�
1
2
1
2 1
; P x y q
n n( )� �
�
�
1
2
1
2 1
.
Äîêàçàòåëüñòâî. 1. Ïî ôîðìóëå ïîëíîé âåðîÿòíîñòè
P x y a P x y a y i P y i P x a i
i
a
i
a
( ) ( / ) ( ) ( )� � � � � � � � �
�
�
� �
0
1
0
1
P y i( )� �
� �
� � � �
�
�
� �
� � �
1 1 1 1
20
1
1 1a
P x a i
a
P x j
a
j
a
a a
i
a
j
a
j
a
( ) ( )
( )
a
a
a a2
1
2
1
2
1
2
�
�
� � .
84 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
Àíàëîãè÷íî äîêàæåì âòîðîå óòâåðæäåíèå ï. 1:
P x y a P x y a y i P y i
i
a
( ) ( / ) ( )� �
� � �
� � �
�
�1 1
0
1
� �
� � �
�
�
�
� �P x a i P y i
a
P x a i
a
P x
i
a
i
a
( ) ( ) ( ) (1
1
1
1
0
1
0
1
� �
�
� j
j
a
)
0
1
� � � �
�
�
�
�
� �
1 1 1
2
1
2
1
2
1
21
1
1
1
2a
P x j
a
j
a
a a
a
a
aj
a
j
a
( )
( )
a
.
Ïîñêîëüêó P x y a P x y a
a
( ) ( )� � �
� � � �1
1
2
1
2
è P x y a( )� �
�1
�
� �
�
1 1
1
2
1
2
P x y a
a
( ) , èìååì P x y a P x y a
a
( ) ( )� � � � �
�
1
1
2
1
2
è
P x y a P x y a
a
( ) ( )� �
� � � � �1
1
2
1
2
.
2. Îáîçíà÷èì p P x y� �( ) . Òîãäà P x y
n
n n
( )� � �
2
2
1
22
. Íàéäåì p . Èñïîëü-
çóåì òîò ôàêò, ÷òî P x y P x y( ) ( )� �
�1 , òîãäà
P x y P x y P x y( ) ( ) ( )� � � �
�1 .
Ïîñêîëüêó P x y P x y p( ) ( )� � � � , ïîëó÷èì óðàâíåíèå p p
n
� �
1
2
1 , îòêóäà
p
n
�
�
1
2
1
2 1
. Òîãäà
P x y p
n
( )� � �
�
1
2
1
2 1
,
P x y P x y p
n n
( ) ( )� �
� �
�
�
�
�
�� � �
� �
1 1 1
1
2
1
2
1
2
1
21 1
.
 ïðèíÿòûõ îáîçíà÷åíèÿõ P x y q
n n( )� �
�
�
1
2
1
2 1
, à P x y( )� �
1
2
1
2 1
� �
�n
� pn . Ëåììà äîêàçàíà.
ÂËÈßÍÈÅ ÎÏÅÐÀÖÈÈ ÌÎÄÓËÜÍÎÃÎ ÑËÎÆÅÍÈß
ÍÀ ÑÒÐÓÊÒÓÐÓ ÔÀÊÒÎÐ-ÃÐÓÏÏÛ ( , )Vn � ÏÎ ÅÅ ÏÎÄÃÐÓÏÏÅ
Îïðåäåëåíèå 1. Îáîçíà÷èì G a a a b b b bk k k( , ; , , )1 2 1 2 1� � � � �� � ïîäãðóïïó èí-
äåêñà 2a ãðóïïû ( , )Vn � , ýëåìåíòû êîòîðîé ñîäåðæàò k «íóëåâûõ» áëîêîâ
A Ak1� �� , ò.å. èìåþò ñëåäóþùóþ ñòðóêòóðó:
áëîê Bk �1 áëîê Ak áëîê Bk áëîê A2 áëîê B2 áëîê A1 áëîê B1
... ... ...
��� ����� ���
b a bk k k� 1
0 0
áèò áèò áèò
... 0 0
2 2
... ...
����� ���
a báèò áèò
0 0
1 1
... ...
����� ���
a báèò áèò
,
ãäå áèòû èç «íåíóëåâûõ» áëîêîâ B Bk1 1� � �� ïðèíèìàþò ïðîèçâîëüíûå çíà÷å-
íèÿ, ïðè÷åì a ai
i
k
�
� �
1
, b bi
i
k
�
� �
1
è a b b nk� � ��1 , ai � 0 , bi � 0 ïðè i k� 2, ..., ;
b1 0� , a1 0� , bk� �1 0 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 85
Òåîðåìà 1. Ïóñòü G a a a b b b bk k k( , ; , , )1 2 1 2 1� � � � �� � — íåêîòîðàÿ ïîäãðóï-
ïà èíäåêñà 2a ãðóïïû ( , )Vn � ; v1 è v2 — ñëó÷àéíûå ýëåìåíòû, ðàâíîâåðîÿòíî
ðàñïðåäåëåííûå â êëàññàõ ñìåæíîñòè H i è H j ïîäãðóïïû G ñîîòâåòñòâåííî;
i j, �1 , .. . , 2a . Òîãäà:
1) êîëè÷åñòâî êëàññîâ ñìåæíîñòè ïî ïîäãðóïïå G , â êîòîðûå ñóììà ýëåìåí-
òîâ v1 è v2 ïî ìîäóëþ 2n ïîïàäàåò ñ íåíóëåâîé âåðîÿòíîñòüþ, ðàâíî 2k , åñëè
b1 0� ; 2 1k
, åñëè b1 0� , à êîëè÷åñòâî êëàññîâ ñìåæíîñòè, â êîòîðûå ñóììà ýëå-
ìåíòîâ v1 è v2 ïî ìîäóëþ 2n ïîïàäàåò ñ íóëåâîé âåðîÿòíîñòüþ, ðàâíî 2 2a k
,
åñëè b1 0� ; 2 2 1a k
, åñëè b1 0� ;
2) åñëè H Hi j� , òî êëàññû ñìåæíîñòè, â êîòîðûå ðàçíîñòü ýëåìåíòîâ v1 è
v2 ïî ìîäóëþ 2n ïîïàäàåò ñ íåíóëåâîé âåðîÿòíîñòüþ, èìåþò âèä
áëîê Bk �1 áëîê Ak áëîê Bk áëîê B2 áëîê A1 áëîê B1
...
���
bk� 1 áèò
...
���
ak áèò
...
���
bk áèò
... ...
���
b2 áèò
...
���
a1 áèò
...
���
b1 áèò
,
ãäå áëîêè Al ñîäåðæàò ëèáî òîëüêî 0, ëèáî 1 äëÿ ëþáîãî l �1 , .. . , k , è êîëè-
÷åñòâî ýòèõ êëàññîâ ñìåæíîñòè ðàâíî 2k , åñëè b1 0� ; 2 1k
, åñëè b1 0� , à êî-
ëè÷åñòâî êëàññîâ ñìåæíîñòè, â êîòîðûå ðàçíîñòü ýëåìåíòîâ v1 è v2 ïî ìîäó-
ëþ 2n ïîïàäàåò ñ íóëåâîé âåðîÿòíîñòüþ, ðàâíî 2 2a k
, åñëè b1 0� ;
2 2 1a k
, åñëè b1 0� . Ïðè ýòîì âåðîÿòíîñòè ïîïàäàíèÿ ðàçíîñòè ýëåìåíòîâ
v1 è v2 â ðàçëè÷íûå êëàññû ñìåæíîñòè îäèíàêîâû ïðè ëþáîì âûáîðå êëàññà
ñìåæíîñòè H i (ò.å. êëàññà ñìåæíîñòè, êîòîðîìó ïðèíàäëåæàò v1 è v2) è çàâè-
ñÿò òîëüêî îò âèäà ïîäãðóïïû, ïî êîòîðîé ñòðîÿòñÿ ýòè êëàññû ñìåæíîñòè;
3) íåíóëåâûå âåðîÿòíîñòè ïîïàäàíèÿ ñóììû (ðàçíîñòè) ýëåìåíòîâ v1 è v2 ïî
ìîäóëþ 2n â ñîîòâåòñòâóþùèå êëàññû ñìåæíîñòè íàõîäÿòñÿ â ïðåäåëàõ îò qb
i
k
i
�
�
1
äî pb
i
k
i
�
�
1
.
Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà äàííîé òåîðåìû äîñòàòî÷íî ðàññìîò-
ðåòü ïîäãðóïïó, ñîäåðæàùóþ îäèí íóëåâîé áëîê åäèíè÷íîé äëèíû è îäèí íóëå-
âîé áëîê áîëüøåé äëèíû. Âûáåðåì ïîäãðóïïó H t m, ãðóïïû ( , )Vn � òàêèì îáðà-
çîì, ÷òî åå ýëåìåíòû èìåþò ñëåäóþùèé âèä:
... ... ...
��� ��� ���
00 0
m táèò áèò
.
Ðàññìîòðèì äåéñòâèå îïåðàöèè ìîäóëüíîãî ñëîæåíèÿ â ãðóïïå �
2n íà ýëå-
ìåíòû ôàêòîð-ãðóïïû ãðóïïû ( , )Vn � ïî âûáðàííîé ïîäãðóïïå H t m, èíäåêñà 8
îòíîñèòåëüíî îïåðàöèè ïîáèòîâîãî ñëîæåíèÿ. Äëÿ ýòîãî âûïèøåì âñå êëàññû
ñìåæíîñòè ïî ýòîé ïîäãðóïïå:
86 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
H
m t
1
00 0� ... ... ...
��� ��� ���
áèò áèò
; H 5
01 0� ... ... ...
��� ��� ���
;
H 2
00 1� ... ... ...
��� ��� ���
; H 6
01 1� ... ... ...
��� ��� ���
;
H 3
10 0� ... ... ...
��� ��� ���
; H 7
11 0� ... ... ...
��� ��� ���
;
H 4
10 1� ... ... ...
��� ��� ���
; H 8
11 1� ... ... ...
��� ��� ���
.
Òîãäà âåðîÿòíîñòè P v v H v Hi i( /1 2 1� � � ; v H k2 � ) , ãäå i j k, , , ...,�1 8 , îïèñû-
âàþòñÿ òàáë. 1, ñèììåòðè÷íîé îòíîñèòåëüíî ãëàâíîé äèàãîíàëè, à âåðîÿòíîñòè
P v v H v v Hi j( / , )1 2 1 2
� � , ãäå i j, , ,�1 8� , îïèñûâàþòñÿ òàáë. 2.
Äîêàæåì ñíà÷àëà ðåçóëüòàòû òàáë. 1. Ðàññìîòðèì äëÿ ïðèìåðà äîêàçà-
òåëüñòâî íåêîòîðûõ âîçìîæíûõ ñëó÷àåâ, ïîñêîëüêó äîêàçàòåëüñòâî îñòàëüíûõ
ñëó÷àåâ ïðîâîäèòñÿ àíàëîãè÷íî.
Äëÿ ïðîèçâîëüíîãî âåêòîðà v Vn� ââåäåì îáîçíà÷åíèÿ
v
m
v
t
vC R
� ... ... ...
��� ���
��
���
��
00 0
áèò áèò
;
� �v
m
v
t
vC R
0 0... ...
���
��
���
��
áèò áèò
.
1. Ïóñòü v H v H1 1 2 1� �, , òîãäà âåêòîðû v1 è v2 èìåþò ñëåäóþùèé âèä:
v
m t
1
00 0� ... ... ...
��� ��� ���
áèò áèò
; v
m t
2
00 0� ... ... ...
��� ��� ���
áèò áèò
.
Ïî ôîðìóëå ïîëíîé âåðîÿòíîñòè èìååì
P v v H P v v v vR R t m t( ) ( )1 2 1 1 2 1 2
12 2� � � � � � � � � � �� �
� � � � � � � � � �� �P v v v v P v vm t R R t R R t( ) ( )1 2
1
1 2 1 2
2 2 2
� � � � �P v v P v vR R t C C m( ) ( )
1 2 1 2
2 2 .
Èñïîëüçóÿ ðåçóëüòàò ï. 1 ëåììû 2, ïîëó÷àåì
P v v H p p
t m t m( )1 2 1 1 1
1
2
1
2
1
2
1
2
� � � �
�
�
�
�� �
�
�
�
�� �
� �
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 87
88 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
Ò à á ë è ö à 1 . Âåðîÿòíîñòè ïîïàäàíèÿ ñóììû âåêòîðîâ v1 è v2 â ñîîòâåòñòâó-
þùèé êëàññ ñìåæíîñòè H i , i �1 8, ...,
v H2 1� v H2 2� v H2 3� v H2 4� v H2 5� v H2 6� v H2 7� v H2 8�
v H1 1�
H 1
p pt m
H 2
q pt m
q qt m p pt m 0 0 0 0 0 0 0 0 p qt m q qt m q pt m p qt m
H 3
0
H 4
0
0 0 p pt m q pt m q qt m p pt m p qt m q qt m q pt m p qt m 0 0 0 0
H 5
p qt m
H 6
q qt m
q pt m p qt m 0 0 0 0 p pt m q pt m q qt m p pt m 0 0 0 0
H 7
0
H 8
0
0 0 p qt m q qt m q pt m p qt m 0 0 0 0 p pt m q pt m q qt m p pt m
v H1 2�
p qt m q qt m 0 0 0 0 0 0 0 0 q pt m p qt m p pt m q pt m
0 0 q qt m p pt m p qt m q qt m q pt m p qt m p pt m q pt m 0 0 0 0
p pt m q pt m 0 0 0 0 q qt m p pt m p qt m q qt m 0 0 0 0
0 0 q pt m p qt m p pt m q pt m 0 0 0 0 q qt m p pt m p qt m q qt m
v H1 3�
p pt m q pt m q qt m p pt m p qt m q qt m q pt m p qt m 0 0 0 0
0 0 0 0 0 0 0 0 p qt m q qt m q pt m p qt m
p qt m q qt m q pt m p qt m 0 0 0 0 p pt m q pt m q qt m p pt m
0 0 0 0 p pt m q pt m q qt m p pt m 0 0 0 0
v H1 4�
p qt m q qt m q pt m p qt m p pt m q pt m 0 0 0 0
0 0 0 0 0 0 q pt m p qt m p pt m q pt m
p pt m q pt m 0 0 0 0 q qt m p pt m p qt m q qt m
0 0 q qt m p pt m p qt m q qt m 0 0 0 0
v H1 5�
0 0 0 0 p pt m q pt m q qt m p pt m
p pt m q pt m q qt m p pt m 0 0 0 0
0 0 0 0 p qt m q qt m q pt m p qt m
p qt m q qt m q pt m p qt m 0 0 0 0
v H1 6�
0 0 q qt m p pt m p qt m q qt m
p qt m q qt m 0 0 0 0
0 0 q pt m p qt m p pt m q pt m
p pt m q pt m 0 0 0 0
v H1 7�
0 0 0 0
p pt m q pt m q qt m p pt m
0 0 0 0
p qt m q qt m q pt m p qt m
v H1 8�
0 0
p qt m q qt m
0 0
p pt m q pt m
Ò à á ë è ö à 2 . Âåðîÿòíîñòè ïîïàäàíèÿ ðàçíîñòè âåêòîðîâ v1 è v2 â ñîîòâåò-
ñòâóþùèé êëàññ ñìåæíîñòè H i , i �1 8, ...,
v v H i1 2, �
Âåðîÿòíîñòè ïîïàäàíèÿ â H i
H1 H 2 H 3 H 4 H 5 H 6 H 7 H 8
H i , i � 1 , .. . , 8 p pt m q qt m 0 0 0 0 p qt m q pt m
Àíàëîãè÷íî íàéäåì âåðîÿòíîñòè ïîïàäàíèÿ â äðóãèå êëàññû ñìåæíîñòè:
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 2 1 2 1 2
2 2� � � � � � � �
�
�
�
�
� �
�
�
�
� �
� �
1
2
1
2
1
2
1
21 1t m t mq p ;
P v v H( )1 2 3 0� � � ;
P v v H( )1 2 4 0� � � ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 5 1 2 1 2
2 2� � � � � � � �
� �
�
�
�
�
�
�
�
� �
� �
1
2
1
2
1
2
1
21 1t m t mp q ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 6 1 2 1 2
2 2� � � � � � � �
�
�
�
�
�
�
�
�
� �
� �
1
2
1
2
1
2
1
21 1t m t mq q ;
P v v H( )1 2 7 0� � � ;
P v v H( )1 2 8 0� � � .
2. Ïóñòü v H v H1 5 2 5� �, , òîãäà âåêòîðû v1 è v2 èìåþò ñëåäóþùèé âèä:
v
m t
1
01 0� ... ... ...
��� ��� ���
áèò áèò
; v
m t
2
01 0� ... ... ...
��� ��� ���
áèò áèò
.
Âûïîëíÿÿ âû÷èñëåíèÿ, àíàëîãè÷íûå ïðåäûäóùèì, ïîëó÷èì:
P v v H( )1 2 1 0� � � ;
P v v H( )1 2 2 0� � � ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 3 1 2 1 2
2 2� � � � � � � �
� �
�
�
�
� �
�
�
�
� �
� �
1
2
1
2
1
2
1
21 1t m t mp p ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 4 1 2 1 2
2 2� � � � � � � �
�
�
�
�
� �
�
�
�
� �
� �
1
2
1
2
1
2
1
21 1t m t mq p ;
P v v H( )1 2 5 0� � � ;
P v v H( )1 2 6 0� � � ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 7 1 2 1 2
2 2� � � � � � � �
� �
�
�
�
�
�
�
�
� �
� �
1
2
1
2
1
2
1
21 1t m t mp q ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 8 1 2 1 2
2 2� � � � � � � �
�
�
�
�
�
�
�
�
� �
� �
1
2
1
2
1
2
1
21 1t m t mq q .
3. Ïóñòü v H v H1 2 2 6� �, , òîãäà âåêòîðû v1 è v2 èìåþò âèä
v
m t
1
00 1� ... ... ...
��� ��� ���
áèò áèò
; v
m t
2
01 1� ... ... ...
��� ��� ���
áèò áèò
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 89
Ïîëó÷èì ñëåäóþùèå âåëè÷èíû äëÿ ñîîòâåòñòâóþùèõ âåðîÿòíîñòåé:
P v v H( )1 2 1 0� � � ;
P v v H( )1 2 2 0� � � ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 3 1 2 1 2
2 1 2� � � � � � � � �
� �
�
�
�
�� �
�
�
�
�� �
� �
1
2
1
2
1
2
1
21 1t m t mp p ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 4 1 2 1 2
2 1 2� � � � � � � � �
�
�
�
�
�� �
�
�
�
�� �
� �
1
2
1
2
1
2
1
21 1t m t mq p ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 5 1 2 1 2
2 1 2� � � � � � � � �
� �
�
�
�
��
�
�
�
�� �
� �
1
2
1
2
1
2
1
21 1t m t mp q ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 6 1 2 1 2
2 1 2� � � � � � � � �
�
�
�
�
��
�
�
�
�� �
� �
1
2
1
2
1
2
1
21 1t m t mq q ;
P v v H( )1 2 7 0� � � ;
P v v H( )1 2 8 0� � � .
4. Ïóñòü v H v H1 2 2 8� �, , òîãäà âåêòîðû v1 è v2 èìåþò âèä
v
m t
1
00 1� ... ... ...
��� ��� ���
áèò áèò
; v
m t
2
11 1� ... ... ...
��� ��� ���
áèò áèò
.
Ïîëó÷èì ñëåäóþùèå âåëè÷èíû:
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 1 1 2 1 2
2 1 2� � � � � � � � �
� �
�
�
�
�� �
�
�
�
�� �
� �
1
2
1
2
1
2
1
21 1t m t mp p ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 2 1 2 1 2
2 1 2� � � � � � � � �
�
�
�
�
�� �
�
�
�
�� �
� �
1
2
1
2
1
2
1
21 1t m t mq p ;
P v v H( )1 2 3 0� � � ;
P v v H( )1 2 4 0� � � ;
P v v H( )1 2 5 0� � � ;
P v v H( )1 2 6 0� � � ;
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 7 1 2 1 2
2 1 2� � � � � � � � �
� �
�
�
�
��
�
�
�
�� �
� �
1
2
1
2
1
2
1
21 1t m t mp q ;
90 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
P v v H P v v P v vR R t C C m( ) ( ) ( )1 2 8 1 2 1 2
2 1 2� � � � � � � � �
�
�
�
�
��
�
�
�
�� �
� �
1
2
1
2
1
2
1
21 1t m t mq q .
Äîêàæåì òåïåðü ðåçóëüòàòû òàáë. 2. Äëÿ ïðèìåðà ðàññìîòðèì ñëó÷àé, êîãäà
v H v H1 1 2 1� �, . Òîãäà ýòè âåêòîðû èìåþò âèä
v
m t
1
00 0� ... ... ...
��� ��� ���
áèò áèò
; v
m t
2
00 0� ... ... ...
��� ��� ���
áèò áèò
.
Ïî ôîðìóëå ïîëíîé âåðîÿòíîñòè èìååì
P v v H P v v v vt m
R R( ) ( ),1 2 2 1 2 1
� � � � � � � � P v v v v P v vR R R R( ) ( )� � � � � �2 1 2 1 2 1
� � �P v v P v vR R C C( ) ( )
2 1 2 1
.
Èñïîëüçóÿ ðåçóëüòàò ï. 2 ëåììû 2, ïîëó÷àåì
P v v H p p
t m t m( )1 2 1 1 1
1
2
1
2
1
2
1
2
� � �
�
�
�
�� �
�
�
�
�� �
� �
.
Àíàëîãè÷íî äëÿ âñåõ äðóãèõ âåðîÿòíîñòåé ïîëó÷èì ñëåäóþùèå çíà÷åíèÿ:
P v v H P v v P v vC C R R
t
( ) ( ) ( )1 2 2 1 2 1 2 1
1
1
2
1
2
� �
� � �
�
�
�
�
� �
�
�
�
�� �
�
1
2
1
2 1m t mq q ;
P v v H( )1 2 3 0
� � ;
P v v H( )1 2 4 0
� � ;
P v v H( )1 2 5 0
� � ;
P v v H( )1 2 6 0
� � ;
P v v H P v v P v vR R C C
t
( ) ( ) ( )1 2 7 1 2 1 2 1
1
2
1
2
1
� � � � � �
�
�
�
��� 2
1
2 1
�
�
�
�� �
�m t mp q ;
P v v H P v v P v vR R C C
t
( ) ( ) ( )1 2 8 1 2 1 2 1
1
1
2
1
2
1
� � �
� �
�
�
�
�
� 2
1
2 1
�
�
�
�
� �
�m t mq p .
Òåîðåìà äîêàçàíà.
Ðàññìîòðèì íåñêîëüêî ïðèìåðîâ ïðèìåíåíèÿ òåîðåìû äëÿ ïîäãðóïï ðàçíîé
ñòðóêòóðû.
Ïðèìåð 1. Ïóñòü H t m, — ïîäãðóïïà ( , )Vn � , èíäåêñ êîòîðîé ðàâåí ÷åòû-
ðåì, à åå ýëåìåíòû èìåþò ñëåäóþùèé âèä:
... ... ...
��� ��� ���
0 0
m táèò áèò
.
Îáîçíà÷èì
e
t
1
0 010 0� ( ... ... )
��� ���
áèò
; em
t m
�
� �
( ... ... )0 010 0
1
��� �����
áèò
; e e etm t m� � .
Ðàññìîòðèì äåéñòâèå îïåðàöèè ìîäóëüíîãî ñëîæåíèÿ â ãðóïïå �
2n íà ýëå-
ìåíòû ôàêòîð-ãðóïïû ãðóïïû ( , )Vn � ïî âûáðàííîé ïîäãðóïïå H t m, îòíîñèòåëü-
íî îïåðàöèè ïîáèòîâîãî ñëîæåíèÿ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 91
Âûïèøåì âñå êëàññû ñìåæíîñòè ïî ýòîé ïîäãðóïïå:
H H t m1 � , ; H e Hm t m3 � � , ;
H e Ht t m2 � � , ; H e Htm t m4 � � , .
Òîãäà âåðîÿòíîñòè P v v H v H v Hi j k( / , )1 2 1 2� � � � , ãäå i j k, , , ...,�1 4 , îïè-
ñûâàþòñÿ òàáë. 3, ñèììåòðè÷íîé îòíîñèòåëüíî ãëàâíîé äèàãîíàëè, à âåðîÿò-
íîñòè P v v H v v Hi j( / , )1 2 1 2
� � , ãäå i j, , ,�1 4� , îïèñûâàþòñÿ òàáë. 4.
Ïðèìåð 2. Ïóñòü H t — ïîäãðóïïà ( , )Vn � , èíäåêñ êîòîðîé ðàâåí ÷åòûðåì,
à åå ýëåìåíòû èìåþò ñëåäóþùèé âèä:
... ...
��� ���
0 0
t áèò
.
Âûïèøåì âñå êëàññû ñìåæíîñòè ïî ýòîé ïîäãðóïïå:
H
t
1
0 0� ... ...
��� ���
áèò
; H 3
1 0� ... ...
��� ���
;
H 2
0 1� ... ...
��� ���
; H 4
1 1� ... ...
��� ���
.
Ðàññìîòðèì äåéñòâèå îïåðàöèè ìîäóëüíîãî ñëîæåíèÿ â ãðóïïå �
2n íà ýëå-
ìåíòû ôàêòîð-ãðóïïû ãðóïïû ( , )Vn � ïî âûáðàííîé ïîäãðóïïå H t . Òîãäà âåðî-
ÿòíîñòè P v v H v H v Hi j k( / , )1 2 1 2� � � � , ãäå i j k, , , ...,�1 4, îïèñûâàþòñÿ
òàáë. 5, ñèììåòðè÷íîé îòíîñèòåëüíî ãëàâíîé äèàãîíàëè, à âåðîÿòíîñòè
P v v H v v Hi j( / , )1 2 1 2
� � , ãäå i j k, , , ,�1 4� , îïèñûâàþòñÿ òàáë. 6.
92 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
Ò à á ë è ö à 3 . Âåðîÿòíîñòè ïîïàäàíèÿ ñóììû âåêòîðîâ v1 è v2 â ñîîòâåòñòâó-
þùèé êëàññ ñìåæíîñòè H i , i �1 4, ..., (äëÿ ïðèìåðà 1)
v H2 1� v H2 2� v H2 3� v H2 4�
v H1 1�
H1
p pt m
H 2
q pt m
H1
q qt m
H 2
p pt m
H1
p qt m
H 2
q qt m
H1
q pt m
H 2
p qt m
H 3
p qt m
H 4
q qt m
H 3
q pt m
H 4
p qt m
H 3
p pt m
H 4
q pt m
H 3
q qt m
H 4
p pt m
v H1 2�
q qt m p pt m p qt m q qt m q pt m p qt m p pt m q pt m
q pt m p qt m p pt m q pt m q qt m p pt m p qt m q qt m
v H1 3�
p qt m q qt m q pt m p qt m p pt m q pt m q qt m p pt m
p pt m q pt m q qt m p pt m p qt m q qt m q pt m p qt m
v H1 4�
q pt m p qt m p pt m q pt m q qt m p pt m p qt m q qt m
q qt m p pt m p qt m q qt m q pt m p qt m p pt m q pt m
Ò à á ë è ö à 4 . Âåðîÿòíîñòè ïîïàäàíèÿ ðàçíîñòè âåêòîðîâ v1 è v2 â ñîîòâåò-
ñòâóþùèé êëàññ ñìåæíîñòè H i , i �1 4, ..., (äëÿ ïðèìåðà 1)
v v H i1 2, �
Âåðîÿòíîñòè ïîïàäàíèÿ â H i
H1 H 2 H 3 H 4
H i , i � 1 , .. ., 4 p pt m q qt m p qt m q pt m
Ñëåäóåò îòìåòèòü, ÷òî åñëè â ïîäãðóïïå èìåþòñÿ òîëüêî íóëåâûå áëîêè åäè-
íè÷íîé äëèíû, òî êîëè÷åñòâî êëàññîâ ñìåæíîñòè, â êîòîðûå ñóììà âåêòîðîâ ïî
ìîäóëþ 2n ïîïàäàåò ñ íåíóëåâîé âåðîÿòíîñòüþ, áóäåò íàèáîëüøèì; åñëè íóëå-
âûå áëîêè áóäóò áîëüøîé äëèíû, òî êîëè÷åñòâî êëàññîâ ñìåæíîñòè, â êîòîðûå
ñóììà âåêòîðîâ ïî ìîäóëþ 2n ïîïàäàåò ñ íåíóëåâîé âåðîÿòíîñòüþ, óìåíüøàåòñÿ.
×åì äëèííåå íóëåâûå áëîêè, òåì â ìåíüøåå êîëè÷åñòâî êëàññîâ ñìåæíîñòè ïîïà-
äàåò ñóììà âåêòîðîâ ïî ìîäóëþ 2n ñ íåíóëåâîé âåðîÿòíîñòüþ. Òàêèì îáðàçîì,
ïåðåìåøèâàþùèå ñâîéñòâà îïåðàöèè ìîäóëüíîãî ñëîæåíèÿ îòíîñèòåëüíî ïîáè-
òîâîãî ñëîæåíèÿ áóäóò çàâèñåòü îò ñòðóêòóðû ïîäãðóïïû.
ÂËÈßÍÈÅ ÎÏÅÐÀÖÈÈ ÏÎÁÈÒÎÂÎÃÎ ÑËÎÆÅÍÈß ÍÀ ÑÒÐÓÊÒÓÐÓ
ÔÀÊÒÎÐ-ÃÐÓÏÏ (�2n , � ) ÏÎ ÅÅ ÏÎÄÃÐÓÏÏÅ ÈÍÄÅÊÑÀ 2k ÎÒÍÎÑÈÒÅËÜÍÎ
ÌÎÄÓËÜÍÎÃÎ ÑËÎÆÅÍÈß
Òåîðåìà 2. Ïóñòü Gk — ïîäãðóïïà (�
2n , �) èíäåêñà 2k . Òîãäà:
1) Gk (â ñîîòâåòñòâóþùåì ïðåäñòàâëåíèè) — ïîäãðóïïà ( , )Vn � ;
2) êëàññû ñìåæíîñòè ïî ïîäãðóïïå Gk (îòíîñèòåëüíî îïåðàöèè +) èìåþò
âèä i Gk� , 0 2� �i k ;
3) êëàññû ñìåæíîñòè ïî ïîäãðóïïå Gk (îòíîñèòåëüíî îïåðàöèè �) èìåþò
âèä i Gk� , ïðè÷åì i G i Gk k� � � , 0 2� �i k ;
4) åñëè v v i Gk1 2, � � , òî ñ âåðîÿòíîñòüþ åäèíèöà v v Gk1 2� � , 0 2� �i k ;
5) åñëè v v i Gk1 2, � � , òî ñ âåðîÿòíîñòüþ åäèíèöà v v Gk1 2
� , 0 2� �i k ;
6) åñëè v i Gk1 � � , v j Gk2 � � , òî ñ âåðîÿòíîñòüþ åäèíèöà v v i j Gk1 2� � � � ,
ïðè÷åì êëàññ ñìåæíîñòè i j Gk� � ìîæåò íå ñîâïàäàòü ñ êëàññîì ñìåæíîñòè
i j Gk� � , 0 2� �i j k, ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 93
Ò à á ë è ö à 5 . Âåðîÿòíîñòè ïîïàäàíèÿ ñóììû âåêòîðîâ v1 è v2 â ñîîòâåòñòâó-
þùèé êëàññ ñìåæíîñòè H i , i �1 4, ..., (äëÿ ïðèìåðà 2)
v H2 1� v H2 2� v H2 3� v H2 4�
v H1 1�
H1
pt
H 2
0
H1
0
H 2
pt
H1
qt
H 2
0
H1
0
H 2
qt
H 3
qt
H 4
0
H 3
0
H 4
qt
H 3
pt
H 4
0
H 3
0
H 4
pt
v H1 2�
0 pt qt 0 0 qt pt 0
0 qt pt 0 0 pt qt 0
v H1 3�
qt 0 0 qt pt 0 0 pt
pt 0 0 pt qt 0 0 qt
v H1 4�
0 qt pt 0 0 pt qt 0
0 pt qt 0 0 qt pt 0
Ò à á ë è ö à 6 . Âåðîÿòíîñòè ïîïàäàíèÿ ðàçíîñòè âåêòîðîâ v1 è v2 â ñîîòâåò-
ñòâóþùèé êëàññ ñìåæíîñòè H i , i �1 4, ..., (äëÿ ïðèìåðà 2)
v v H i1 2, �
Âåðîÿòíîñòè ïîïàäàíèÿ â H i
H1 H 2 H 3 H 4
H i , i � 1 , .. ., 4 pt 0 qt 0
7) åñëè v i Gk1 � � , v j Gk2 � � , òî ñ âåðîÿòíîñòüþ åäèíèöà v v i j Gk1 2� � � � ,
0 2� �i j k, .
Äîêàçàòåëüñòâî. Íå îãðàíè÷èâàÿ îáùíîñòè, ïðåäïîëîæèì, ÷òî ïîäãðóïïà
ñîäåðæèò îäèí íóëåâîé áëîê èç äâóõ áèòîâ. Äëÿ íóëåâîãî áëîêà áîëüøåé äëèíû
äîêàçàòåëüñòâî ïðîâîäèòñÿ àíàëîãè÷íî. Âûáåðåì ïîäãðóïïó G2 ãðóïïû ( , )Vn � ,
èíäåêñ êîòîðîé ðàâåí 4, òàêèì îáðàçîì, ÷òî åå ýëåìåíòû èìåþò âèä
...
���
n
2
00
áèò
.
Âûïèøåì âñå êëàññû ñìåæíîñòè ïî ýòîé ïîäãðóïïå:
H
n
1
2
00�
...
���
áèò
; H
n
3
2
10�
...
���
áèò
;
H
n
2
2
01�
...
���
áèò
; H
n
4
2
11�
...
���
áèò
.
Ðàññìîòðèì äåéñòâèå îïåðàöèè ìîäóëüíîãî ñëîæåíèÿ â ãðóïïå�
2n íà ýëåìåíòû
ôàêòîð-ãðóïïû ãðóïïû ( , )Vn � ïî âûáðàííîé ïîäãðóïïå G2 îòíîñèòåëüíî îïåðàöèè
ïîáèòîâîãî ñëîæåíèÿ. Òîãäà âåðîÿòíîñòè P v v H v H v Hi j k( / , )1 2 1 2� � � � , ãäå
i j k, , , ,�1 4� , îïèñûâàþòñÿ òàáë. 7, ñèììåòðè÷íîé îòíîñèòåëüíî ãëàâíîé äèàãî-
íàëè, à âåðîÿòíîñòè P v v H v v Hi j( / , )1 2 1 2
� � , ãäå i j k, , , ,�1 4� , îïèñûâàþò-
ñÿ òàáë. 8.
Äîêàæåì ñíà÷àëà ðåçóëüòàòû òàáë. 7. Ðàññìîòðèì äëÿ ïðèìåðà äîêàçà-
òåëüñòâî íåêîòîðûõ âîçìîæíûõ ñëó÷àåâ, ïîñêîëüêó äîêàçàòåëüñòâî îñòàëüíûõ
ñëó÷àåâ ïðîâîäèòñÿ àíàëîãè÷íî.
1. Ïóñòü v v H1 2 1, � , òîãäà âåêòîðû v1 è v2 èìåþò ñëåäóþùèé âèä:
v
n
1
2
00�
...
���
áèò
; v
n
2
2
00�
...
���
áèò
.
94 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
Ò à á ë è ö à 7 . Âåðîÿòíîñòè ïîïàäàíèÿ ñóììû âåêòîðîâ v1 è v2 ïî ìîäóëþ 2n
â ñîîòâåòñòâóþùèé êëàññ ñìåæíîñòè H i , i �1 4, ...,
v H2 1� v H2 2� v H2 3� v H2 4�
v H1 1�
H1
1
H 2
0
H1
0
H 2
1
H1
0
H 2
0
H1
0
H 2
0
H 3
0
H 4
0
H 3
0
H 4
0
H 3
1
H 4
0
H 3
0
H 4
1
v H1 2�
0 1 0 0 0 0 1 0
0 0 1 0 0 1 0 0
v H1 3�
0 0 0 0 1 0 0 1
1 0 0 1 0 0 0 0
v H1 4�
0 0 1 0 0 1 0 0
0 1 0 0 0 0 1 0
Î÷åâèäíî, ÷òî ñóììà ýòèõ âåêòîðîâ ïî v1 ìîäóëþ 2n âñåãäà áóäåò ïîïàäàòü
â ýòîò æå êëàññ ñìåæíîñòè, à èìåííî
P v v H( )1 2 1 1� � � ; P v v H( )1 2 3 0� � � ;
P v v H( )1 2 2 0� � � ; P v v H( )1 2 4 0� � � .
2. Ïóñòü v H1 2� , à v H2 4� . Òîãäà âåêòîðû v1 è v2 èìåþò ñëåäóþùèé âèä:
v
n
1
2
01�
...
���
áèò
; v
n
2
2
11�
...
���
áèò
.
Ñóììà ýòèõ âåêòîðîâ ïî ìîäóëþ 2n âñåãäà áóäåò ïîïàäàòü â êëàññ ñìåæíî-
ñòè H1 , ò.å.
P v v H( )1 2 1 1� � � ; P v v H( )1 2 3 0� � � ;
P v v H( )1 2 2 0� � � ; P v v H( )1 2 4 0� � � .
Äîêàæåì òåïåðü ðåçóëüòàòû òàáë. 8. Äëÿ ïðèìåðà ðàññìîòðèì ñëó÷àé, êîãäà
v H v H1 3 2 3� �, . Òîãäà ýòè âåêòîðû èìåþò âèä
v
n
1
2
10�
...
���
áèò
; v
n
2
2
10�
...
���
áèò
.
Ðàçíîñòü äàííûõ âåêòîðîâ ïî ìîäóëþ 2n âñåãäà áóäåò ïîïàäàòü â êëàññ
ñìåæíîñòè H1 , ò.å.
P v v H( )1 2 1 1
� � ; P v v H( )1 2 3 0
� � ;
P v v H( )1 2 2 0
� � ; P v v H( )1 2 4 0
� � .
Ðàññìîòðèì äåéñòâèå îïåðàöèè ïîáèòîâîãî ñëîæåíèÿ â ãðóïïå Vn íà ýëåìåí-
òû ôàêòîð-ãðóïïû ãðóïïû (�
2n , �) ïî âûáðàííîé ïîäãðóïïå G2 îòíîñèòåëüíî
îïåðàöèè ìîäóëüíîãî ñëîæåíèÿ. Ñëåäóåò îòìåòèòü, ÷òî êëàññû ñìåæíîñòè ïî
ïîäãðóïïå G2 îòíîñèòåëüíî ìîäóëüíîãî ñëîæåíèÿ áóäóò â òî÷íîñòè ñîâïàäàòü
ñ âûïèñàííûìè âûøå êëàññàìè ñìåæíîñòè H1 , H 2 , H 3 , H 4 îòíîñèòåëüíî îïåðà-
öèè ïîáèòîâîãî ñëîæåíèÿ. Òîãäà âåðîÿòíîñòè P v v H v H v Hi j k( / , )1 2 1 2� � � � ,
ãäå i j k, , , ,�1 4� , îïèñûâàþòñÿ òàáë. 9, ñèììåòðè÷íîé îòíîñèòåëüíî ãëàâíîé
äèàãîíàëè, à âåðîÿòíîñòè P v v H v v Hi j( / , )1 2 1 2
� � , ãäå i j k, , , ,�1 4� , îïèñû-
âàþòñÿ òàáë. 10.
Äîêàæåì ðåçóëüòàòû òàáë. 9. Ðàññìîòðèì äîêàçàòåëüñòâî íåêîòîðûõ âîçìîæ-
íûõ ñëó÷àåâ.
1. Ïóñòü v v H1 2 1, � , òîãäà âåêòîðû v1 è v2 èìåþò ñëåäóþùèé âèä:
v
n
1
2
00�
...
���
áèò
; v
n
2
2
00�
...
���
áèò
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 95
Ò à á ë è ö à 8 . Âåðîÿòíîñòè ïîïàäàíèÿ ðàçíîñòè âåêòîðîâ v1 è v2 ïî ìîäóëþ
2n â ñîîòâåòñòâóþùèé êëàññ ñìåæíîñòè H i , i �1 4, ...,
v v H i1 2, �
Âåðîÿòíîñòè ïîïàäàíèÿ â H i
H1 H 2 H 3 H 4
H i , i � 1 , ... , 4 1 0 0 0
Î÷åâèäíî, ÷òî ïîáèòîâàÿ ñóììà ýòèõ âåêòîðîâ âñåãäà áóäåò ïîïàäàòü â ýòîò
æå êëàññ ñìåæíîñòè, ò.å.
P v v H( )1 2 1 1� � � ; P v v H( )1 2 3 0� � � ;
P v v H( )1 2 2 0� � � ; P v v H( )1 2 4 0� � � .
2. Ïóñòü v H1 2� , v H2 4� . Òîãäà âåêòîðû v1 è v2 èìåþò ñëåäóþùèé âèä:
v
n
1
2
01�
...
���
áèò
; v
n
2
2
11�
...
���
áèò
.
Ïîáèòîâàÿ ñóììà ýòèõ âåêòîðîâ â îòëè÷èå îò îïåðàöèè ñëîæåíèÿ ïî ìîäóëþ
2n âñåãäà áóäåò ïîïàäàòü â êëàññ ñìåæíîñòè H 3 , ò.å.
P v v H( )1 2 1 0� � � ; P v v H( )1 2 3 1� � � ;
P v v H( )1 2 2 0� � � ; P v v H( )1 2 4 0� � � .
Äîêàæåì ðåçóëüòàòû òàáë. 10. Äëÿ ïðèìåðà ðàññìîòðèì ñëåäóþùèé ñëó÷àé,
êîãäà v H v H1 3 2 3� �, . Òîãäà ýòè âåêòîðû èìåþò âèä
v
n
1
2
10�
...
���
áèò
; v
n
2
2
10�
...
���
áèò
.
Ïîáèòîâàÿ ðàçíîñòü äàííûõ âåêòîðîâ, òàê æå êàê è ðàçíîñòü ïî ìîäóëþ 2n ,
âñåãäà ïîïàäàåò â êëàññ ñìåæíîñòè H1 , ò.å.
P v v H( )1 2 1 1
� � ; P v v H( )1 2 3 0
� � ;
P v v H( )1 2 2 0
� � ; P v v H( )1 2 4 0
� � .
Òåîðåìà äîêàçàíà.
96 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
Ò à á ë è ö à 9 . Âåðîÿòíîñòè ïîïàäàíèÿ ïîáèòîâîé ñóììû âåêòîðîâ v1 è v2
â ñîîòâåòñòâóþùèé êëàññ ñìåæíîñòè H i , i �1 4, ... ,
v H2 1� v H2 2� v H2 3� v H2 4�
v H1 1�
H1
1
H 2
0
H1
0
H 2
1
H1
0
H 2
0
H1
0
H 2
0
H 3
0
H 4
0
H 3
0
H 4
0
H 3
1
H 4
0
H 3
0
H 4
1
v H1 2�
0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 0
v H1 3�
0 0 0 0 1 0 0 1
1 0 0 1 0 0 0 0
v H1 4�
0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 0
Ò à á ë è ö à 1 0 . Âåðîÿòíîñòè ïîïàäàíèÿ ïîáèòîâîé ðàçíîñòè âåêòîðîâ v1 è v2
â ñîîòâåòñòâóþùèé êëàññ ñìåæíîñòè H i , i �1 4, ...,
v v H i1 2, �
Âåðîÿòíîñòè ïîïàäàíèÿ â H i
H1 H 2 H 3 H 4
H i , i � 1 , ... , 4 1 0 0 0
Èç äàííîé òåîðåìû ìîæíî ñäåëàòü ñëåäóþùèé âûâîä: åñëè ïîäãðóïïà èìååò
ñòðóêòóðó, îïèñàííóþ â ï. á) ëåììû 1, ò.å. äëÿ íåêîòîðîãî k n� 0, ..., ýëåìåíòû
ýòîé ïîäãðóïïû èìåþò âèä
... ... ,
��� ���
n k k
áèò áèò
0 0
òî îïåðàöèÿ ïîáèòîâîãî (ìîäóëüíîãî) ñëîæåíèÿ ñîõðàíÿåò ñòðóêòóðó ñîîòâåò-
ñòâóþùåé ôàêòîð-ãðóïïû îòíîñèòåëüíî ìîäóëüíîãî (ïîáèòîâîãî) ñëîæåíèÿ.
ÇÀÊËÞ×ÅÍÈÅ
Ðåçóëüòàòû, ïîëó÷åííûå â äàííîé ñòàòüå, õàðàêòåðèçóþò ïåðåìåøèâàþùèå
ñâîéñòâà îïåðàöèé ïîáèòîâîãî è ìîäóëüíîãî ñëîæåíèÿ, çàäàííûõ íà îäíîì
íîñèòåëå. Íàèáîëåå èíòåðåñíûì ÿâëÿåòñÿ òîò ôàêò, ÷òî äåéñòâèå îïåðàöèè ìî-
äóëüíîãî ñëîæåíèÿ íà ôàêòîð-ãðóïïó îòíîñèòåëüíî îïåðàöèè ïîáèòîâîãî ñëî-
æåíèÿ ñóùåñòâåííî çàâèñèò îò âûáîðà ïîäãðóïïû â ( , )Vn � , à îïåðàöèÿ ïîáè-
òîâîãî ñëîæåíèÿ âñåãäà ñîõðàíÿåò ñòðóêòóðó ñîîòâåòñòâóþùåé ôàêòîð-ãðóïïû
ïî ëþáîé ïîäãðóïïå â (�
2n , � ).
Äàííûå ðåçóëüòàòû ïîêàçûâàþò ïîòåíöèàëüíóþ âîçìîæíîñòü ïðèìåíåíèÿ
àòàêè ãîìîìîðôèçìîâ (ãðóïïîâîé àòàêè) ïðè íåêîòîðûõ äîïîëíèòåëüíûõ óñëîâè-
ÿõ â òîì ñëó÷àå, êîãäà â ðàóíäîâûõ ôóíêöèÿõ áëî÷íîãî øèôðà èñïîëüçóþòñÿ ðàç-
íûå îïåðàöèè, íàïðèìåð â øèôðàõ «Êàëèíà», «Ìóõîìîð» è íåêîòîðûõ äðóãèõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ø å ì ÿ ê è í à Î .  . Î ïåðåìåøèâàþùèõ ñâîéñòâàõ îïåðàöèé â êîíå÷íîì ïîëå // Òð. Âîñüìîé
Îáùåðîñ. íàó÷. êîíô. «Ìàòåìàòèêà è áåçîïàñíîñòü èíôîðìàöèîííûõ òåõíîëîãèé» (ÌàÁÈÒ-09),
30 îêò. — 2 íîÿá. 2009. — Ì.: ÌÖÍÌÎ, 2010. — 2. — C. 87–90.
2. Ã î ð ÷ è í ñ ê è é Þ . Í . Î ãîìîìîðôèçìàõ ìíîãîîñíîâíûõ óíèâåðñàëüíûõ àëãåáð â ñâÿçè ñ êðèïòî-
ãðàôè÷åñêèìè ïðèìåíåíèÿìè // Òð. ïî äèñêðåò. ìàòåìàòèêå. — Ì.: ÒÂÏ, 1997. — 1. — Ñ. 67–84.
3. à î ð ÷ è í ñ ê è é Þ . Í . Ñòîõàñòè÷åñêèå àëãåáðû // Òàì æå. — 2. — Ñ. 55–87.
4. Ã Î Ñ Ò 28147–89. Ñèñòåìû îáðàáîòêè èíôîðìàöèè. Çàùèòà êðèïòîãðàôè÷åñêàÿ. Àëãîðèòì
êðèïòîãðàôè÷åñêîãî ïðåîáðàçîâàíèÿ. — Ì.: Ãîññòàíäàðò ÑÑÑÐ, 1989. — 28 ñ.
5. Ã î ð á å í ê î È . Ä . , T î ö ü ê è é Î . Ñ . , Ê à ç ü ì ³ í à Ñ . Â . Ïåðñïåêòèâíèé áëîêîâèé øèôð
«Êàëèíà» — îñíîâí³ ïîëîæåííÿ òà ñïåöèô³êàö³ÿ // Ïðèêëàä. ðàä³îåëåêòðîí³êà. — 2007. — 6, ¹ 2. —
Ñ. 195–208.
6. L a i X . , M a s s e y J . L . , M u r p h y S . Markov ciphers and differential cryptanalysis // Adv. in
Cryptology — EUROCRYPT’91: Proc. — Berlin: Springer-Verlag, 1991. — P. 17–38.
7. B i h a m E . , S h a m i r A . Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. — 1991.
— 4, N 1. — P. 3–72.
8. B e r s o n T . A . Differential cryptanalysis mod 232 with applications to MD5 // Adv. in Cryptology. —
CRYPTO’98 (LNCS 372): Proc. — New York: Springer-Verlag, Inc., 1999. — P. 95–103.
9. Ê î â à ë ü ÷ ó ê Ë .  . Ïîñòðîåíèå âåðõíèõ îöåíîê ñðåäíèõ âåðîÿòíîñòåé öåëî÷èñëåííûõ
äèôôåðåíöèàëîâ êîìïîçèöèè êëþ÷åâîãî ñóììàòîðà, áëîêà ïîäñòàíîâêè è îïåðàòîðà ñäâèãà //
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — ¹ 6. — C. 89–96.
Ïîñòóïèëà 19.01.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 97
|