Численные методы решения задачи о математическом сейфе
Приведены численные методы решения задачи о математическом сейфе с произвольным конечным числом позиций замков. Методы базируются на TSS-алгоритмах построения множества базисных решений систем линейных диофантовых уравнений в конечных полях и кольцах. Наведено чисельні методи розв’язання задачі про...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2019 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/181027 |
| 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: | Численные методы решения задачи о математическом сейфе / С.Л. Крывый // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 18-34. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859866028262031360 |
|---|---|
| author | Крывый, С.Л. |
| author_facet | Крывый, С.Л. |
| citation_txt | Численные методы решения задачи о математическом сейфе / С.Л. Крывый // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 18-34. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Приведены численные методы решения задачи о математическом сейфе с произвольным конечным числом позиций замков. Методы базируются на TSS-алгоритмах построения множества базисных решений систем линейных диофантовых уравнений в конечных полях и кольцах.
Наведено чисельні методи розв’язання задачі про математичний сейф з довільним скінченним числом позицій засувів. Методи ґрунтуються на TSS-алгоритмах побудови множини базисних розв’язків систем лінійних діофантових рівнянь в скінченних полях і кільцях.
The numerical metods to solve problems of mathematical safe with an arbitrary finite number of position of bolts is presented. The basis of the methods are TSS-algorithms for solving systems of linear Diophantine equations in finite fields and rings.
|
| first_indexed | 2025-12-07T15:48:27Z |
| format | Article |
| fulltext |
ÓÄÊ 51.681.3
Ñ.Ë. ÊÐÛÂÛÉ
×ÈÑËÅÍÍÛÅ ÌÅÒÎÄÛ ÐÅØÅÍÈß ÇÀÄÀ×È
Î ÌÀÒÅÌÀÒÈ×ÅÑÊÎÌ ÑÅÉÔÅ
Àííîòàöèÿ. Ïðèâåäåíû ÷èñëåííûå ìåòîäû ðåøåíèÿ çàäà÷è î ìàòåìàòè÷åñ-
êîì ñåéôå ñ ïðîèçâîëüíûì êîíå÷íûì ÷èñëîì ïîçèöèé çàìêîâ. Ìåòîäû áà-
çèðóþòñÿ íà TSS-àëãîðèòìàõ ïîñòðîåíèÿ ìíîæåñòâà áàçèñíûõ ðåøåíèé ñèñ-
òåì ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé â êîíå÷íûõ ïîëÿõ è êîëüöàõ.
Êëþ÷åâûå ñëîâà: äèîôàíòîâûå óðàâíåíèÿ, êîíå÷íûå ïîëÿ, êîíå÷íûå êîëü-
öà, ñèñòåìû ëèíåéíûõ óðàâíåíèé, áàçèñ ðåøåíèé.
ÂÂÅÄÅÍÈÅ
Ïåðâîå óïîìèíàíèå çàäà÷è î ìàòåìàòè÷åñêîì ñåéôå áûëî â ðàáîòå [1]. Ìàòåìà-
òè÷åñêèì ñåéôîì íàçûâàåòñÿ ñèñòåìà Z z z zn� ( , , , )1 2 � âçàèìîñâÿçàííûõ çàì-
êîâ, êîãäà ïðè ïîâîðîòå êëþ÷à â îäíîì çàìêå òàêîé æå ïîâîðîò ïðîèñõîäèò è
â çàìêàõ, ñâÿçàííûõ ñ äàííûì. Ìàòåìàòè÷åñêèé ñåéô ìîæåò çàäàâàòüñÿ äâóìÿ
ñïîñîáàìè: ñ ïîìîùüþ ïðÿìîóãîëüíîé ìàòðèöû, ýëåìåíòû êîòîðîé ñîîòâåòñòâó-
þò çàìêàì, à çíà÷åíèÿ åå ýëåìåíòîâ — ïîçèöèÿì çàìêîâ, ò.å. â âèäå ìàòðèöû
Z zij� | | | | , i m j n� �1 1, , , , ,� � , à òàêæå ñ ïîìîùüþ ãðàôà, âåðøèíû êîòîðîãî
ñîîòâåòñòâóþò çàìêàì. Ïðè ìàòðè÷íîì çàäàíèè ìàòåìàòè÷åñêîãî ñåéôà êàæäûé
çàìîê zij âçàèìîñâÿçàí ñ òåìè çàìêàìè, êîòîðûå ðàñïîëîæåíû â òîé æå ñòðîêå
è òîì æå ñòîëáöå. À ïðè çàäàíèè ìàòåìàòè÷åñêîãî ñåéôà ñ ïîìîùüþ ãðàôà
ñâÿçàííûìè ñ äàííûì çàìêîì ÿâëÿþòñÿ òå çàìêè, êîòîðûå ñîîòâåòñòâóþò ðàñ-
ïîëîæåííûì â ñìåæíûõ âåðøèíàõ. Èñõîäíîå ñîñòîÿíèå ñåéôà Z çàäàåòñÿ ìàòðè-
öåé B bij� | | | | . Êàæäûé çàìîê ìîæåò íàõîäèòüñÿ â îäíîé èç íåñêîëüêèõ ïîçèöèé.
Âñåõ âîçìîæíûõ ïîçèöèé êîíå÷íîå ÷èñëî: 0 1 1, , ,� k � . Çàìîê îòêðûò, êîãäà îí
íàõîäèòñÿ â ïîçèöèè 0.  ëþáîé äðóãîé ïîçèöèè çàìîê ñ÷èòàåòñÿ çàêðûòûì.
Åñëè â êàêîì-òî çàìêå îñóùåñòâëÿåòñÿ ïîâîðîò êëþ÷à, òî âñå çàìêè, êîòîðûå
ñâÿçàíû ñ äàííûì çàìêîì, óâåëè÷èâàþò ñâîè ïîçèöèè íà åäèíèöó ïî ìîäóëþ k .
1. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Íåîáõîäèìî ðåøèòü ñëåäóþùóþ çàäà÷ó. Èñõîäÿ èç íà÷àëüíîãî ñîñòîÿíèÿ ñåé-
ôà, ïðåäñòàâëåííîãî ìàòðèöåé B bij� | | | | , ãäå b kij � �{ }0 1 1, , ,� , íàéòè òàêóþ
ïîñëåäîâàòåëüíîñòü çàìêîâ è ÷èñëî ïîâîðîòîâ êëþ÷à â íèõ, ÷òîáû ñåéô ïåðå-
øåë â ïîëîæåíèå îòêðûòîãî, ò.å. êîãäà âñå çàìêè íàõîäÿòñÿ â ïîçèöèè 0.
Ïðèâåäåì âíà÷àëå çàäàíèå ìàòåìàòè÷åñêîãî ñåéôà ñ ïîìîùüþ ìàòðèöû è ìå-
òîäû ðåøåíèÿ çàäà÷è íàä ðàçëè÷íûìè îáëàñòÿìè.
Ðàññìîòðèì ìàòåìàòè÷åñêóþ ïîñòàíîâêó çàäà÷è. Ïóñòü ìàòðèöà X xij� | | | |
ÿâëÿåòñÿ ðåøåíèåì çàäà÷è, ãäå xij — ÷èñëî ïîâîðîòîâ êëþ÷à â çàìêå zij . Òîãäà
óñëîâèå òîãî, ÷òî ýëåìåíò bij ïðåîáðàçóåòñÿ ìàòðèöåé X â íóëü, ïðåäñòàâëÿåòñÿ
ñîîòíîøåíèåì
s
n
is
s s i
m
sj ijx x b k
� � �
� �� � �
1 1
0
,
( )mod , (1)
ãäå i m j n� �1 1, , , , ,� � .
Îáîçíà÷èì x x x x x x xn n m mn� ( , , , , , , , , , )11 1 21 2 1� � � � âåêòîð-ñòîëáåö,
ïîëó÷åííûé èç ìàòðèöû X ïîñëåäîâàòåëüíîé çàïèñüþ åe ñòðîê. Àíàëîãè÷íî èç
ìàòðèöû B ïîëó÷èì âåêòîð-ñòîëáåö b . Êðîìå òîãî, ïóñòü � n — ìàòðèöà ðàçìåðà
n n , ñîñòîÿùàÿ èç åäèíèö, En — åäèíè÷íàÿ ìàòðèöà òîãî æå ðàçìåðà. Òîãäà ðå-
øåíèå çàäà÷è î ìàòåìàòè÷åñêîì ñåéôå ñâîäèòñÿ ê ïðåîáðàçîâàíèþ (1) äëÿ âñåé
18 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
© Ñ.Ë. Êðûâûé, 2019
ìàòðèöû B è çàïèñûâàåòñÿ â âèäå ñèñòåìû óðàâíåíèé
Ax b k� � 0 ( )mod , (2)
ãäå ìàòðèöà A ðàçìåðà mn mn ñîñòîèò èç m2 êëåòîê:
A
E E E
E E E
E E E
E E E
n n n n
n n n n
n n n n
n n n n
�
�
�
�
�
�
� �
� �
� �
� � � � � �
� �
�
�
�
�
�
�
�
�
�
. (3)
Äàëåå ðàññìàòðèâàåòñÿ çàäà÷à î ñåéôå íàä êîíå÷íûìè êîëüöàìè è ïîëÿìè,
à òàêæå åå âàðèàöèè íàä ýòèìè îáëàñòÿìè.
Êîëüöîì âû÷åòîâ ïî ìîäóëþ ñîñòàâíîãî ÷èñëà m íàçûâàåòñÿ àëãåáðà
Z A mm � � �( , , ,{ }0 1 1� , � � � � � �{ }, , , , , )1 0 1 , ãäå � è � åñòü áèíàðíûå àññîöèà-
òèâíûå, êîììóòàòèâíûå îïåðàöèè ñëîæåíèÿ è óìíîæåíèÿ ïî ìîäóëþ m, ñâÿçàí-
íûå çàêîíîì äèñòðèáóòèâíîñòè, îïåðàöèÿ � è îïåðàöèÿ �1 ÿâëÿþòñÿ óíàðíûìè
îïåðàöèÿìè âçÿòèÿ ïðîòèâîïîëîæíîãî è îáðàòíîãî ýëåìåíòîâ îòíîñèòåëüíî îïå-
ðàöèé � è � ñîîòâåòñòâåííî, 0 è 1 — íóëüàðíûå îïåðàöèè — àääèòèâíûé íóëü è
ìóëüòèïëèêàòèâíàÿ åäèíèöà [2].
Êîëüöî âû÷åòîâ Zm íàçûâàåòñÿ ïðèìàðíûì, åñëè ìîäóëü m ÿâëÿåòñÿ ñòå-
ïåíüþ ïðîñòîãî ÷èñëà p, ò.å. m pt� , ãäå t �1, t N� . Ïîñêîëüêó m íå îáÿçàòåëüíî
ïðîñòîå ÷èñëî, òî ñðàâíåíèå ax b m� ( )mod â êîëüöå Zm ïðè a � 0 íå âñåãäà èìå-
åò ðåøåíèå. Ðåøåíèå âîçìîæíî, åñëè ÍÎÄ ( , )a m �1 èëè ÍÎÄ ( , )a m d� è d —
äåëèòåëü ÷èñëà b.
Ïîëåì âû÷åòîâ ïî ìîäóëþ m íàçûâàåòñÿ àññîöèàòèâíî-êîììóòàòèâíîå êîëü-
öî âû÷åòîâ, â êîòîðîì ìóëüòèïëèêàòèâíàÿ ïîëóãðóïïà ÿâëÿåòñÿ ãðóïïîé. Èçâåñò-
íî, ÷òî êîëüöî âû÷åòîâ ïî ìîäóëþ m áóäåò ïîëåì, åñëè ìîäóëü m — ïðîñòîå ÷èñ-
ëî. Ïîëå âû÷åòîâ îáîçíà÷èì �m .
Äîïîëíåíèåì ýëåìåíòà a â êîëüöå Zm èëè â ïîëå � p íàçûâàåòñÿ ýëåìåíò b
òàêîé, ÷òî a b m� � 0 ( )mod . Î÷åâèäíî, ÷òî ñðàâíåíèÿ a x a xj j11 1 1� � �� �
� � �a x mn n1 0 ( )mod è a x b x a x mj j n n11 1 1 1 0� � � � �� � ( )mod ýêâèâàëåíòíû,
ò.å. êàæäîå ðåøåíèå ïåðâîãî óðàâíåíèÿ ÿâëÿåòñÿ ðåøåíèåì âòîðîãî è íàîáîðîò.
Åñëè m p� — ïðîñòîå ÷èñëî, òî â ïîëå � p ïðè a � 0 ñðàâíåíèå
ax b p� ( )mod âñåãäà èìååò ðåøåíèå è ýòî ðåøåíèå åäèíñòâåííî.
Ðàññìîòðèì ïîëå � pk ïî ìîäóëþ íåïðèâîäèìîãî ïîëèíîìà q x( ) ñòåïåíè k
íàä ïîëåì �p . Ïîñòðîåíèå òàêîãî ïîëÿ ñâîäèòñÿ ê âû÷èñëåíèþ îñòàòêîâ îò äåëå-
íèÿ ïîëèíîìîâ, ïîëó÷àåìûõ ïðè óìíîæåíèè ýëåìåíòîâ ïîëÿ (ïîëèíîìîâ ñòåïå-
íè, ìåíüøåé k) íà íåïðèâîäèìûé íàä ïîëåì � p ïîëèíîì q x( ). Ïîëå �
pk ñîñòîèò
èç pk ýëåìåíòîâ è èìååò õàðàêòåðèñòèêó p.  êà÷åñòâå ïðèìåðîâ òàêîãî òèïà ïî-
ëåé ïðèâåäåì òàáëèöû îïåðàöèé ïîëåé �
22 è �
32 , êîòîðûå ñòðîÿòñÿ ñ ïîìîùüþ
íåïðèâîäèìûõ ïîëèíîìîâ x x2 1� � è x x2 2� � íàä ïîëÿìè �2 è �3 ñîîòâåò-
ñòâåííî è çàäàíû òàáëèöàìè ñëîæåíèÿ (òàáë. 1, 3) è òàáëèöàìè óìíîæåíèÿ
(òàáë. 2, 4). (Ïîñòðîåíèå òàêèõ ïîëåé äåòàëüíî îïèñàíî â [2].) Â òàáë. 1, 2 ïîëè-
íîì x îáîçíà÷åí ÷èñëîì 2, à ïîëèíîì x �1 — ÷èñëîì 3.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 19
Ò à á ë è ö à 1
� 0 1 2 3
0 0 1 2 3
1 1 0 3 2
2 2 3 0 1
3 3 2 1 0
Ò à á ë è ö à 2
� 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 3 1
3 0 3 1 2
 òàáë. 3, 4 ïîëèíîì x îáîçíà÷åí ÷èñëîì 3, ïîëèíîì x �1 — ÷èñëîì 4, ïîëè-
íîì x �2 — ÷èñëîì 5, ïîëèíîì 2x — ÷èñëîì 6, ïîëèíîì 2 1x � — ÷èñëîì 7, ïîëè-
íîì 2 2x � — ÷èñëîì 8.
2. TSS-ÌÅÒÎÄ ÐÅØÅÍÈß ÑÈÑÒÅÌ ËÈÍÅÉÍÛÕ ÄÈÎÔÀÍÒÎÂÛÕ ÓÐÀÂÍÅÍÈÉ
TSS-ìåòîä ðåøåíèÿ ñèñòåì ëèíåéíûõ îäíîðîäíûõ äèîôàíòîâûõ óðàâíåíèé (ÑËÎÄÓ)
è íåîäíîðîäíûõ óðàâíåíèé (ÑËÍÄÓ) â êîíå÷íûõ êîëüöàõ è ïîëÿõ ðàññìàòðèâàëñÿ
â ðàáîòàõ [3–5]. Ïðèâåäåì êðàòêîå îïèñàíèå TSS-ìåòîäà ðåøåíèÿ ÑËÍÄÓ.
Ïóñòü äàíà ÑËÍÄÓ
SN
L x a x a x b
L x a x a x b
q q
q q�
� � � �
� � � �
1 11 1 1 1
2 21 1 2 2
( ) ,
( ) ,
�
�
�������������
�L x a x a x bs s sq q s( ) � � � �
�
�
��
�
�
� 1 1
(4)
íàä ïîëåì � p è e1 1 0 0 0� ( , , , , )� , e2 0 1 0 0� ( , , , , ),� � , eq � ( , , , , )0 0 0 1� —
åäèíè÷íûå âåêòîðû èç ìíîæåñòâà � p
q . Ñèñòåìà
S
L x a x a x
L x a x a x
q q
q q�
� � � �
� � � �
1 11 1 1
2 21 1 2
0
0
( ) ,
( ) ,
�
�
�������������
�L x a x a xs s sq q( ) � � � �
�
�
��
�
�
� 1 1 0
(5)
íàçûâàåòñÿ ÑËÎÄÓ è ñîîòâåòñòâóåò âûøåïðèâåäåííîé ÑËÍÄÓ SN . Ïîñêîëüêó
ðåøåíèå ÑËÍÄÓ ñâîäèòñÿ ê ðåøåíèþ ÑËÎÄÓ, òî äîñòàòî÷íî ðàññìîòðåòü
ñïîñîá ðåøåíèÿ ÑËÎÄÓ.
Âîçüìåì ïåðâîå óðàâíåíèå
L x a x a x a xq q1 11 1 12 2 1 0( ) � � � � �� (6)
ñèñòåìû (5). Äîïóñòèì, ÷òî a j1 0� , çàìåíèì ýòîò êîýôôèöèåíò åãî äîïîëíåíè-
åì � b j1 . Ïîñòðîèì ìíîæåñòâî ðåøåíèé B e b ak j k1 1 10 0 0 0� �{ ( , , , , , , , ,� �
0 0 0, ,� }� M , ãäå M e L er r0 1 0� �{ }: ( ) , a k1 0� , à b j1 ÿâëÿåòñÿ k-é êîîðäèíà-
òîé â âåêòîðàõ èç B1.
Èíûìè ñëîâàìè, ìíîæåñòâî B1 ñòðîèòñÿ ïóòåì êîìáèíèðîâàíèÿ äîïîëíåíèÿ
ïåðâîãî íåíóëåâîãî êîýôôèöèåíòà, âçÿòîãî ñ îòðèöàòåëüíûì çíàêîì, ñ îñòàëüíû-
ìè íåíóëåâûìè êîýôôèöèåíòàìè è ïîïîëíåííîå âåêòîðàìè êàíîíè÷åñêîãî áàçè-
ñà, êîòîðûå ñîîòâåòñòâóþò íóëåâûì êîýôôèöèåíòàì ËÎÄÓ (6). Ïîñòðîåííîå òà-
êèì îáðàçîì ìíîæåñòâî íàçîâåì TSS . Î÷åâèäíî, ÷òî âåêòîðû èç ìíîæåñòâà B1
ÿâëÿþòñÿ ðåøåíèÿìè ËÎÄÓ (6).
Âîçüìåì ôóíêöèþ L x a x a xq q2 21 1 2( ) � � �� è ðàññìîòðèì ËÎÄÓ âèäà
L e y L e y L e ym m2 1 1 2 2 2 2 0( ) ( ) ( )� � � �� . (7)
20 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
Ò à á ë è ö à 3
� 0 1 2 3 4 5 6 7 8
0 0 1 2 3 4 5 6 7 8
1 1 2 0 4 5 3 7 8 6
2 2 0 1 5 3 4 8 6 7
3 3 4 5 6 7 8 0 1 2
4 4 5 3 7 8 6 1 2 0
5 5 3 4 8 6 7 2 0 1
6 6 7 8 0 1 2 3 4 5
7 7 8 6 1 2 0 4 5 3
8 8 6 7 2 0 1 5 3 4
Ò à á ë è ö à 4
* 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8
2 0 2 1 6 8 7 3 5 4
3 0 3 6 7 1 4 5 8 2
4 0 4 8 1 5 6 2 3 7
5 0 5 7 4 6 2 8 1 3
6 0 6 3 5 2 8 7 4 1
7 0 7 5 8 3 1 4 2 6
8 0 8 4 2 7 3 1 6 5
Çàìåòèì, ÷òî åñëè âñå L ei2 0( ) � , òî óðàâíåíèå L x2 ( ) ëèíåéíî âûðàæàåòñÿ ÷å-
ðåç L x1 ( ) è åãî ìîæíî óäàëèòü èç ÑËÎÄÓ S . Ïîýòîìó áóäåì ïðåäïîëàãàòü,
÷òî âñå óðàâíåíèÿ â S ëèíåéíî íåçàâèñèìû.
Íàéäåì TSS-ìåòîäîì ìíîæåñòâî � � �B r r rm{ }1 2 1, , ,� ðåøåíèé ËÎÄÓ (7) è ïî-
ñòðîèì ïî âåêòîðàì èç �B ñîîòâåòñòâóþùèå êîìáèíàöèè âåêòîðîâ èç B1. Îáîçíà÷èì
ýòî ìíîæåñòâî M s s sm� �{ }1 2 1, , ,� . Ïðîäîëæàÿ ýòó ïðîöåäóðó, ïîñòðîèì äëÿ âñåé
ÑËÎÄÓ S ìíîæåñòâî ðåøåíèé M . Â ðàáîòå [5] áûëî äîêàçàíî, ÷òî TSS-ìíîæåñòâî
M , ïîñòðîåííîå òàêèì ñïîñîáîì äëÿ ÑËÎÄÓ S âèäà (5), ÿâëÿåòñÿ áàçèñîì ìíîæåñ-
òâà âñåõ ðåøåíèé ýòîé ÑËÎÄÓ.
Ñëîæíîñòü ïîñòðîåíèÿ áàçèñà ïðîïîðöèîíàëüíà âåëè÷èíå sl3 , ãäå s — ÷èñëî
óðàâíåíèé â ÑËÎÄÓ, l t q� max ( , ), t p� log — êîëè÷åñòâî äâîè÷íûõ ðàçðÿäîâ
ìîäóëÿ p, à q — êîëè÷åñòâî íåèçâåñòíûõ â CËÎÄÓ.
Ïðè îöåíêå ñëîæíîñòè ýëåìåíòàðíûìè ñ÷èòàþòñÿ îïåðàöèè ñëîæåíèÿ è âû-
÷èòàíèÿ [3, 4].
Ìåòîä ïîñòðîåíèÿ TSS (TSS-ìåòîä) ðåøåíèÿ ÑËÍÄÓ â ïîëå � p ñâîäèòñÿ
ê ðåøåíèþ ÑËÎÄÓ. Äåéñòâèòåëüíî, ïóñòü äàíà ÑËÍÄÓ
S
L x a x a x b
L x a x a x b
n n
n n�
� � � �
� � � �
1 11 1 1 1
2 21 1 2 2
( ) ,
( ) ,
�
�
�������������
�L x a x a x bs s sn n s( ) ,� � � �
�
�
�
�
�
1 1
(mod )p (8)
ãäå aij , bi , xi p�� , i s�1, ,� , j n�1, ,� , s n� . Ïîñêîëüêó îáå ÷àñòè óðàâíåíèÿ
ìîæíî óìíîæàòü íà ÷èñëî, à ñàìè óðàâíåíèÿ ñêëàäûâàòü è âû÷èòàòü, òî ïðå-
îáðàçóåì S ê âèäó (ïîëàãàÿ, ÷òî bs � 0)
� �
� � � � � � �
� � � � � �
S
L x a x a x
L x a x a x
n n
n n
1 11 1 1
2 21 1 2
0( ) ,
( )
�
� �
� � � � � � �� � �
0
01 11 1 1
,
( ) ,
(
�������������
�L x a x a x
L
s s s n n
s x a x a x bs sn n s) .� � � �
�
�
�
�
�
�
�
1 1 �
( )mod p (9)
Ïóñòü � � � � �B e e em{ }1 2, , ,� — áàçèñ ìíîæåñòâà ðåøåíèé ÑËÎÄÓ, ñîñòîÿùåé èç
ïåðâûõ s�1 óðàâíåíèÿ ñèñòåìû �S , à B e e ek� { }1 2, , ,� — áàçèñ ìíîæåñòâà ðå-
øåíèé ÑËÎÄÓ, êîòîðàÿ ñîîòâåòñòâóåò �S . Ïîñòðîèì óðàâíåíèå L e ys ( )� �1 1 �
� � � �L e y bs m m s( ) . Åñëè âñå L es i( ) � 0, òî äàííîå óðàâíåíèå íå èìååò ðåøå-
íèé, à çíà÷èò, íå èìååò ðåøåíèé è èñõîäíàÿ ÑËÍÄÓ (â ýòîì ñëó÷àå L xs ( ) ëè-
íåéíî çàâèñèò îò � ��L x L xs1 1( ), , ( )� ). Åñëè õîòÿ áû îäíî çíà÷åíèå L es i( ) � 0, òî
ðåøåíèå âñåãäà ñóùåñòâóåò, è åñëè y d dm� ( , , )1 � ýòî ðåøåíèå, òî âåêòîð
x d e d em m
1
1 1� � � � �� ÿâëÿåòñÿ ÷àñòíûì ðåøåíèåì óðàâíåíèÿ L x bs s( ) � . Òîãäà
îáùåå ðåøåíèå ÑËÎÄÓ �S , à çíà÷èò, è ñèñòåìû S , ïðåäñòàâëÿåòñÿ â âèäå
u x b ei i
i
k
� �
�
�1
1
, ãäå e Bi � , i k�1 2, , ,� .
Òàêèì îáðàçîì, èìååò ìåñòî ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 1. ÑËÍÄÓ S , âñå óðàâíåíèÿ êîòîðîé ëèíåéíî íåçàâèñèìû è åå ðàç-
ìåðíîñòü ðàâíà s n , âñåãäà ñîâìåñòíà íàä ïîëåì � p è åå îáùåå ðåøåíèå èìååò
âèä u x b ei i
i
k
� �
�
�1
1
, ãäå x1 — íåêîòîðîå ÷àñòíîå ðåøåíèå S , à ei — áàçèñíûå âåê-
òîðû ìíîæåñòâà ðåøåíèé ÑËÎÄÓ, êîòîðàÿ ñîîòâåòñòâóåò äàííîé ÑËÍÄÓ S .
Ñëîæíîñòü ïîñòðîåíèÿ îáùåãî ðåøåíèÿ ÑËÍÄÓ ïðîïîðöèîíàëüíà âåëè÷èíå
sl3 , ãäå s — êîëè÷åñòâî óðàâíåíèé â ñèñòåìå, l t n� max ( , ), t — êîëè÷åñòâî äâî-
è÷íûõ ðàçðÿäîâ ÷èñëà p, à n — êîëè÷åñòâî íåèçâåñòíûõ â ÑËÍÄÓ [3, 5].
Àíàëîãè÷íî âû÷èñëÿåòñÿ áàçèñ ìíîæåñòâà ðåøåíèé â ïîëå �
pk . Îäíàêî ðå-
àëèçàöèÿ TSS-ìåòîäà â ýòîì ïîëå èìååò íåêîòîðóþ îñîáåííîñòü. Òàê, åñëè â ïîëå
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 21
âû÷åòîâ äëÿ àëãîðèòìà íåîáõîäèìî óêàçàòü òîëüêî ìîäóëü è ìàòðèöó ñèñòåìû,
òî çäåñü êðîìå ìîäóëÿ è ìàòðèöû íåîáõîäèìî óêàçûâàòü òàáëèöû ñëîæåíèÿ è
óìíîæåíèÿ ïîëÿ �
pk (íàïðèìåð, òàáë. 1–4).
Ïðåäñòàâèì TSS-ìåòîä ðåøåíèÿ ÑËÍÄÓ â êîëüöå âû÷åòîâ ïî ìîäóëþ ñî-
ñòàâíîãî ÷èñëà. Ïðèíèìàÿ âî âíèìàíèå ñâîéñòâà êîëüöà Zm , ðàññìîòðèì ÑËÍÄÓ
S
L x a x a x b
L x a x a x b
q q
q q�
� � � �
� � � �
1 11 1 1 1
2 21 1 2 2
( ) ,
( ) ,
�
�
�������������
�L x a x a x bs s sq q s( ) ,� � � �
�
�
��
�
�
� 1 1
( )mod m (10)
ãäå a b Zij i m, � .
Ïóñòü ìîäóëü èìååò ðàçëîæåíèå íà ïðîñòûå ìíîæèòåëè m p p p
k k
r
kr� �
1 2
1 2 .
Òîãäà ñèñòåìå S ñîîòâåòñòâóåò ýêâèâàëåíòíàÿ åé ñèñòåìà èç r s� óðàâíåíèé âèäà
� �
� � � �
� � � �
S
L x a x a x b
L x a x a x b
q q
q q
1 11 1 1 1
2 21 1 2 2
( ) ,
( ) ,
�
�
�������������
�L x a x a x b
p
s s sq q s
k
( ) ,� � � �
�
�
��
�
�
� 1 1
1
1(mod )
( ) ,
( ) ,
L x a x a x b
L x a x a x b
q q
q q
1 11 1 1 1
2 21 1 2 2
� � � �
� � � �
�
�
�������������
�
�
L x a x a x b
p
s s sq q s
k
( ) ,
( )
� � � �
�
�
��
�
�
� 1 1
2
2mod
L x a x a x b
L x a x a x b
q q
q q
1 11 1 1 1
2 21 1 2 2
( ) ,
( ) ,
� � � �
� � � �
�
�
�������������
�L x a x a x b
p
s s sq q s
r
kr
( ) .
( )
� � � �
�
�
��
�
�
�
�
�
1 1
mod
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
(11)
Ýêâèâàëåíòíîñòü ñèñòåì S è �S î÷åâèäíà. Äåéñòâèòåëüíî, åñëè x — ðåøåíèå
ñèñòåìû S , òî îíî áóäåò ðåøåíèåì è êàæäîé ïîäñèñòåìû ïî ìîäóëþ pi
ki , ïî-
ñêîëüêó ìîäóëü m äåëèòñÿ íà êàæäîå èç ÷èñåë pi
ki , i r�1 2, ,� . Åñëè x — ðåøåíèå
ñèñòåìû �S , òî îíî áóäåò ðåøåíèåì êàæäîé åå ïîäñèñòåìû ïî ìîäóëþ pi
ki , à çíà-
÷èò, è ðåøåíèåì ñèñòåìû S ïî ìîäóëþ m, ïîñêîëüêó ÷èñëà pi
ki âçàèìíî ïðîñòû
è èõ ïðîèçâåäåíèå ðàâíî m.
Ïåðåéäåì îò ñèñòåìû �S ê ñèñòåìå îäíîðîäíûõ óðàâíåíèé:
S
L x a x a x b x
L x a x a x
q q
q q
' ' �
� � � � �
� � �
1 11 1 1 1 0
2 21 1 2
0( ) ,
( )
�
� � �
� � � � �
b x
L x a x a x b xs s sq q s
2 0
1 1 0
0
0
,
( ) ,
���������������
�
�
�
��
�
�
�
� � � � �
�
( )
( ) ,
( )
mod p
L x a x a x b x
L x a
k
q q
1
1 11 1 1 1 0
2
1
0�
21 1 2 2 0
1 1
0x a x b x
L x a x a
q q
s s
� � � �
� � �
�
���������������
�
,
( ) sq q s
k
q q
x b x
p
L x a x a x b
� �
�
�
��
�
�
�
� � � �
0
2
1 11 1 1
0
2
,
( )
( )
mod
�
� 1 0
2 21 1 2 2 0
0
0
x
L x a x a x b x
L
q q
s
�
� � � � �
,
( ) ,�
���������������
( ) .
( )
x a x a x b x
p
s sq q s
r
kr
� � � � �
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
1 1 0 0�
mod
�
�
�
�
�
�
�
�
�
�
22 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
Ïóñòü x — ðåøåíèå ñèñòåìû âèäà
S
L x a x a x b x
L x a x a x
q q
q q
1
1 11 1 1 1 0
2 21 1 2
0
�
� � � � �
� � � �
( ) ,
( )
�
� b x
L x a x a x b xs s sq q s
2 0
1 1 0
0
0
�
� � � � �
�
,
( ) .
���������������
�
�
��
�
�
�
( )mod p
k
1
1
Ðàññìîòðèì âåêòîð m x1 , ãäå m m p
k
1 1
1� / , êîòîðûé ÿâëÿåòñÿ ðåøåíèåì ñèñòå-
ìû S' ' . Äåéñòâèòåëüíî, äëÿ âòîðîé ñèñòåìû S 2 , àíàëîãè÷íîé ñèñòåìå ïî ìîäóëþ
p
k
2
2 , ïîëó÷àåì äëÿ ëþáîãî åå óðàâíåíèÿ Li :
L m x m L x m d pi i i
k
( ) ( ) ( )1 1 1 2
0 2� � � mod ,
i s�1 2, ,� , òàê êàê m1 êðàòíî p
k
2
2 .
Àíàëîãè÷íî åñëè y — ðåøåíèå S 2 , òî m y2 , ãäå m m p
k
2 2
2� / , áóäåò ðåøåíèåì
ñèñòåìû S' ' , à çíà÷èò, è äëÿ ëþáîé èç ñèñòåì S S r3 , ,� . Òîãäà îáùåå ðåøåíèå
ñèñòåìû S' ' ïðèíèìàåò âèä
x m x m x m xr r� � � �1 1 2 2 � , (12)
ãäå xi — ðåøåíèå ñèñòåìû S i .
Ïóñòü e m xi i i� , ãäå xi — ðåøåíèå ñèñòåìû S i , i r�1 2, , ,� . Ýòè ðåøåíèÿ ëè-
íåéíî íåçàâèñèìû íàä êîëüöîì Zm è ñîñòàâëÿþò áàçèñ ìíîæåñòâà ðåøåíèé ñèñ-
òåìû [4, 5]. Òàêèì îáðàçîì, äîñòàòî÷íî íàéòè ðåøåíèå ñèñòåìû �S , à ðåøåíèå òà-
êîé ñèñòåìû ñâîäèòñÿ ê ðåøåíèþ ñèñòåì èëè â ïîëÿõ âû÷åòîâ ïî ìîäóëþ ïðî-
ñòîãî ÷èñëà (êîãäà ñòåïåíü k i �1 äëÿ íåêîòîðîãî i r�[ , ]1 è òîãäà êîëüöî Zki
áóäåò
ïîëåì), èëè â ïðèìàðíûõ êîëüöàõ ïî ìîäóëþ ñòåïåíè ïðîñòîãî ÷èñëà.
Ðàññìîòðèì ôîðìèðîâàíèå ìíîæåñòâà ðåøåíèé â ïðèìàðíîì êîëüöå TSS-ìåòî-
äîì. Ïîñêîëüêó ïîñòðîåíèå ìíîæåñòâà ðåøåíèé ñèñòåìû ñâîäèòñÿ ê ðåøåíèþ îäíî-
ãî óðàâíåíèÿ, òî ðàññìîòðèì ËÎÄÓ îáùåãî âèäà íàä ïðèìàðíûì êîëüöîì Zm
a x a x a xn n1 1 2 2 0� � � �� , (13)
ãäå ai , x Zi m� , m p yy� �, 1, y�� (ìíîæåñòâó íàòóðàëüíûõ ÷èñåë), i n�1, ,� .
Åñëè ñðåäè êîýôôèöèåíòîâ ËÎÄÓ åñòü êîýôôèöèåíò, êîòîðûé âçàèìíî ïðîñò ñ ìî-
äóëåì, òî áàçèñ ìíîæåñòâà åãî ðåøåíèé âû÷èñëÿåòñÿ îïèñàííûì âûøå TSS-ìåòî-
äîì. Åñëè ÍÎÄ ( , , , , )a a a m pn
u
1 2 � � òîãäà, ñîêðàùàÿ êîýôôèöèåíò óðàâíåíèÿ
(13) íà pu , ïîëó÷àåì ËÎÄÓ
b x b x b xn n1 1 2 2 0� � � �� (14)
íàä ïðèìàðíûì êîëüöîì Zm ' , ãäå � �m p� , � � y u– .
Ïîëó÷åííîå óðàâíåíèå èìååò ñâîéñòâî: ëþáîå ðåøåíèå ËÎÄÓ (13) áóäåò ðå-
øåíèåì ËÎÄÓ (14). Îáðàòíîå íå èìååò ìåñòà. Äåéñòâèòåëüíî, ïóñòü b1 â (14) âçà-
èìíî ïðîñò ñ ìîäóëåì �m . Òîãäà TSS ýòîãî ËÎÄÓ áóäåò áàçèñîì åãî ìíîæåñòâà
ðåøåíèé:
s b c s b c1 2 2 30 0 0 0 0 0 0 0� �( , , , , , , ), ( , , , , , , )� � ,
s b c s b cn n3 4 10 0 0 0 0 0 0 0� ��( , , , , , , ), , ( , , , , , , )� � � ,
ãäå c b p� �1
� — äîïîëíåíèå êîýôôèöèåíòà b1. Î÷åâèäíûì ðåøåíèåì (13)
â êîëüöå Zm áóäåò âåêòîð s p mn � �( , , , , ) ( /� 0 0 0� ÍÎÄ ( , , , ), , , )a a mn1 0 0� � ,
êîòîðûé íå âûðàæàåòñÿ â âèäå ëèíåéíîé êîìáèíàöèè âåêòîðîâ èç TSS , òàê êàê
c x p� � 0 ( )mod � òîãäà è òîëüêî òîãäà, êîãäà x p� � â ñèëó âçàèìíîé ïðîñòîòû c è p� .
Èìååò ìåñòî ñëåäóþùàÿ òåîðåìà.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 23
Òåîðåìà 2. TSS óðàâíåíèÿ (14), ñðåäè êîýôôèöèåíòîâ êîòîðîãî åñòü êîýô-
ôèöèåíò âçàèìíî ïðîñò ñ ìîäóëåì, äîïîëíåííîå âåêòîðîì s pn � ( , , , , )� 0 0 0� , ñî-
ñòàâëÿåò áàçèñ ìíîæåñòâà ðåøåíèé ËÎÄÓ (13) [4].
 îáùåì ñëó÷àå åñëè ìîäóëü m èìååò ðàçëîæåíèå íà ïðîñòûå ìíîæèòåëè
m p p p
k k
r
kr�
1 2
1 2 � , òî ïðîöåäóðà ïîñòðîåíèÿ áàçèñà ìíîæåñòâà ðåøåíèé ÑËÎÄÓ
â êîëüöå Zm ñâîäèòñÿ ê ðåøåíèþ r ïîäñèñòåì. Êàæäàÿ èç ýòèõ ïîäñèñòåì ðåøà-
åòñÿ íåçàâèñèìî ïî ìîäóëÿì pi
ki è ñòðîÿòñÿ áàçèñû B B Br1 2, , ,� ñîîòâåòñòâåí-
íî. Çàòåì ñòðîèòñÿ áàçèñ B m p B m p B m p B
k k
r
k
r
r� � � �/ / /
1 1 2 2
1 2 � , ãäå qBi
îçíà÷àåò óìíîæåíèå êàæäîãî âåêòîðà èç Bi íà q .
Ïðèíèìàÿ âî âíèìàíèå, ÷òî àðèôìåòè÷åñêàÿ ñëîæíîñòü âûïîëíåíèÿ îïåðà-
öèé ñëîæåíèÿ è âû÷èòàíèÿ â êîëüöå Zm ïðîïîðöèîíàëüíà s m� �log ( )1 , îïåðà-
öèé óìíîæåíèÿ è äåëåíèÿ, êàê è âû÷èñëåíèÿ ÍÎÄ äâóõ ÷èñåë, ìåíüøèõ m, âûðà-
æàåòñÿ âåëè÷èíîé s2 , òî àðèôìåòè÷åñêàÿ ñëîæíîñòü íàõîæäåíèÿ áàçèñà ìíî-
æåñòâà ðåøåíèé ÑËÎÄÓ èìååò òàêèå ñîñòàâëÿþùèå:
� l3 — ðåøåíèå îäíîãî ËÎÄÓ è ðåøåíèå îäíîãî ïðîìåæóòî÷íîãî ËÎÄÓ;
� n l2 3 — âû÷èñëåíèå çíà÷åíèé è ñîêðàùåíèå íà ÍÎÄ L x( ), à òàêæå ïîñòðî-
åíèå êîìáèíàöèé âåêòîðîâ, êîòîðûå ñîñòàâëÿþò áàçèñ ìíîæåñòâà ðåøåíèé
ËÎÄÓ (l n s� max ( , )).
Ñëåäîâàòåëüíî, àðèôìåòè÷åñêàÿ ñëîæíîñòü ïåðåõîäà îò ïðåäûäóùåãî ê ñëå-
äóþùåìó ËÎÄÓ â îäíîé ïîäñèñòåìå ïðîïîðöèîíàëüíà âåëè÷èíå l5 , à ïîñêîëüêó
òàêàÿ ïðîöåäóðà ïîâòîðÿåòñÿ r ðàç, òo ïîëó÷àåì îöåíêó O l( )6 , ãäå l n s r� max ( , , ).
Òàêèì îáðàçîì, èìååò ìåñòî ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 3. Ìíîæåñòâî B, ïîñòðîåííîå TSS-ìåòîäîì, ÿâëÿåòñÿ áàçèñîì ìíî-
æåñòâà ðåøåíèé ÑËOÄÓ S' ' . Àðèôìåòè÷åñêàÿ ñëîæíîñòü ïîñòðîåíèÿ B ïðîïîð-
öèîíàëüíà âåëè÷èíå O l( )6 , ãäå l n s r� max ( , , ).
Ðàññìîòðèì áàçèñ M ìíîæåñòâà ðåøåíèé ÑËÎÄÓ S' ' . Âûäåëèì â ýòîì áàçèñå
ðåøåíèÿ, â êîòîðûõ ïîñëåäíÿÿ êîîðäèíàòà íå ðàâíà íóëþ. Ïóñòü d d dt1 2, , ,� —
çíà÷åíèÿ ýòèõ êîîðäèíàò. Ñîñòàâèì ñðàâíåíèå
c d c d c d mt t1 1 2 2 1� � � �� ( ).mod (15)
Åñëè ýòî ñðàâíåíèå èìååò ðåøåíèå ( , , , )u u ut1 2 � , òî ÑËÍÄÓ �S ñîâìåñòíà
è ëèíåéíàÿ êîìáèíàöèÿ
x u x u x u xt t
1
1 1 2 2� � � ��
ÿâëÿåòñÿ ÷àñòíûì ðåøåíèåì ÑËÍÄÓ �S . Åñëè âûøåïðèâåäåííîå ñðàâíåíèå íå
èìååò ðåøåíèé, òî ÑËÍÄÓ �S òàêæå íå èìååò ðåøåíèé.
Òàêèì îáðàçîì, ïðèâåäåííûé àëãîðèòì ðåøåíèÿ ÑËÍÄÓ â êîëüöå Zm áóäåò
èìåòü ïîëèíîìèàëüíóþ îöåíêó ñëîæíîñòè, åñëè èìååòñÿ ðàçëîæåíèå ìîäóëÿ m íà
ïðîñòûå ìíîæèòåëè.  ïðîòèâíîì ñëó÷àå ñëîæíîñòü ðåøåíèÿ áóäåò âêëþ÷àòü ðåøå-
íèå ïðîáëåìû ôàêòîðèçàöèè ìîäóëÿ m, ÷òî ñíèæàåò ýôôåêòèâíîñòü àëãîðèòìà.
3. PÅØÅÍÈE ÇÀÄÀ×È Î ÌÀÒÅÌÀÒÈ×ÅÑÊÎÌ ÑÅÉÔÅ
Ñëó÷àé 1. ×èñëî ñîñòîÿíèé çàìêîâ p — ïðîñòîå. Ýòî çíà÷èò, ÷òî ðåøåíèÿ
ñèñòåìû (2) íàõîäèì â ïîëå âû÷åòîâ ïî ìîäóëþ p. Ïîñòðîåíèå ýòîãî ðåøåíèÿ
ñ èñïîëüçîâàíèåì TSS-ìåòîäà ïðèâåäåíî â ðàáîòàõ [3, 5]. Ïîýòîìó ðàññìîòðèì
òîëüêî ïðèìåðû, èëëþñòðèðóþùèå ðàáîòó TSS-àëãîðèòìà.
Ïóñòü èìååì ñåéô â ïîëå �3 ñ ìàòðèöåé
B � �
�
�
�
!
2 0 2 2
1 2 2 1
.
Òîãäà b � ( , , , , , , , )2 0 2 2 1 2 2 1 è ñèñòåìà óðàâíåíèé Ax b� � 0 3( )mod èìååò âèä
24 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
Ax b� �
1 1 1 1 1 0 0 0 2
1 1 1 1 0 1 0 0 0
1 1 1 1 0 0 1 0 2
1 1 1 1 0 0 0 1 2
1 0 0 0 1 1 1 1 1
0 1 0 0 1 1 1 1 2
0 0 1 0 1 1 1 1 2
0 0 0 1 1 1 1 1 1
0 3
�
�
�
�
��
�
�
�
�
�
� ( )mod .
Ïðèìåíÿÿ TSS-àëãîðèòì äëÿ ðåøåíèÿ ýòîé ñèñòåìû, íàõîäèì ðåøåíèå CËÍÄÓ
x � ( , , , , , , , )0 2 2 0 0 2 0 0 , ò.å. x11 0� , x12 2� , x13 2� ,
x14 0� , x21 0� , x22 2� , x23 0� , x24 0� .
Ýòîìó ðåøåíèþ ñîîòâåòñòâóþò òàêèå ïðåîáðàçîâàíèÿ ìàòðèöû B :
2 0 2 2
1 2 2 1
212
�
�
�
�
! " �( )x
1 2 1 1
1 1 2 1
213
�
�
�
�
! " �( )x
0 1 0 0
1 1 1 1
2
0 0 0 0
0 0 0 022
�
�
�
�
! " � �
�
�
�
!( )x .
Ýòà æå çàäà÷à ïo ìîäóëþ 13 èìååò ðåøåíèå x11 8� , x12 7� , x13 7� , x14 8� ,
x21 7� , x22 9� , x23 7� , x24 7� , â ÷åì ìîæíî óáåäèòüñÿ íåïîñðåäñòâåííîé
ïðîâåðêîé.
Ñëåäóåò çàìåòèòü, ÷òî â ñëó÷àå, êîãäà ÷èñëî m n� �1, ãäå m n — ðàçìåð
ìàòðèöû B , êðàòíî ìîäóëþ, a ñóììà êoýôôèöèåíòîâ ìàòðèöû B íå êðàòíà ìîäó-
ëþ, òî çàäà÷à î ñåéôå íå èìååò ðåøåíèÿ. Ýòî ñëåäóåò èç òåîðåìû 1. Äåéñòâèòåëü-
íî, çàäà÷à î ñåéôå ñ ìàòðèöåé B ïî ìîäóëþ 5,
Ax b� �
1 1 1 1 1 0 0 0 2
1 1 1 1 0 1 0 0 0
1 1 1 1 0 0 1 0 2
1 1 1 1 0 0 0 1 2
1 0 0 0 1 1 1 1 1
0 1 0 0 1 1 1 1 2
0 0 1 0 1 1 1 1 2
0 0 0 1 1 1 1 1 1
0 5
�
�
�
�
��
�
�
�
�
�
� ( )mod ,
íå èìååò ðåøåíèÿ, ïîñêîëüêó m n� � � � � �1 2 4 1 5 (ýòî çíà÷èò, ÷òî ïîñëåäíÿÿ
ñòðîêà ìàòðèöû A ëèíåéíî çàâèñèò îò ïðåäûäóùèõ ñòðîê), à ñóììà ýëåìåíòîâ
ìàòðèöû B ðàâíà 12 è íå êðàòíà ïÿòè.
Ñëó÷àé 2. ×èñëî ñîñòîÿíèé çàìêîâ pk , ãäå p — ïðîñòîå ÷èñëî è îáëàñòü,
íàä êîòîðîé ðåøàåòñÿ ñèñòåìà, ïðåäñòàâëÿåò ïîëå �
pk . Ðàññìîòðèì ñëó÷àé ïîëÿ
�
22 , ïîñêîëüêó âñå âûêëàäêè äëÿ áîëüøèõ çíà÷åíèé p è k àíàëîãè÷íû.
Ïóñòü èìååì ñåéô â ïîëå �
22 ñ ìàòðèöåé
B � �
�
�
�
!
1 2 3
0 1 1
.
Òîãäà b � ( , , , , , )1 2 3 0 1 1 è ñèñòåìà Ax b� � 0 â ïîëå �
22 ïðèíèìàåò âèä
Ax b� �
�
�
�
1 1 1 1 0 0 1
1 1 1 0 1 0 2
1 1 1 0 0 1 3
1 0 0 1 1 1 0
0 1 0 1 1 1 1
0 0 1 1 1 1 1
��
�
�
�
�
� 0 . (16)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 25
Ïðèìåíÿÿ TSS-àëãîðèòì äëÿ ðåøåíèÿ ñèñòåìû (16), ïîëó÷àåì äëÿ ïåðâîãî åå
óðàâíåíèÿ
( , , , , , , ), ( , , , , , , ), ( , , , , , , )1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 ,
( , , , , , , ), ( , , , , , , ), ( , , , , , , )0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 .
Çíà÷åíèÿ ëåâîé ÷àñòè âòîðîãî óðàâíåíèÿ ñèñòåìû (16), âû÷èñëåííûå ïî òàá-
ëèöàì ñëîæåíèÿ è óìíîæåíèÿ â ïîëå �
22 (ñì. òàáë. 1, 2), ðàâíû 3, 3, 3, 2, 1, 0. Ïî
ýòèì çíà÷åíèÿì ïóòåì êîìáèíèðîâàíèÿ ïåðâîãî ðåøåíèÿ ñ îñòàëüíûìè ïîëó÷à-
åì ðåøåíèÿ ïåðâîãî è âòîðîãî óðàâíåíèé ñèñòåìû (16):
( , , , , , , ), ( , , , , , , ), ( , , , , , , )1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 2 0 0 3 ,
( , , , , , , ), ( , , , , , , )1 0 0 0 3 0 1 0 0 0 0 0 1 0 .
Çíà÷åíèÿ ëåâîé ÷àñòè òðåòüåãî óðàâíåíèÿ ðàâíû 0, 0, 3, 2, 1. Ïî ýòèì çíà÷å-
íèÿì êîìáèíèðîâàíèåì ïîñëåäíåãî ðåøåíèÿ ñ òðåòüèì è ÷åòâåðòûì ïîëó÷àåì
ðåøåíèÿ ïåðâûõ òðåõ óðàâíåíèé ñèñòåìû:
( , , , , , , ), ( , , , , , , ), ( , , , , , , ), (1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 2 0 3 3 1, , , , , , )0 0 0 3 2 1 .
Çíà÷åíèÿ ëåâîé ÷àñòè ÷åòâåðòîãî óðàâíåíèÿ ðàâíû 1, 1, 0, 0. Ïî ýòèì çíà÷åíè-
ÿì êîìáèíèðîâàíèåì ïåðâîãî ñî âòîðûì ðåøåíèåì ïîëó÷àåì ðåøåíèÿ ïåðâûõ
÷åòûðåõ óðàâíåíèé ñèñòåìû:
( , , , , , , ), ( , , , , , , ), ( , , , , , , )0 1 1 0 0 0 0 1 0 0 2 0 3 3 1 0 0 0 3 2 1 .
Çíà÷åíèÿ ëåâîé ÷àñòè ïÿòîãî óðàâíåíèÿ ðàâíû 1, 2, 0. Ïî ýòèì çíà÷åíèÿì ïî-
ëó÷àåì ðåøåíèÿ ïåðâûõ ïÿòè óðàâíåíèé ñèñòåìû:
( , , , , , , ), ( , , , , , , )1 2 2 2 0 3 3 1 0 0 0 3 2 1 .
Çíà÷åíèÿ ëåâîé ÷àñòè øåñòîãî óðàâíåíèÿ ðàâíû 0, 0. Ýòî çíà÷èò, ÷òî îáà âåêòî-
ðû ÿâëÿþòñÿ ðåøåíèÿìè èñõîäíîé ñèñòåìû. Âòîðîå ðåøåíèå äåéñòâèòåëüíî ÿâ-
ëÿåòñÿ ðåøåíèåì ñèñòåìû (16), à ïåðâîå ðåøåíèå ñòàíîâèòñÿ ðåøåíèåì â ñëó-
÷àå óìíîæåíèÿ íà 2 ñîãëàñíî òàáëèöàì ñëîæåíèÿ è óìíîæåíèÿ ïîëÿ �
22 . Â ðå-
çóëüòàòå ïîëó÷èì âåêòîð (2, 3, 3, 3, 0, 1, 1) — âòîðîå ðåøåíèå ñèñòåìû (16).
Íåïîñðåäñòâåííîé ïðîâåðêîé ìîæíî óáåäèòüñÿ, ÷òî ïîëó÷åííûå ðåøåíèÿ
äåéñòâèòåëüíî îòêðûâàþò ñåéô. Äëÿ ïåðâîãî ðåøåíèÿ èìååì
1 2 3
0 1 1
111
�
�
�
�
! " �( )x
0 3 2
1 1 1
322
�
�
�
�
! " �( )x
0 0 2
2 2 2
223
�
�
�
�
! " �( )x
0 0 0
0 0 0
�
�
�
�
! .
Äëÿ âòîðîãî ðåøåíèÿ èìååì
1 2 3
0 1 1
211
�
�
�
�
! " �( )x
3 0 1
2 1 1
312
�
�
�
�
! " �( )x
0 3 2
2 2 1
�
�
�
�
! "
" �( )x13 3
3 0 1
2 2 2
321
�
�
�
�
! " �( )x
0 0 1
1 1 1
133
�
�
�
�
! " �( )x
0 0 0
0 0 0
�
�
�
�
! .
Äëÿ ïîëó÷åíèÿ ðåøåíèÿ çàäà÷è î ñåéôå â ýòîì ïîëå íåîáõîäèìî âûïîëíåíèå
óñëîâèÿ: åñëè m n p� � �1 0 ( )mod , òî b b pi
i
mn
mn
�
�
� �
1
1
( )mod , ãäå ñóììà âû÷èñëÿåò-
ñÿ ïî òàáëèöàì ïîëÿ �
pk . Äåéñòâèòåëüíî, åñëè m n p� � �1 0 ( )mod , òî ïîñëåäíåå
óðàâíåíèå ñèñòåìû (16) ÿâëÿåòñÿ ñóììîé (ëèíåéíîé êîìáèíàöèåé) ïðåäûäóùèõ
óðàâíåíèé ýòîé ñèñòåìû. Îòñþäà ñëåäóåò ñïðàâåäëèâîñòü óñëîâèÿ.
26 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
Íàïðèìåð, ïðèâåäåííàÿ âûøå çàäà÷à î ñåéôå, â êîòîðîé ïîñëåäíåå çíà÷åíèå
ñâîáîäíîãî ÷ëåíà ðàâíî 2 (à íå 1), íå èìååò ðåøåíèÿ â ïîëå �
22 , ïîñêîëüêó
m n� � � � � � �1 1 1 1 1 0 2( )mod è
i
ib
�
� �
1
5
1, a ïîñëåäíåå óðàâíåíèå, ÿâëÿþùååñÿ
ñóììîé ïðåäûäóùèõ ïÿòè óðàâíåíèé, ðàâíî äâóì. Ïîëó÷åííîå ïðîòèâîðå÷èå
ñâèäåòåëüñòâóåò î íåñîâìåñòíîñòè ñèñòåìû (16). Äåéñòâèòåëüíî, êîìáèíàöèÿ
ðåøåíèé
s s1 21 2 2 2 0 3 3 1 0 0 0 3 2 1� �( , , , , , , ), ( , , , , , , )
äëÿ çíà÷åíèé 2 è 3 (ðåçóëüòàò ïîäñòàíîâêè â ïîñëåäíåå óðàâíåíèå) äàåò ðåøå-
íèå 2 3 3 3 3 3 3 01 2s s� � ( , , , , , , ), êîòîðîå íå ÿâëÿåòñÿ ðåøåíèåì çàäà÷è î ñåéôå.
Ñëó÷àé 3. ×èñëî m — ñîñòàâíîå è îáëàñòü, íàä êîòîðîé ðåøàåòñÿ ñèñòåìà (2),
ÿâëÿåòñÿ êîëüöîì âû÷åòîâ ïî ìîäóëþ m.
Ïóñòü èìååì ñåéô â êîëüöå Z12 ñ ìàòðèöåé
B � �
�
�
�
!
4 5 2
1 3 1
.
Òîãäà ñèñòåìà (2) ïðèíèìàåò âèä
Ax b
x x x x
x x x x
x x
� �
� � � � �
� � � � �
�
11 12 13 21
11 12 13 22
11
4 0
5 0
,
,
12 13 23
11 21 22 23
12 21 22 23
2 0
1 0
� � � �
� � � � �
� � �
x x
x x x x
x x x x
,
,
� �
� � � � �
�
�
�
��
�
�
�
�
3 0
1 013 21 22 23
,
.x x x x
(mod )12
Ïðèìåíÿÿ TSS-àëãîðèòì äëÿ ðåøåíèÿ ýòîé ñèñòåìû, ïîëó÷àåì ðåøåíèÿ
s1 0 6 0 6 9 0 9� ( , , , , , , ), s2 4 8 4 4 0 0 4� ( , , , , , , ).
Èç ýòèõ ðåøåíèé íóæíî ïîëó÷èòü ðåøåíèå, â êîòîðîì ïîñëåäíÿÿ êîîðäèíàòà
ðàâíà 1, ÷òî ñîîòâåòñòâóåò èñõîäíûì ïîçèöèÿì çàìêîâ. Äëÿ ýòîãî ðåøàåì ñðàâíå-
íèå 9 4 1 12x y� � ( )mod . Î÷åâèäíûì ðåøåíèåì ýòîãî ñðàâíåíèÿ åñòü x �1, y � �2
èëè ñ ó÷åòîì äîïîëíåíèÿ x �1, y �10. Ëèíåéíàÿ êîìáèíàöèÿ s s1 210� äàåò ðåøå-
íèå çàäà÷è î ìàòåìàòè÷åñêîì ñåéôå z � ( , , , , , )4 2 4 10 9 0 . Äåéñòâèòåëüíî,
4 5 2
1 3 1
411
�
�
�
�
! " �( )x
8 9 6
5 3 1
212
�
�
�
�
! " �( )x
10 11 8
5 5 1
413
�
�
�
�
! " �( )x
2 3 0
5 5 5
�
�
�
�
! "
" �( )x21 10
0 3 0
3 3 3
922
�
�
�
�
! " �( )x
0 0 0
0 0 0
�
�
�
�
! .
4. ÂÀÐÈÀÖÈÈ ÇÀÄÀ×È Î ÌÀÒÅÌÀÒÈ×ÅÑÊÎÌ ÑÅÉÔÅ
Ñëó÷àé 4. Ðàññìîòðèì çàäà÷ó î ñåéôå â ïîëå âû÷åòîâ �k , êîòîðûé ñ÷èòàåòñÿ
îòêðûòûì ïðè îïðåäåëåííîé êîìáèíàöèè âñåõ çàìêîâ (èñêëþ÷àÿ íóëåâûå ïî-
çèöèè). Òîãäà ñèñòåìà (2) ïðèíèìàåò âèä
Ax b c k� � ( )mod , (17)
ãäå c — ñîñòîÿíèÿ çàìêîâ, ïðè êîòîðûõ ñåéô ñ÷èòàåòñÿ îòêðûòûì.
Î÷åâèäíî, ÷òî äàííàÿ çàäà÷à ñâîäèòñÿ ê ðàññìîòðåííûì âûøå ñëó÷àÿì, ïî-
ñêîëüêó ñèñòåìà (17) ïðåîáðàçóåòñÿ ê ÑËÎÄÓ
Ax d k� � 0 ( )mod , (18)
ãäå d b c� � .
Ñëîæíîñòü âû÷èñëåíèÿ ïåðåáîðíûì ìåòîäîì âåêòîðà d , êîãäà íå èçâåñòíû îò-
êðûâàþùèå êîìáèíàöèè, ïðîïîðöèîíàëüíà âåëè÷èíå k mn , ãäå m n — ðàçìåð ìàò-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 27
ðèöû A. Î÷åâèäíî, ÷òî ïðè íåáîëüøèõ çíà÷åíèÿõ k m, , n âû÷èñëåíèå âåêòîðà d
íå ñîñòàâëÿåò îñîáîãî òðóäà. Îäíàêî åñëè ìîäóëü k äîñòàòî÷íî áîëüøîé, òî äàæå
ïðè íåáîëüøèõ çíà÷åíèÿõ m è n çàäà÷à óñëîæíÿåòñÿ. Íàïðèìåð, åñëè k �101, m � 4,
n � 5, òî ñëîæíîñòü ïåðåáîðíîãî ìåòîäà ñîñòàâëÿåò P � # #101 10 220 41 123 , à ýòî
óæå äîñòàòî÷íî áîëüøîå êîëè÷åñòâî êîìáèíàöèé, êîòîðîå íåîáõîäèìî â íàèõóä-
øåì ñëó÷àå âûïîëíèòü.
Åñëè â çàäà÷å íå èçâåñòåí ìîäóëü, òî ñëîæíîñòü âîçðàñòàåò â k ðàç.
Ïóñòü äàíà ìàòðèöà ñåéôà
B �
�
�
�
��
�
!
!!
14 0 0
0 0 0
0 0 11
,
à çàäà÷à ðåøàåòñÿ â ïîëå ïî ìîäóëþ 17 ñ îòêðûâàþùåé ñåéô ìàòðèöåé (êîì-
áèíàöèåé)
c �
�
�
�
��
�
!
!!
1 2 3
4 5 6
7 8 9
.
Òîãäà ÑËÍÄÓ Ax b c� � ( )mod 17 ïðèíèìàåò âèä
Ax b� �
�
�
�
1 1 1 1 0 0 1 0 0 14 1
1 1 1 0 1 0 0 1 0 0 2
1 1 1 0 0 1 0 0 1 0 3
1 0 0 1 1 1 1 0 0 0 4
0 1 0 1 1 1 0 1 0 0 5
0 0 1 1 1 1 0 0 1 0 6
1 0 0 1 0 0 1 1 1 0 7
0 1 0 0 1 0 1 1 1 0
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
8
0 0 1 0 0 1 1 1 1 11 9
( )mod 17 .
Ïîñëå ïðåîáðàçîâàíèÿ ýòîé ÑËÍÄÓ ê ÑËÎÄÓ ïîëó÷àåì
Ax d� �
�
�
�
1 1 1 1 0 0 1 0 0 13 0
1 1 1 0 1 0 0 1 0 15 0
1 1 1 0 0 1 0 0 1 14 0
1 0 0 1 1 1 1 0 0 13 0
0 1 0 1 1 1 0 1 0 12 0
0 0 1 1 1 1 0 0 1 11 0
1 0 0 1 0 0 1 1 1 10 0
0 1 0 0
�
�
�
�
1 0 1 1 1 9 0
0 0 1 0 0 1 1 1 1 2 0
�
�
�
�
�
�
�
�
�
�
�
�
�
( )mod 17 .
Ðåøåíèåì ýòîé ñèñòåìû åñòü âåêòîð y � ( , , , , , , , , , )3 13 5 1 13 5 15 10 6 5 . Äëÿ ïî-
ñòðîåíèÿ ðåøåíèÿ çàäà÷è î ñåéôå íåîáõîäèìî ðåøèòü ñðàâíåíèå 5 1 17z � ( )mod .
Ðåøåíèåì ýòîãî ñðàâíåíèÿ åñòü z � 7. Óìíîæàÿ âåêòîð y íà z � 7, ïîëó÷àåì ðå-
øåíèå çàäà÷è î ñåéôå: x � ( , , , , , , , , )4 6 1 7 6 1 3 2 8 . Äåéñòâèòåëüíî,
14 0 0
0 0 0
0 0 11
411
�
�
�
��
�
!
!!
" �( )x
1 4 4
4 0 0
4 0 11
612
�
�
�
��
�
!
!!
" �( )x
7 10 10
4 6 0
4 6 11
113
�
�
�
��
�
!
!!
" �( )x
8 11 11
4 6 1
4 6 12
�
�
�
��
�
!
!!
"
" �( )x21 7
15 11 11
11 13 8
11 6 12
622
�
�
�
��
�
!
!!
" �( )x
15 0 11
0 2 14
11 12 12
123
�
�
�
��
�
!
!!
" �( )x
15 0 12
0 2 15
11 12 13
�
�
�
��
�
!
!!
"
28 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
" �( )x31 3
1 0 12
4 3 15
14 15 16
232
�
�
�
��
�
!
!!
" �( )x
1 2 12
4 5 15
16 0 1
833
�
�
�
��
�
!
!!
" �( )x
1 2 3
4 5 6
7 8 9
�
�
�
��
�
!
!!
.
Ñëó÷àé 5. Ðàññìîòðèì çàäà÷ó î ñåéôå â ïîëå �
pk , êîòîðûé ñ÷èòàåòñÿ îòêðû-
òûì ïðè îïðåäåëåííîé êîìáèíàöèè çàìêîâ.
Ñëîæíîñòü âû÷èñëåíèÿ âåêòîðà d (êîãäà íå èçâåñòíû îòêðûâàþùèå êîìáè-
íàöèè) â íàèõóäøåì ñëó÷àå ïåðåáîðíûì ìåòîäîì ïðîïîðöèîíàëüíà âåëè÷èíå
( )p pk mn kmn� , ÷òî óæå ïðè íåáîëüøèõ çíà÷åíèÿõ p m n, , , k ñîñòàâëÿåò áîëüøèå
òðóäíîñòè âû÷èñëèòåëüíîãî õàðàêòåðà. Íàïðèìåð, ïðè p � 3, m � 2, n � 4, k � 5
ïîëó÷àåì 340 âàðèàíòîâ äëÿ àíàëèçà. Ýòà ñëîæíîñòü ìîæåò âîçðàñòè, åñëè òàá-
ëèöû ñëîæåíèÿ è óìíîæåíèÿ ïîëÿ �pk çàäàâàòü ñ òî÷íîñòüþ äî îáîçíà÷åíèÿ åå
ýëåìåíòîâ.  ýòîì ñëó÷àå íåîáõîäèìî íàéòè èçîìîðôèçì ìåæäó òàáëèöàìè äëÿ
ïîëÿ �
32 (ñì. òàáë. 3, 4). Íàïðèìåð, ïåðåíóìåðóåì ýëåìåíòû ýòîãî ïîëÿ ñëåäóþ-
ùèì îáðàçîì: ïîëèíîì x îáîçíà÷èì ÷èñëîì 8, ïîëèíîì x �1 — ÷èñëîì 7, ïîëè-
íîì x �2 — ÷èñëîì 6, ïîëèíîì 2x — ÷èñëîì 5, ïîëèíîì 2 1x � — ÷èñëîì 4, ïîëè-
íîì 2 2x � — ÷èñëîì 3. Òîãäà òàáëèöû ñëîæåíèÿ è óìíîæåíèÿ ïîëÿ èìåþò âèä
òàáë. 5 è òàáë. 6 ñîîòâåòñòâåííî. Äàæå ïðè p � 3 ÷èñëî èçîìîðôèçìîâ ñîñòàâëÿåò
( )! !3 3 6 720 32 6� � � # .
Åñëè â çàäà÷å ïîìèìî íåèçâåñòíîé îòêðûâàþùåé êîìáèíàöèè íå èçâåñòåí è
ìîäóëü ïîëÿ, òî çàäà÷à åùå áîëüøå óñëîæíÿåòñÿ.  ýòîì ñëó÷àå íåîáõîäèìî íàé-
òè ìîäóëü ïîëÿ è ñàìî ïîëå, ÷òî òðåáóåò äîïîëíèòåëüíûõ âðåìåííûõ è
âû÷èñëèòåëüíûõ çàòðàò.
Ñëó÷àé 6. Ðàññìîòðèì çàäà÷ó î ñåéôå, ðåøåíèÿ êîòîðîé íàõîäèì â êîëüöå
âû÷åòîâ ïî ìîäóëþ ñîñòàâíîãî ÷èñëà m ïðè íåèçâåñòíîé êîìáèíàöèè çàìêîâ, îò-
êðûâàþùåé ñåéô.
Ïóñòü çàäà÷à î ñåéôå ðåøàåòñÿ â êîëüöå ïî ìîäóëþ 15 ñ ìàòðèöåé
B �
�
�
�
��
�
!
!!
14 2 3
4 5 6
7 8 11
è ñ îòêðûâàþùåé ñåéô ìàòðèöåé
c �
�
�
�
��
�
!
!!
0 2 3
4 5 6
7 8 0
.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 29
Ò à á ë è ö à 6
* 0 1 2 8 7 6 5 4 3
0 0 0 0 0 0 0 0 0 0
1 0 1 2 8 7 6 5 4 3
2 0 2 1 5 3 4 8 6 7
8 0 8 5 4 1 7 6 3 2
7 0 7 3 1 6 5 2 8 4
6 0 6 4 7 5 2 3 1 8
5 0 5 8 6 2 3 4 7 1
4 0 4 6 3 8 1 7 2 5
3 0 3 7 2 4 8 1 5 6
Ò à á ë è ö à 5
� 0 1 2 8 7 6 5 4 3
0 0 1 2 8 7 6 5 4 3
1 1 2 0 7 6 8 4 3 5
2 2 0 1 6 8 7 3 5 4
8 8 7 6 5 4 3 0 1 2
7 7 6 8 4 3 5 1 2 0
6 6 8 7 3 5 4 2 0 1
5 5 4 3 0 1 2 8 7 6
4 4 3 5 1 2 0 7 6 8
3 3 5 4 2 0 1 6 8 7
Òîãäà ÑËÍÄÓ Ax b c� � ( )mod 15 ïðèíèìàåò âèä
Ax b� �
�
�
�
1 1 1 1 0 0 1 0 0 14 0
1 1 1 0 1 0 0 1 0 2 2
1 1 1 0 0 1 0 0 1 3 3
1 0 0 1 1 1 1 0 0 4 4
0 1 0 1 1 1 0 1 0 5 5
0 0 1 1 1 1 0 0 1 6 6
1 0 0 1 0 0 1 1 1 7 7
0 1 0 0 1 0 1 1 1 8
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
8
0 0 1 0 0 1 1 1 1 11 0
( )mod 15 .
Ïîñëå ïðåîáðàçîâàíèÿ ýòîé ÑËÍÄÓ ê ÑËÎÄÓ ïîëó÷àåì
Ax d� �
�
�
�
1 1 1 1 0 0 1 0 0 14 0
1 1 1 0 1 0 0 1 0 0 0
1 1 1 0 0 1 0 0 1 0 0
1 0 0 1 1 1 1 0 0 0 0
0 1 0 1 1 1 0 1 0 0 0
0 0 1 1 1 1 0 0 1 0 0
1 0 0 1 0 0 1 1 1 0 0
0 1 0 0 1 0 1 1 1 0
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
0
0 0 1 0 0 1 1 1 1 11 0
( )mod 15 .
Ðåøåíèåì ýòîé ñèñòåìû åñòü âåêòîð x � ( , , , , , , , , )5 13 0 13 5 7 0 7 5 , êîòîðûé îò-
êðûâàåò ñåéô. Äåéñòâèòåëüíî,
14 2 3
4 5 6
7 8 11
511
�
�
�
��
�
!
!!
" �( )x
4 7 8
9 5 6
12 8 11
1312
�
�
�
��
�
!
!!
" �( )x
2 5 6
9 3 6
12 6 11
1321
�
�
�
��
�
!
!!
" �( )x
0 5 6
7 1 4
10 6 11
�
�
�
��
�
!
!!
"
" �( )x22 5
0 10 6
12 6 9
10 11 11
723
�
�
�
��
�
!
!!
" �( )x
0 10 13
4 13 11
0 11 3
732
�
�
�
��
�
!
!!
" �( )x
0 2 13
4 5 1
2 3 10
�
�
�
��
�
!
!!
"
" �( )x33 5
0 2 3
4 5 6
7 8 0
�
�
�
��
�
!
!!
.
Ñëó÷àé 7. Ðåøåíèÿ çàäà÷è î ñåéôå íàõîäèì â êîëüöå âû÷åòîâ ïî ìîäóëþ
ñîñòàâíîãî ÷èñëà m ïðè íåèçâåñòíîé êîìáèíàöèè çàìêîâ, îòêðûâàþùåé ñåéô,
è ìàòðèöå ñèñòåìû (15).
Ïóñòü çàäà÷à î ñåéôå ðåøàåòñÿ â êîëüöå ïî ìîäóëþ 27 ñ ìàòðèöåé
B �
�
�
�
��
�
!
!!
1 2 0
0 0 0
0 0 0
è ñ îòêðûâàþùåé ñåéô ìàòðèöåé
c �
�
�
�
��
�
!
!!
1 2 3
4 5 6
7 8 9
.
30 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
Êðîìå òîãî, ìàòðèöà A ñèñòåìû èìååò âèä
A �
1 1 1 3 0 0 2 0 0
1 1 1 0 3 0 0 2 0
1 1 1 0 0 3 0 0 2
1 0 0 3 3 3 2 0 0
0 1 0 3 3 3 0 2 0
0 0 1 3 3 3 0 0 2
1 0 0 3 0 0 2 2 2
0 1 0 0 3 0 2 2 2
0 0 1 0 0 3 2 2 2
.
Òîãäà ÑËÍÄÓ Ax b c� � ( )mod 27 ïðèíèìàåò âèä
Ax b� �
�
�
�
1 1 1 3 0 0 2 0 0 1 1
1 1 1 0 3 0 0 2 0 2 2
1 1 1 0 0 3 0 0 2 0 3
1 0 0 3 3 3 2 0 0 0 4
0 1 0 3 3 3 0 2 0 0 5
0 0 1 3 3 3 0 0 2 0 6
1 0 0 3 0 0 2 2 2 0 7
0 1 0 0 3 0 2 2 2 0
�
�
�
�
� 8
0 0 1 0 0 3 2 2 2 0 9�
�
�
�
�
�
�
�
�
�
�
�
( )mod 27 .
Ðåøåíèåì ýòîé ñèñòåìû åñòü âåêòîð x � ( , , , , , , , , , )4 5 18 20 20 7 24 24 24 18 , êîòî-
ðûé íå îòêðûâàåò ñåéôà (â ÷åì ìîæíî óáåäèòüñÿ). Äëÿ òîãî ÷òîáû ñåéô îòêðû-
âàëñÿ, íåîáõîäèìî ðåøåíèå ïðåîáðàçîâàòü ñëåäóþùèì îáðàçîì:
� ïåðâûå òðè êîîðäèíàòû, êîòîðûå ñîîòâåòñòâóþ êîýôôèöèåíòàì 1, îñòàþò-
ñÿ íåèçìåííûìè;
� âòîðûå òðè êîîðäèíàòû, êîòîðûå ñîîòâåòñòâóþ êîýôôèöèåíòàì 3, óìíî-
æàþòñÿ íà 3 ïî ìîäóëþ 27;
� òðåòüè òðè êîîðäèíàòû, êîòîðûå ñîîòâåòñòâóþò êîýôôèöèåíòàì 2, óìíî-
æàþòñÿ íà 2 ïî ìîäóëþ 27.
 ðåçóëüòàòå ïîëó÷àåì ðåøåíèå a � ( , , , , , , , , )4 5 18 6 6 21 21 21 9 , êîòîðîå îòêðû-
âàåò ñåéô. Äåéñòâèòåëüíî,
1 2 0
0 0 0
0 0 0
411
�
�
�
��
�
!
!!
" �( )x
5 6 4
4 0 0
4 0 0
512
�
�
�
��
�
!
!!
" �( )x
10 11 9
4 5 0
4 5 0
1813
�
�
�
��
�
!
!!
" �( )x
1 2 0
4 5 18
4 5 18
�
�
�
��
�
!
!!
"
" �( )x21 6
7 2 0
10 11 24
10 5 18
622
�
�
�
��
�
!
!!
" �( )x
7 8 0
16 17 3
10 11 18
2123
�
�
�
��
�
!
!!
" �( )x
7 8 21
10 11 24
10 11 12
�
�
�
��
�
!
!!
"
" �( )x31 21
1 8 21
4 11 24
4 5 6
2132
�
�
�
��
�
!
!!
" �( )x
1 2 21
4 5 24
25 26 0
933
�
�
�
��
�
!
!!
" �( )x
1 2 3
4 5 6
7 8 9
�
�
�
��
�
!
!!
.
Ïóñòü çàäà÷à î ñåéôå ðåøàåòñÿ, êàê è ðàíüøå, â êîëüöå ïî ìîäóëþ 27 ñ ìàò-
ðèöåé
B �
�
�
�
��
�
!
!!
6 6 0
0 0 0
0 0 0
è ñ îòêðûâàþùåé ñåéô ìàòðèöåé
c �
�
�
�
��
�
!
!!
0 0 6
0 3 0
0 3 0
.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 31
Êðîìå òîãî, ìàòðèöà A ñèñòåìû èìååò âèä
A �
1 3 2 1 0 0 1 0 0
1 3 2 0 3 0 0 3 0
1 3 2 0 0 2 0 0 2
1 0 0 1 3 2 1 0 0
0 3 0 1 3 2 0 3 0
0 0 2 1 3 2 0 0 2
1 0 0 1 0 0 1 3 2
0 3 0 0 3 0 1 3 2
0 0 2 0 0 2 1 3 2
.
Òîãäà ÑËÍÄÓ Ax b c� � ( )mod 27 ïðèíèìàåò âèä
Ax b� �
�
�
�
1 3 2 1 0 0 1 0 0 6 0
1 3 2 0 3 0 0 3 0 6 0
1 3 2 0 0 2 0 0 2 0 6
1 0 0 1 3 2 1 0 0 0 0
0 3 0 1 3 2 0 3 0 0 3
0 0 2 1 3 2 0 0 2 0 0
1 0 0 1 0 0 1 3 2 0 0
0 3 0 0 3 0 1 3 2 0
�
�
�
�
� 3
0 0 2 0 0 2 1 3 2 0 0�
�
�
�
�
�
�
�
�
�
�
�
( ).mod 27
Ðåøåíèåì ýòîé ñèñòåìû åñòü âåêòîð x � ( , , , , , , , , )0 19 24 12 13 9 12 13 9 , êîòîðûé
íå îòêðûâàåò ñåéôà (â ÷åì ìîæíî óáåäèòüñÿ). Äëÿ òîãî ÷òîáû ñåéô îòêðûâàëñÿ,
íåîáõîäèìî ðåøåíèå ïðåîáðàçîâàòü ñëåäóþùèì îáðàçîì:
� ïåðâàÿ, ÷åòâåðòàÿ è ñåäüìàÿ êîîðäèíàòû, êîòîðûå ñîîòâåòñòâóþò êîýôôè-
öèåíòó 1, îñòàþòñÿ íåèçìåííûìè;
� âòîðàÿ, ïÿòàÿ è âîñüìàÿ êîîðäèíàòû, êîòîðûå ñîîòâåòñòâóþò êîýôôèöèåí-
òó 3, óìíîæàþòñÿ íà 3 ïî ìîäóëþ 27;
� òðåòüÿ, øåñòàÿ è äåâÿòàÿ êîîðäèíàòû, êîòîðûå ñîîòâåòñòâóþò êîýôôèöè-
åíòó 2, óìíîæàþòñÿ íà 2 ïî ìîäóëþ 27.
 ðåçóëüòàòå ïîëó÷àåì ðåøåíèå a � ( , , , , , , , , )0 3 21 12 12 18 12 12 18 , êîòîðîå îò-
êðûâàåò ñåéô. Äåéñòâèòåëüíî,
6 6 0
0 0 0
0 0 0
312
�
�
�
��
�
!
!!
" �( )x
9 9 3
0 3 0
0 3 0
2113
�
�
�
��
�
!
!!
" �( )x
3 3 24
0 3 21
0 3 21
1221
�
�
�
��
�
!
!!
" �( )x
15 3 24
12 15 6
12 3 21
�
�
�
��
�
!
!!
"
" �( )x22 12
15 15 24
24 0 18
12 15 21
1823
�
�
�
��
�
!
!!
" �( )x
15 15 15
15 18 9
12 15 12
1231
�
�
�
��
�
!
!!
" �( )x
0 15 15
0 18 9
24 0 24
�
�
�
��
�
!
!!
"
" �( )x32 12
0 0 15
0 3 9
9 12 9
1833
�
�
�
��
�
!
!!
" �( )x
0 0 6
0 3 0
0 3 0
�
�
�
��
�
!
!!
.
Ñèñòåìà (17) áóäåò íåñîâìåñòíîé, åñëè õîòÿ áû ïî îäíîìó èç ìîäóëåé ðàçëîæå-
íèÿ îíà íåñîâìåñòíà èëè ñðàâíåíèå (15) íå èìååò ðåøåíèé. Ñëîæíîñòíûå îöåíêè
âîçðàñòàþò íà âåëè÷èíó 2m , ïîñêîëüêó íåîáõîäèìî íàéòè òàêæå ìàòðèöó A.
Òàêèì îáðàçîì, íàèáîëåå ñëîæíîé çàäà÷åé î ñåéôå ïðè íåèçâåñòíîì ìîäóëå
è íåèçâåñòíûõ îòêðûâàþùåé êîìáèíàöèè è ìàòðèöå, ïî-âèäèìîìó, åñòü çàäà÷à
î ñåéôå â ïîëå �pk èëè â êîëüöå Zm .
32 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
5. ÇÀÄÀÍÈÅ ÌÀÒÅÌÀÒÈ×ÅÑÊÎÃÎ ÑÅÉÔÀ Ñ ÏÎÌÎÙÜÞ ÃÐÀÔÀ
Ïðè çàäàíèè ìàòåìàòè÷åñêîãî ñåéôà íà ãðàôå G V E� ( , ) çàìêè â âåðøèíàõ ìîãóò
íàõîäèòüñÿ â îäíîé èç ïîçèöèé ìíîæåñòâà { }0 1 1, , ,� k � . Åñëè â âåðøèíå u çàìîê
íàõîäèòñÿ â ïîçèöèè i, òî ïîâîðîò êëþ÷à â ýòîé âåðøèíå ïåðåâîäèò â ïîçèöèþ
( ) ( )i k�1 mod åå çàìîê, à òàêæå è âñå çàìêè âåðøèí, ñìåæíûõ ñ âåðøèíîé u. Íà-
÷àëüíûå ïîçèöèè çàìêîâ â âåðøèíàõ çàäàþòñÿ âåêòîðîì b b b b V� ( , , , )| |1 2 � .
Ðåøåíèå çàäà÷è âûïîëíÿåòñÿ òåìè æå àëãîðèòìàìè, ÷òî è ïðè ðåøåíèè çàäà-
÷è íà ìàòðèöàõ. Îäíàêî ïðè òàêîì çàäàíèè ñòðóêòóðà ìàòðèöû ÑËÎÄÓ
Ax b c k� � ( )mod ìîæåò áûòü ïðîèçâîëüíîé.
Ïðèìåð 1. Ïóñòü èìååì ãðàô G V E� ( , ) (ðèñ. 1) è âåêòîð b � ( , , , , )1 2 1 1 3 .
Ñòðîèì ÑËÎÄÓ Ax b k� � 0 ( )mod äëÿ çàäà÷è, çàäàííîé ýòèì ãðàôîì (k � 5):
Ðåøåíèåì äàííîé ÑËÎÄÓ ÿâëÿåòñÿ âåêòîð
x � ( , , , , )0 1 2 1 1
1 2 1 1 3
1
2 3 2 1 3
2
4 0 4 3 3
1
4 0 0 4 4
1
0 0 0 0 0
2
3
4
5
,
,
,
,
.
$ �
$ �
$ �
$ �
b
b
b
b
Òàêèì îáðàçîì, ñåéô îòêðûò.
Ïðèìåð 2. Ðàññìîòðèì îðãðàô G (ðèñ. 2), ãäå b � ( , , , , )1 2 1 1 3 è c � ( , , , , )1 3 0 2 6 .
Ñòðîèì ÑËHÄÓ Ax b c k� � ( )mod äëÿ çàäà÷è, çàäàííîé ýòèì ãðàôîì (k �15):
Ðåøåíèåì äàííîé ÑËÎÄÓ ÿâëÿåòñÿ âåêòîð x � ( , , , , )0 0 1 13 3 . Âûïîëíèâ ïîâîðî-
òû êëþ÷à ïî ñòîëáöàì ìàòðèöû, ïîëó÷èì îòêðûâàþùóþ êîìáèíàöèþ ïîçèöèé
çàìêîâ â âåðøèíàõ îðãðàôà:
1 2 1 1 3
1
1 3 2 1 3
13
1 3 0 14 3
3
1 3 0 2 6
3
4
5
,
,
,
.
$ �
$ �
$ �
b
b
b
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 33
A
b
�
�
�
�
��
�
�
1 2 3 4 5
1 1 1 1 0 1 1
2 1 1 1 0 0 2
3 1 1 1 1 0 1
4 0 0 1 1 1 1
5 1 0 0 1 1 3
�
�
� 0 5(mod ).
A
b c
�
�
�
�
�
1 2 3 4 5
1 1 1 0 0 0 1 1
2 0 1 1 0 0 2 3
3 1 0 1 1 0 1 0
4 0 0 0 1 1 1 2
5 1 0 0 0 1 3 6�
�
�
�
��
�
�
�
�
( )mod 15 .
1
2
3
5 4
Ðèñ. 1. Ãðàô G V E� ( , )
1
2
3
5 4
Ðèñ. 2. Îðãðàô G
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåíû àëãîðèòìû ðåøåíèÿ çàäà÷è î ìàòåìàòè÷åñêîì ñåéôå â ðàçíûõ âà-
ðèàöèÿõ è íàä ðàçëè÷íûìè îáëàñòÿìè. Íàèáîëåå ñëîæíîé çàäà÷åé î ñåéôå ïðè
íåèçâåñòíûõ ìîäóëå è îòêðûâàþùåé êîìáèíàöèè çàìêîâ ÿâëÿåòñÿ çàäà÷à
â ïîëå �pk è êîëüöà âû÷åòîâ ïî ñîñòàâíîìó ìîäóëþ. Îòëè÷èå çàäà÷ î ìàòå-
ìàòè÷åñêîì ñåéôå íà ãðàôàõ îò àíàëîãè÷íîé íà ìàòðèöàõ ñîñòîèò â òîì, ÷òî
ñòðóêòóðà ìàòðèöû ñèñòåìû óðàâíåíèé ìîæåò áûòü ïðîèçâîëüíîé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Äîíåö Ã.À. Ðåøåíèå çàäà÷è î ñåéôå íà (0, 1)-ìàòðèöàõ. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2002. ¹ 1.
Ñ. 98–105.
2. Ñåð㳺íêî ².Â., Êðèâèé Ñ.Ë., Ïðîâîòàð Î.². Àëãåáðà¿÷í³ àñïåêòè ³íôîðìàö³éíèõ òåõíîëîã³é. ×. 1. Êè¿â:
²íòåðñåðâ³ñ, 2018. 410 ñ.
3. Êðûâûé Ñ.Ë. Àëãîðèòìû ðåøåíèÿ ñèñòåì ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé â ïîëÿõ âû÷åòîâ. Êèáåðíå-
òèêà è ñèñòåìíûé àíàëèç. 2007. ¹ 2. C. 15–23.
4. Êðûâûé Ñ.Ë. Àëãîðèòìû ðåøåíèÿ ñèñòåì ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé â êîëüöàõ âû÷åòîâ. Êèáåð-
íåòèêà è ñèñòåìíûé àíàëèç. 2007. ¹ 6. C. 27–40.
5. Êðèâèé Ñ.Ë. ˳í³éí³ ä³îôàíòîâ³ îáìåæåííÿ òà ¿õ çàñòîñóâàííÿ. ×åðí³âö³; Êè¿â: Áóêðåê, 2015. 224 ñ.
Íàä³éøëà äî ðåäàêö³¿ 09.10.2018
Ñ.Ë. Êðèâèé
×ÈÑÅËÜͲ ÌÅÒÎÄÈ ÐÎÇÂ’ßÇÀÍÍß ÇÀÄÀײ ÏÐÎ ÌÀÒÅÌÀÒÈ×ÍÈÉ ÑÅÉÔ
Àíîòàö³ÿ. Íàâåäåíî ÷èñåëüí³ ìåòîäè ðîçâ’ÿçàííÿ çàäà÷³ ïðî ìàòåìàòè÷íèé
ñåéô ç äîâ³ëüíèì ñê³í÷åííèì ÷èñëîì ïîçèö³é çàñóâ³â. Ìåòîäè ´ðóíòóþòüñÿ
íà TSS-àëãîðèòìàõ ïîáóäîâè ìíîæèíè áàçèñíèõ ðîçâ’ÿçê³â ñèñòåì ë³í³éíèõ
ä³îôàíòîâèõ ð³âíÿíü â ñê³í÷åííèõ ïîëÿõ ³ ê³ëüöÿõ.
Êëþ÷îâ³ ñëîâà: ä³îôàíòîâ³ ð³âíÿííÿ, ñê³í÷åíí³ ïîëÿ, ñê³í÷åíí³ ê³ëüöÿ, ñèñ-
òåìè ë³í³éíèõ ð³âíÿíü, áàçèñ ðîçâ’ÿçê³â.
S.L. Kryvyi
THE NUMERICAL METHODS TO SOLVE PROBLEMS OF MATHEMATICAL SAFE
Abstract. The numerical metods to solve problems of mathematical safe with an
arbitrary finite number of position of bolts is presented. The basis of the
methods are TSS-algorithms for solving systems of linear Diophantine equations
in finite fields and rings.
Keywords: Diophantine equations, finite fields, finite rings, systems of linear
equations, basis of solutions.
Êðûâûé Ñåðãåé Ëóêüÿíîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà
èìåíè Òàðàñà Øåâ÷åíêî, e-mail: sl.krivoi@gmail.com.
34 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
|
| id | nasplib_isofts_kiev_ua-123456789-181027 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T15:48:27Z |
| publishDate | 2019 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Крывый, С.Л. 2021-10-29T17:25:15Z 2021-10-29T17:25:15Z 2019 Численные методы решения задачи о математическом сейфе / С.Л. Крывый // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 18-34. — Бібліогр.: 5 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/181027 51.681.3 Приведены численные методы решения задачи о математическом сейфе с произвольным конечным числом позиций замков. Методы базируются на TSS-алгоритмах построения множества базисных решений систем линейных диофантовых уравнений в конечных полях и кольцах. Наведено чисельні методи розв’язання задачі про математичний сейф з довільним скінченним числом позицій засувів. Методи ґрунтуються на TSS-алгоритмах побудови множини базисних розв’язків систем лінійних діофантових рівнянь в скінченних полях і кільцях. The numerical metods to solve problems of mathematical safe with an arbitrary finite number of position of bolts is presented. The basis of the methods are TSS-algorithms for solving systems of linear Diophantine equations in finite fields and rings. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кібернетика Численные методы решения задачи о математическом сейфе Чисельні методи розв’язання задачі про математичний сейф The numerical methods to solve problems of mathematical safe Article published earlier |
| spellingShingle | Численные методы решения задачи о математическом сейфе Крывый, С.Л. Кібернетика |
| title | Численные методы решения задачи о математическом сейфе |
| title_alt | Чисельні методи розв’язання задачі про математичний сейф The numerical methods to solve problems of mathematical safe |
| title_full | Численные методы решения задачи о математическом сейфе |
| title_fullStr | Численные методы решения задачи о математическом сейфе |
| title_full_unstemmed | Численные методы решения задачи о математическом сейфе |
| title_short | Численные методы решения задачи о математическом сейфе |
| title_sort | численные методы решения задачи о математическом сейфе |
| topic | Кібернетика |
| topic_facet | Кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/181027 |
| work_keys_str_mv | AT kryvyisl čislennyemetodyrešeniâzadačiomatematičeskomseife AT kryvyisl čiselʹnímetodirozvâzannâzadačípromatematičniiseif AT kryvyisl thenumericalmethodstosolveproblemsofmathematicalsafe |