Алгоритмы решения систем линейных уравнений в кольцах вычетов

Алгоритмы решения систем линейных уравнений в кольцах вычетов

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Кибернетика и системный анализ
Datum:2016
1. Verfasser: Крывый, С.Л.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Schlagworte:
Программно-технические комплексы
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/142023
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:Алгоритмы решения систем линейных уравнений в кольцах вычетов / С.Л. Крывый // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 149-160. — Бібліогр.: 6 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-142023
record_format dspace
spelling Крывый, С.Л.
2018-09-20T18:09:27Z
2018-09-20T18:09:27Z
2016
Алгоритмы решения систем линейных уравнений в кольцах вычетов / С.Л. Крывый // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 149-160. — Бібліогр.: 6 назв. — рос.
0023-1274
https://nasplib.isofts.kiev.ua/handle/123456789/142023
51.681.3
Предложены полиномиальные алгоритмы построения базиса множества решений системы линейных однородных и неоднородных диофантовых уравнений в кольце вычетов по модулю некоторого числа при условии известного разложения модуля на простые множители.
Запропоновано поліноміальні алгоритми побудови базису множини розв’язків системи лінійних однорідних і неоднорідних діофантових рівнянь в кільці лишків за модулем деякого числа при умові відомого розкладу модуля на прості множники.
The author proposes polynomial algorithms to construct the base of the set of solutions of a system of linear Diophantine homogeneous and inhomogeneous equations in residue ring modulo some number provided that prime factorization of the modulo is known
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Кибернетика и системный анализ
Программно-технические комплексы
Алгоритмы решения систем линейных уравнений в кольцах вычетов
Алгоритми розв’язання систем лінійних рівнянь в кільцях лишків
Solution algorithms for systems of linear equations over residue rings
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 2016
language Russian
container_title Кибернетика и системный анализ
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Алгоритми розв’язання систем лінійних рівнянь в кільцях лишків
Solution algorithms for systems of linear equations over residue rings
description Предложены полиномиальные алгоритмы построения базиса множества решений системы линейных однородных и неоднородных диофантовых уравнений в кольце вычетов по модулю некоторого числа при условии известного разложения модуля на простые множители. Запропоновано поліноміальні алгоритми побудови базису множини розв’язків системи лінійних однорідних і неоднорідних діофантових рівнянь в кільці лишків за модулем деякого числа при умові відомого розкладу модуля на прості множники. The author proposes polynomial algorithms to construct the base of the set of solutions of a system of linear Diophantine homogeneous and inhomogeneous equations in residue ring modulo some number provided that prime factorization of the modulo is known
issn 0023-1274
url https://nasplib.isofts.kiev.ua/handle/123456789/142023
citation_txt Алгоритмы решения систем линейных уравнений в кольцах вычетов / С.Л. Крывый // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 149-160. — Бібліогр.: 6 назв. — рос.
work_keys_str_mv AT kryvyisl algoritmyrešeniâsistemlineinyhuravneniivkolʹcahvyčetov
AT kryvyisl algoritmirozvâzannâsistemlíníinihrívnânʹvkílʹcâhliškív
AT kryvyisl solutionalgorithmsforsystemsoflinearequationsoverresiduerings
first_indexed 2025-11-27T02:26:37Z
last_indexed 2025-11-27T02:26:37Z
_version_ 1850793968359440384
fulltext Ñ.Ë. ÊÐÛÂÛÉ ÓÄÊ 51.681.3 ÀËÃÎÐÈÒÌÛ ÐÅØÅÍÈß ÑÈÑÒÅÌ ËÈÍÅÉÍÛÕ ÓÐÀÂÍÅÍÈÉ Â ÊÎËÜÖÀÕ ÂÛ×ÅÒΠÀííîòàöèÿ. Ïðåäëîæåíû ïîëèíîìèàëüíûå àëãîðèòìû ïîñòðîåíèÿ áàçèñà ìíîæåñòâà ðåøåíèé ñèñòåìû ëèíåéíûõ îäíîðîäíûõ è íåîäíîðîäíûõ äèî- ôàíòîâûõ óðàâíåíèé â êîëüöå âû÷åòîâ ïî ìîäóëþ íåêîòîðîãî ÷èñëà ïðè óñëîâèè èçâåñòíîãî ðàçëîæåíèÿ ìîäóëÿ íà ïðîñòûå ìíîæèòåëè. Êëþ÷åâûå ñëîâà: êîëüöî âû÷åòîâ, ëèíåéíûå äèîôàíòîâûå óðàâíåíèÿ, áà- çèñ ìíîæåñòâà ðåøåíèé. ÂÂÅÄÅÍÈÅ Â íàñòîÿùåé ñòàòüå ðàññìàòðèâàþòñÿ óëó÷øåííûå àëãîðèòìû ïîñòðîåíèÿ áà- çèñà ìíîæåñòâà ðåøåíèé ñèñòåì ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé â êîëüöå âû÷åòîâ ïî ìîäóëþ ñîñòàâíîãî ÷èñëà m ïî ñðàâíåíèþ ñ òåìè àëãîðèòìàìè, êîòîðûå ïðèâîäèëèñü â [1].  îñíîâå ïðåäëàãàåìûõ àëãîðèòìîâ ëåæèò TSS-ìå- òîä [2, 3]. Ñëîæíîñòü ïðåäëàãàåìûõ àëãîðèòìîâ îïðåäåëÿåòñÿ ñëîæíîñòüþ ïðîáëåìû ðàçëîæåíèÿ ìîäóëÿ m íà ïðîñòûå ìíîæèòåëè. Åñëè òàêîå ðàçëîæå- íèå èìååò ìåñòî, òî ïðåäëàãàåìûå àëãîðèòìû èìåþò ïîëèíîìèàëüíóþ îöåíêó ñëîæíîñòè. Ðàññìàòðèâàåìûå àëãîðèòìû ïðèìåíÿþòñÿ ê ðåøåíèþ çàäà÷è î ìà- òåìàòè÷åñêîì ñåéôå [4, 5]. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Êîëüöîì âû÷åòîâ Zm ïî ìîäóëþ ÷èñëà m íàçûâàåòñÿ àëãåáðà Z Dm � �( { , ,0 1 � � , }, { , , , , , })m � � � � � �1 0 11� , ãäå çíàêè � è � ïðåäñòàâëÿþò áèíàðíûå îïåðà- öèè ñëîæåíèÿ è óìíîæåíèÿ ïî ìîäóëþ m, çíàêè � è �1 ïðåäñòàâëÿþò óíàð- íûå îïåðàöèè âçÿòèÿ ïðîòèâîïîëîæíîãî è îáðàòíîãî ýëåìåíòîâ îòíîñèòåëüíî îïåðàöèé � è � ñîîòâåòñòâåííî, 0 è 1 — íóëüàðíûå îïåðàöèè, ò.å. àääèòèâíûé íóëü è ìóëüòèïëèêàòèâíàÿ åäèíèöà. Èç ñâîéñòâ îïåðàöèé â êîëüöå Zm âûòåêàåò ñïðàâåäëèâîñòü òîæäåñòâà ( , )� � � � � � �x y Z x y m x ym 0 . Îòñþäà ñëåäóåò, ÷òî êîãäà x m y� – â êîëüöå Zm , òî � �y x m– , ÷òî äàåò âîç- ìîæíîñòü çàìåíÿòü ïîëîæèòåëüíîå ÷èñëî x íà îòðèöàòåëüíîå ÷èñëî � �y x m– è íàîáîðîò. Òàêèå ýëåìåíòû x è – y áóäåì íàçûâàòü äîïîëíåíèÿìè (x äîïîëíÿ- åò – y äî íóëÿ è íàîáîðîò). Êîëüöî âû÷åòîâ Zm íàçûâàåòñÿ ïðèìàðíûì, åñëè ìîäóëü m ÿâëÿåòñÿ ñòåïåíüþ ïðîñòîãî ÷èñëà p, ò.å. m pt� , ãäå t 1, t N� . Ïîñêîëüêó m — íå îáÿçàòåëüíî ïðî- ñòîå ÷èñëî, òî â êîëüöå Zm ïðè a � 0 ñðàâíåíèå ax b m� ( )mod íå âñåãäà èìååò ðå- øåíèå. Îíî áóäåò èìåòü ðåøåíèå, åñëè ÍÎÄ(a m d, ) � è d — äåëèòåëü ÷èñëà b. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 149 © Ñ.Ë. Êðûâûé, 2016 Ðàññìîòðèì ñèñòåìó ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé (ÑËÄÓ) â êîëüöå 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 , (1) ãäå a b Zij i m, � . Ðåøåíèåì ÑËÄÓ (1) íàçûâàåòñÿ òàêîé âåêòîð c c c cn� ( , , , )1 2 � , ïðè ïîäñòà- íîâêå êîòîðîãî âìåñòî x â L xi ( ) ïîëó÷àåì òîæäåñòâî L c b mi i( ) (mod )� äëÿ âñåõ i q�1 2, , ,� . ÑËÄÓ íàçûâàåòñÿ îäíîðîäíîé (ÑËÎÄÓ), åñëè âñå bi ðàâíû íóëþ, â ïðîòèâíîì ñëó÷àå ÑËÄÓ íàçûâàåòñÿ íåîäíîðîäíîé (ÑËÍÄÓ). Åñëè M — ìíîæåñòâî ðåøåíèé ñèñòåìû S , òî äëÿ ÑËÎÄÓ íóëåâîé âåêòîð âñåãäà áóäåò åå ðåøåíèåì. Ýòî ðåøåíèå íàçûâàþò òðèâèàëüíûì, à ëþáîå ðåøå- íèå ñèñòåìû S , îòëè÷íîå îò íóëåâîãî, íàçûâàåòñÿ íåòðèâèàëüíûì. ÑËÎÄÓ S íà- çûâàåì íåñîâìåñòíîé, åñëè îíà èìååò òîëüêî òðèâèàëüíîå ðåøåíèå, â ïðîòèâíîì ñëó÷àå S íàçûâàåòñÿ ñîâìåñòíîé ñèñòåìîé. Ïóñòü ìîäóëü èìååò ðàçëîæåíèå íà ïðîñòûå ìíîæèòåëè: m p p p k k r kr� 1 2 1 2� , ãäå p p pr1 2� � �� . Òîãäà ïî ñèñòåìå S ïîñòðîèì ñèñòåìó ñ r s� óðàâíåíèÿìè âèäà � � � � � � � � � � � � � � � � � � � � � � � � � � S S L x a x a x b xq q 1 1 11 1 1 1 0( ) � � � � � � � 0 02 21 1 2 2 0 , ( ) , ( ) L x a x a x b x L x q q s � ��������������� � � � � � � � � � � � � a x a x b x p S L x a x s sq q s k 1 1 0 1 2 1 11 0 1 � (mod ), ( ) 1 1 1 0 2 21 1 2 2 0 0 0 � � � � � � � � � � � ������ a x b x L x a x a x b x q q q q , ( ) , ��������� �L x a x a x b x p s s sq q s k ( ) (mod ), � � � � � � � � � 1 1 0 2 0 2 � � � � � � � � � � � � � S L x a x a x b x L x a x a x r q q q 1 11 1 1 1 0 2 21 1 2 0( ) , ( ) q s s sq q s b x L x a x a x b x � � � � � � � 2 0 1 1 0 0 0 , ( ) ��������������� � � � � � � � (mod ).pr kr (2) Òåîðåìà 1. Ñèñòåìû S è �S ýêâèâàëåíòíû. Äåéñòâèòåëüíî, åñëè x — ðåøåíèå ñèñòåìû S , òî îíî áóäåò ðåøåíèåì êàæ- äîé èç ïîäñèñòåì ïî ìîäóëþ pi ki , ïîñêîëüêó ìîäóëü m äåëèòñÿ íà êàæäîå èç ÷è- ñåë pi ki , i r�1 2, , ,� . Åñëè x — ðåøåíèå ñèñòåìû �S , òî îíî áóäåò ðåøåíèåì êàæ- äîé èç åå ïîäñèñòåì ïî ìîäóëþ pi ki , à çíà÷èò, è ðåøåíèåì ñèñòåìû S ïî ìîäóëþ m, ïîñêîëüêó ÷èñëà pi ki âçàèìíî ïðîñòûå è èõ ïðîèçâåäåíèå ðàâíî m. Ïóñòü x a a aq� ( , , , , )1 2 1� — ðåøåíèå ïîäñèñòåìû âèäà 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 150 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 Ðàññìîòðèì âåêòîð m x1 , ãäå m m p k1 1 1 � , êîòîðûé áóäåò ðåøåíèåì ñèñòåìû �S . Äåéñòâèòåëüíî, äëÿ âòîðîé ñèñòåìû S 2 , àíàëîãè÷íîé ïðåäûäóùåé ïî ìîäóëþ p k 2 2 , ïîëó÷àåì äëÿ ëþáîãî åå óðàâíåíèÿ Li L m x m L x m d pi i i k ( ) ( ) (mod )1 1 1 2 0 2� � � , i s�1 2, , ,� , ïîñêîëüêó m1 êðàòíî p k 2 2 , à di êðàòíî p k 1 1 . Àíàëîãè÷íî åñëè y — ðåøåíèå S 2 , òî m y2 , ãäå m m p k2 2 2 � , áóäåò ðåøåíèåì ñèñòåìû �S è ò.ä. äëÿ ëþáîé èç ñèñòåì S S r3 , ,� . Ïî ýòèì ðåøåíèÿì íåîáõîäèìî ïîñòðîèòü ÷àñòíîå ðåøåíèå ñèñòåìû S . Îáîçíà÷èì e m xi i i� , ãäå xi — ðåøåíèå ñèñòåìû S i ri , , , ,�1 2 � . Ëåììà 1. Âåêòîðû e e er1 2, , ,� ëèíåéíî íåçàâèñèìû íàä êîëüöîì Zm . Äëÿ äîêàçàòåëüñòâà ïðåäñòàâèì âåêòîðû ei â êîîðäèíàòíîé ôîðìå e c c c e c c c e c cq q k k k1 11 12 1 2 21 22 2 1� � �( , , , ), ( , , , ), , ( ,� � � 2 , , )� ckq è äîïóñòèì, ÷òî ñóùåñòâóþò ÷èñëà a a ak1 2, , ,� , ãäå a pi i ki� , òàêèå, ÷òî a e a e a e mk k1 1 2 2 0� � � �� (mod ) èëè, ÷òî òî æå ñàìîå, a e a e b e mk k2 2 1 1� � �� ( )mod , ãäå b1 — äîïîëíåíèå a1 â êîëüöå Zm è a e m1 1 0�� (mod ). Ïðèíèìàÿ âî âíèìà- íèå êîîðäèíàòíóþ ôîðìó âåêòîðîâ e i ki , , , ,�1 2 � , ïîëó÷àåì ñèñòåìó � � � � � � � � � � S a m c a m c b m c a m c a m c k k k k k k 1 2 2 21 1 1 1 11 2 2 22 2 � � , � � � � � � � b m c a m c a m c b m cq k k kq 1 1 12 2 2 2 1 1 1 , �������������� � q k p � � � � (mod ), 1 1 ãäå �cij — êîîðäèíàòû âåêòîðîâ x i ri , , , ,�1 2 � . Èç âèäà ñðàâíåíèé ñèñòåìû �S1 âûòåêàåò, ÷òî ëåâàÿ ÷àñòü êàæäîãî èç íèõ êðàòíà p k 1 1 , êàê è ñàì ìîäóëü m. Íî òîãäà ñèñòåìà �S1 áóäåò èìåòü ðåøåíèå òîëü- êî â ñëó÷àå êðàòíîñòè ÷èñëà b m1 1 (à çíà÷èò, êðàòíîñòè a c i1 1 ) ÷èñëó p k 1 1 . Íî åñëè âñå ÷èñëà a c i1 1 êðàòíû p k 1 1 , òî ïîëó÷àåì a e m1 1 0� (mod ), ÷òî ïðîòèâîðå÷èò ïðåäïîëîæåíèþ a e m1 1 0�� (mod ). Ïîëó÷åííîå ïðîòèâîðå÷èå ïîêàçûâàåò íåñîâ- ìåñòíîñòü ñèñòåìû �S1, à ýòî ñâèäåòåëüñòâóåò î ëèíåéíîé íåçàâèñèìîñòè ñîâîêóï- íîñòè âåêòîðîâ e e ek1 2, , ,� . Ëåììà äîêàçàíà. Äëÿ ïîñòðîåíèÿ èñêîìîãî ÷àñòíîãî ðåøåíèÿ ñèñòåìû S ñîñòàâèì ñðàâíåíèå âèäà m e m e m e mr r1 1 2 2 1� � � �� (mod ). (3) Ïóñòü u b b br� ( , , , )1 2 � — ðåøåíèå ýòîãî ñðàâíåíèÿ; òîãäà âåêòîð � � � � �b e b e b er r1 1 2 2 � áóäåò èñêîìûì ÷àñòíûì ðåøåíèåì ñèñòåìû S . Çàìåòèì, ÷òî ñðàâíåíèå (3) áóäåò èìåòü ðåøåíèå òîëüêî â ñëó÷àå ÍÎÄ ( , , )b br1 1� � . Ýòî âûòåêàåò èç ñëåäóþùåãî óòâåðæäåíèÿ. Òåîðåìà 2. ÑËÍÄÓ (1) ñîâìåñòíà òîãäà è òîëüêî òîãäà, êîãäà ñðàâíåíèå (3) èìååò ðåøåíèå. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 151 Äîêàçàòåëüñòâî. Åñëè ñðàâíåíèå (3) èìååò ðåøåíèå, òî ðàñøèðåííàÿ ÑËÎÄÓ äëÿ äàííîé ÑËÍÄÓ èìååò ðåøåíèå, â êîòîðîì ïîñëåäíÿÿ êîîðäèíàòà ðàâíà åäèíèöå. Òîãäà, îòáðàñûâàÿ â ýòîì ðåøåíèè ïîñëåäíþþ êîîðäèíàòó, ïîëó÷àåì ÷àñòíîå ðåøåíèå ÑËÍÄÓ. Ïóñòü ÑËÍÄÓ ñîâìåñòíà è x1 — åå ÷àñòíîå ðåøåíèå. Òîãäà ðàñøèðåííàÿ ÑËÎÄÓ äëÿ äàííîé ÑËÍÄÓ â ñâîåì áàçèñå áóäåò èìåòü âåêòîðû, ïîñëåäíèå êîîðäè- íàòû êîòîðûõ îòëè÷íû îò íóëÿ è äëÿ êîòîðûõ ñðàâíåíèå (3) èìååò ðåøåíèå.  ïðî- òèâíîì ñëó÷àå ýòî ïðîòèâîðå÷èëî áû ñîâìåñòíîñòè ÑËÍÄÓ. Òåîðåìà äîêàçàíà. Èç ýòîé òåîðåìû ñëåäóåò, ÷òî åñëè â ðàçëîæåíèè ìîäóëÿ m âñå ïðîñòûå ìíî- æèòåëè èìåþò ïåðâóþ ñòåïåíü è ÑËÍÄÓ, íà êîòîðûå ðàñïàäàåòñÿ èñõîäíàÿ ÑËÍÄÓ â êîëüöå Zm , ñîâìåñòíû, òî è èñõîäíàÿ ñèñòåìà òàêæå ñîâìåñòíà. Ïóñòü x1 — ÷àñòíîå ðåøåíèå ÑËÍÄÓ S è x x xs1 2, , ,� — áàçèñíûå ðåøåíèÿ ÑËÎÄÓ, êîòîðàÿ ñîîòâåòñòâóåò S . Òîãäà îáùåå ðåøåíèå ñèñòåìû �S ïðèíèìàåò âèä y x a x a x a xs s� � � � �1 1 1 2 2 � . (4) Ñëåäîâàòåëüíî, âîçíèêàåò íåîáõîäèìîñòü ðåøèòü ñèñòåìó âèäà �S . À ðåøå- íèå òàêîé ñèñòåìû ñâîäèòñÿ ê ðåøåíèþ ïîäñèñòåì S i ïî ìîäóëþ pi ki ëèáî â ïî- ëÿõ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëà (â ñëó÷àå k i �1 äëÿ íåêîòîðîãî i r�[ , ]1 ), ëèáî ê ðåøåíèþ ñèñòåì â ïðèìàðíûõ êîëüöàõ (â ñëó÷àå k i 1). TSS-ÌÅÒÎÄ ÐÅØÅÍÈß ÑËÎÄÓ ÍÀÄ ÏÐÈÌÀÐÍÛÌÈ ÊÎËÜÖÀÌÈ Ðàññìîòðèì âíà÷àäå ËÎÄÓ L x a x a x a xi i n n( ) � � � � � �1 1 0� � , (5) ãäå a x Zi i m, � , i n�1, ,� . Äîïóñòèì, ÷òî ai � 0, òîãäà èìååò ìåñòî òàêîå ïðî- ñòîå óòâåðæäåíèå. Ëåììà 2. Åñëè c c cn� ( , , )1 � — ðåøåíèå ËÎÄÓ (5) â Zm , òî îíî áóäåò ðå- øåíèåì ËÎÄÓ a x b x a xi i n n1 1 0� � � � �� � , ãäå � bi — äîïîëíåíèå êîýôôèöè- åíòà ai , ò.å. � �b a mi i – , i n�1, ,� [1]. Ðàññìîòðèì ËÎÄÓ, êîòîðîå óäîâëåòâîðÿåò ñëåäóþùåìó óñëîâèþ. Óñëîâèå 1. Ñðåäè êîýôôèöèåíòîâ ËÎÄÓ ñóùåñòâóåò êîýôôèöèåíò, êîòîðûé âçàèìíî ïðîñò ñ ìîäóëåì m. Äîïóñòèì, ÷òî â äàííîì ËÎÄÓ òàêèì êîýôôèöèåíòîì ÿâëÿåòñÿ ïåðâûé íå- íóëåâîé êîýôôèöèåíò ak , k n�1 2, , ,� . Ðàññìîòðèì ìíîæåñòâî åäèíè÷íûõ âåê- òîðîâ M e en0 1� { , , }� è ôóíêöèþ L x a x a x a xn n( ) � � � �1 1 2 2 � — ëåâóþ ÷àñòü ËÎÄÓ (5). Çàìåíèì â ôóíêöèè L x( ) ïåðâûé íåíóëåâîé êîýôôèöèåíò ak , êîòî- ðûé âçàèìíî ïðîñò ñ ìîäóëåì, åãî îòðèöàòåëüíûì äîïîëíåíèåì � bk è ïîñòðî- èì ìíîæåñòâî âåêòîðîâ, êîìáèíèðóÿ åãî ñ îñòàëüíûìè íåíóëåâûìè êîýôôèöè- åíòàìè ËÎÄÓ, B a b Mj k� {( , , , , , , , , , )}0 0 0 0 0 0� � � � , ãäå M e L er r0 0� �{ : ( ) }, a j � 0 ÿâëÿåòñÿ k-é êîîðäèíàòîé, à bk ÿâëÿåòñÿ j-é êîîðäèíàòîé â âåêòîðàõ èç ìíîæåñòâà B . Èíûìè ñëîâàìè, ìíîæåñòâî B ñòðî- èòñÿ êîìáèíèðîâàíèåì äîïîëíåíèÿ ïðîèçâîëüíîãî íåíóëåâîãî êîýôôèöèåíòà, óäîâëåòâîðÿþùåãî óñëîâèþ 1 è âçÿòîãî ñ îòðèöàòåëüíûì çíàêîì, ñ îñòàëüíû- ìè íåíóëåâûìè êîýôôèöèåíòàìè è ïîïîëíÿåòñÿ åäèíè÷íûìè âåêòîðàìè, êîòî- ðûå ñîîòâåòñòâóþò íóëåâûì êîýôôèöèåíòàì ËÎÄÓ (5). Ïîñòðîåííîå òàêèì îáðàçîì ìíîæåñòâî áóäåì íàçûâàòü TSS-ìíîæåñòâîì. Î÷åâèäíî, ÷òî âåêòîðû èç ìíîæåñòâà B ÿâëÿþòñÿ ðåøåíèÿìè ËÎÄÓ (5).  ðàáîòå [1] áûëè óñòàíîâëåíû òàêèå ñâîéñòâà ðåøåíèé èç TSS. 152 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 Òåîðåìà 3. Ìíîæåñòâî B ðåøåíèé ËÎÄÓ (5), ïîñòðîåííîå êîìáèíèðîâàíèåì äîïîëíåíèÿ ïåðâîãî íåíóëåâîãî êîýôôèöèåíòà, óäîâëåòâîðÿþùåãî óñëîâèþ 1 è âçÿòîãî ñ îòðèöàòåëüíûì çíàêîì, ñ îñòàëüíûìè íåíóëåâûìè êîýôôèöèåíòàìè è ïîïîëíåííîå åäèíè÷íûìè âåêòîðàìè, êîòîðûå ñîîòâåòñòâóþò íóëåâûì êîýôôèöè- åíòàì ËÎÄÓ (5), ÿâëÿåòñÿ áàçèñîì ìíîæåñòâà âñåõ ðåøåíèé ýòîãî ËÎÄÓ. Ñëîæíîñòü àëãîðèòìà ïðîïîðöèîíàëüíà âåëè÷èíå l3 , ãäå l s n� max ( , ), s m� log — êîëè÷åñòâî äâîè÷íûõ ðàçðÿäîâ ÷èñëà m, à n — ÷èñëî íåèçâåñòíûõ â ËÎÄÓ. Èç ýòîé òåîðåìû î÷åâèäíûì îáðàçîì âûòåêàåò ñëåäñòâèå. Ñëåäñòâèå 1. Åñëè ìîäóëü m ÿâëÿåòñÿ ïðîñòûì ÷èñëîì, òî ìíîæåñòâî B ðå- øåíèé ËÎÄÓ (5) ÿâëÿåòñÿ áàçèñîì ìíîæåñòâà âñåõ ðåøåíèé ýòîãî ËÎÄÓ. Ñëîæíîñòü àëãîðèòìà ïðîïîðöèîíàëüíà âåëè÷èíå l3 , ãäå l t n� max ( , ), t — ÷èñëî ðàçðÿäîâ ïðîñòîãî ÷èñëà m, à n — ÷èñëî íåèçâåñòíûõ â ËÎÄÓ [1]. Äåéñòâèòåëüíî, åñëè ìîäóëü m — ïðîñòîå ÷èñëî, òî óñëîâèå 1 âûïîëíÿåòñÿ àâòîìàòè÷åñêè. Ïóñòü èìååì ËÍÄÓ a x a x a x bk k n n1 1 � � � � �� � , (6) â êîòîðîì êîýôôèöèåíò ak âçàèìíî ïðîñò ñ ìîäóëåì m. Íàéäåì ðåøåíèå ñðàâíåíèÿ a y b mk � (mod ), êîòîðîå ïðè äàííûõ óñëîâèÿõ áóäåò åäèíñòâåííûì. Ïóñòü ýòèì ðåøåíèåì áó- äåò c, à âåêòîð x c1 0 0 0 0� ( , , , , , , )� � áóäåò ðåøåíèåì (6). Ïðèìåíÿÿ TSS-ìå- òîä ê ËÎÄÓ, êîòîðîå ñîîòâåòñòâóåò ËÍÄÓ (6), íàõîäèì áàçèñ B ìíîæåñòâà åãî ðåøåíèé. Ïóñòü x c c cn 1 1 2� ( , , , )� — íåêîòîðîå ÷àñòíîå ðåøåíèå (6), íàéäåííîå îïè- ñàííûì âûøå ñïîñîáîì, à B e e em� { , , , }1 2 � — áàçèñ ìíîæåñòâà ðåøåíèé ËÎÄÓ a x a x a xn n1 1 2 2 0� � � �� . (7) Òåîðåìà 4. Ïðîèçâîëüíîå ðåøåíèå ËÍÄÓ (6) ïðåäñòàâëÿåòñÿ â âèäå u x� �1 � � � b ei i i m 1 , ãäå x1 — ÷àñòíîå ðåøåíèå ËÍÄÓ (6), à e em1, ,� — áàçèñíûå âåêòîðû ìíîæåñòâà ðåøåíèé ËÎÄÓ (7), êîòîðîå ñîîòâåòñòâóåò ËÍÄÓ (6) [1]. Ðàññìîòðèì ËÎÄÓ íàä ïðèìàðíûìè êîëüöàìè.  îáùåì ñëó÷àå ïðèâåäåí- íûå âûøå ñïîñîáû ðåøåíèÿ ËÎÄÓ è ËÍÄÓ íå ïðèìåíèìû. Ðàññìîòðèì ËÎÄÓ íàä ïðèìàðíûì êîëüöîì Zm L x a x a x a xi i n n( ) � � � � � �1 1 0� � , (8) ãäå a x Z m p ti i m t, , ,� � 1, t N� , i n�1, ,� . Ïóñòü ÍÎÄ( , , , , )a a a m pn u 1 2 � � , òîãäà, ñîêðàùàÿ êîýôôèöèåíòû â (8) íà pu , ïîëó÷àåì ËÎÄÓ b x b x b xn n1 1 2 2 0� � � �� (9) íàä ïðèìàðíûì êîëüöîì Zm ' , ãäå � � �m p t u� �, – . Èñõîäÿ èç ñâîéñòâà ïîëó- ÷åííîãî óðàâíåíèÿ ëþáîå ðåøåíèå ËÎÄÓ (8) áóäåò ðåøåíèåì ËÎÄÓ (9). Îáðàòíîå óòâåðæäåíèå íå èìååò ìåñòà. Äåéñòâèòåëüíî, ïóñòü êîýôôèöèåíò b1 â (9) âçàèìíî ïðîñò ñ ìîäóëåì �m . Òîãäà ñòðîèì TSS ýòîãî ËÎÄÓ, êîòîðîå â ñèëó òåîðåìû 3 ÿâëÿåòñÿ áàçèñîì åãî ìíîæåñòâà ðåøåíèé: ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 153 s b c1 2 0 0 0 0� ( , , , , , , )� , s b c2 3 0 0 0 0� ( , , , , , , )� , s b c s b cn n3 4 10 0 0 0 0 0 0 0� ��( , , , , , , ), , ( , , , , , , )� � � , ãäå c p b� �� 1 — äîïîëíåíèå êîýôôèöèåíòà b1, âçÿòîå ñ ïðîòèâîïîëîæíûì çíàêîì. Ïîñêîëüêó êîëüöî Zm ñ äåëèòåëÿìè íóëÿ, òî î÷åâèäíûì ðåøåíèåì (8) áóäåò âåêòîð s pn � ( , , , , )� 0 0 0� , êîòîðûé íå âûðàæàåòñÿ íåîòðèöàòåëüíîé ëè- íåéíîé êîìáèíàöèåé âåêòîðîâ èç TSS , òàê êàê c x p� � 0 (mod )� òîãäà è òîëüêî òîãäà, êîãäà x p� � â ñèëó âçàèìíîé ïðîñòîòû c è p� . Îäíàêî èìååò ìåñòî ñëåäóþùåå óòâåðäæåíèå. Òåoðåìà 5. Ìíîæåñòâî TSS óðàâíåíèÿ (9), äîïîëíåííîå âåêòîðîì s pn � ( , , , , )� 0 0 0� , ÿâëÿåòñÿ áàçèñîì ìíîæåñòâà ðåøåíèé ËÎÄÓ (8). Äîêàçàòåëüñòâî. Ïóñòü x d d dn� ( , , , )1 2 � — ïðîèçâîëüíîå ðåøåíèå ËÎÄÓ (8). Ïîñòðîèì âåêòîð c c s c s c s c b c b d dn n n n n� � � � � � �� � �1 1 2 2 1 1 1 2 1 2� � �( , , , ), ò.å. d c c mi i� � �(mod ), i n� 2, ,� , è ðàññìîòðèì âåêòîð c x c s c b c b dn n n n� � � � � � � ��( , , , )1 2 1 1 0 0� � ( , , , )c b c b dn n1 2 1 1 0 0� � � ���� � , ãäå ��d1 — äîïîëíåíèå � � ��d c dn1 1 (mod )�m . Ïîëó÷åííûé âåêòîð ÿâëÿåòñÿ ðåøå- íèåì (8), à ñëåäîâàòåëüíî, ÿâëÿåòñÿ ðåøåíèåì (9). Ïðåäñòàâèì ��d1 â âèäå b d1 : b d d1 1� �� (mod )p� (òàêîå ïðåäñòàâëåíèå åäèíñòâåííî â ñèëó âçàèìíîé ïðîñòîòû b1 è p�). Òîãäà c x c s c bn n� � � �( 1 2 � � � ���c b b dn n1 1 0 0, , , )� , è ïîñëå ïîäñòà- íîâêè c x� â ËÎÄÓ (9) ïîëó÷àåì b b d b c b c pn n1 1 2 1 1 0( ) (mod )�� � � � ��� � . Ñëåäîâàòåëüíî, âîçìîæíû äâà ñëó÷àÿ: à) b d b c b c upn n k 1 2 1 1 0�� � � � ��� , (mod )pt�1 ; á) b d b c b c upn n k 1 2 1 1 0�� � � � ���� , (mod )pt�1 .  ñëó÷àå à) äîêàçàòåëüñòâà íå òðåáóåòñÿ.  ñëó÷àå á) äëÿ îêîí÷àòåëüíîãî ïðåäñòàâëåíèÿ âåêòîðà x íåîáõîäèìî èç âåêòîðà x c– âû÷åñòü âåêòîð usn : x c c u sn n� � � �( ) 0 è x c c u sn n� � �( ) . Òåîðåìà äîêàçàíà. Ðàññìîòðèì îáùèé ñëó÷àé ËÎÄÓ, äëÿ êîòîðûõ íå âûïîëíÿåòñÿ óñëîâèå 1. Ïðåäïîëîæèì, ÷òî ìîäóëü m èìååò ðàçëîæåíèå íà ïðîñòûå ìíîæèòåëè âèäà m p qc d� , è äàíî ËÎÄÓ L x a x a x a xi i n n( ) � � � � � �1 1 0� � , (10) ãäå a x Zi i m, � , i n�1, ,� . Ïîñòðîèì ïî ýòîìó ËÎÄÓ äâà ËÎÄÓ: L x a x a x a xn n1 1 1 2 2 0( ) � � � � � � � �� , (11) L x b x b x b xn n2 1 1 2 2 0( ) � � � � � � � �� , (12) ãäå � �a ai i (mod )pc , � �b ai i (mod ), , ,q i nd �1 � . Èìååò ìåñòî ïðîñòîå óòâåðæäåíèå. Ëåììà 3. ËÎÄÓ (11) è (12) óäîâëåòâîðÿþò óñëîâèþ 1, ò.å. â êàæäîì èç ýòèõ óðàâíåíèé ñóùåñòâóåò ïî êðàéíåé ìåðå îäèí êîýôôèöèåíò, êîòîðûé âçàèìíî ïðîñò ñ ìîäóëåì pc è q d . Äåéñòâèòåëüíî, ðàññìîòðèì ïðîèçâîëüíûé íåíóëåâîé êîýôôèöèåíò �ai ËÎÄÓ (11). Åñëè �ai è pc âçàèìíî ïðîñòûå, òî äîêàçàòåëüñòâà íå òðåáóåòñÿ.  ïðî- òèâíîì ñëó÷àå âñå êîýôôèöèåíòû �ai äîëæíû áûòü êðàòíû pu , u c� . Ñîêðàùàÿ íà ÍÎÄ ýòèõ ÷èñåë, ïîëó÷àåì óðàâíåíèå, ýêâèâàëåíòíîå èñõîäíîìó, äëÿ êîòîðîãî âû- ïîëíÿåòñÿ óñëîâèå 1. Äîêàçàòåëüñòâî äëÿ ËÎÄÓ (12) àíàëîãè÷íî. Ëåììà äîêàçàíà. 154 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 Îòñþäà âûòåêàåò, ÷òî ËÎÄÓ (11) è (12) óäîâëåòâîðÿþò óñëîâèþ 1. Èñïîëü- çóÿ TSS-àëãîðèòì, ïîñòðîèì áàçèñû ìíîæåñòâ ðåøåíèé äëÿ îáîèõ ËÎÄÓ. Ïóñòü ýòî áóäóò ñîîòâåòñòâåííî ìíîæåñòâà � � �B e e en1 1 2 1{ , , , }� è � � �B s s sn2 1 2 1{ , , , }� . Ïîñòðîèì ìíîæåñòâà B e q e e q e e q ed d n d n1 1 1 2 2 1 1� � � � � � �� �{ , , , }� , B s p s s p s s p sc c n c n2 1 1 2 2 1 1� � � � � � �� �{ , , , }� . Èìååò ìåñòî ñëåäóþùåå óòâåðæäåíèå. Òåîðåìà 6. Ìíîæåñòâî B B B� 1 2� ÿâëÿåòñÿ áàçèñîì ìíîæåñòâà âñåõ ðåøå- íèé ËÎÄÓ (10). Äîêàçàòåëüñòâî. Î÷åâèäíî, ÷òî âåêòîðû èç B ÿâëÿþòñÿ ðåøåíèÿìè ËÎÄÓ (10). Ïóñòü x x xn� ( , , )1 � — ïðîèçâîëüíîå ðåøåíèå ËÎÄÓ (10). Åñëè x pi c� è x qi d� äëÿ âñåõ i n�1 2, , ,� , òî x ÿâëÿåòñÿ ðåøåíèåì ËÎÄÓ (11) è ËÎÄÓ (12) è, ñëåäîâàòåëüíî, ïðåäñòàâëÿåòñÿ â âèäå íåîòðèöàòåëüíîé ëèíåéíîé êîìáèíàöèè âåêòîðîâ èç B1 è B2 : x a e a e a en n� � � � � �11 1 12 2 1 1 1� â B1 è x a s a s a sn n� � � � � �21 1 22 2 2 1 1� â B2 . Äîìíîæàÿ ïåðâîå ðàçëîæåíèå íà q d , à âòîðîå íà pc , ïîëó÷àåì q x a e a e a ed n n� � � � � � � � � �� �11 1 12 2 1 1 1� â �B1, p x a s a s a sc n n� � � � � � � � � �� �21 1 22 2 2 1 1� â �B2 , ãäå � �a a qi i d 1 1 , � �d d qi i dÍÎÄ ( , ), � �a a pi i c 2 2 . Ðàññìîòðèì óðàâíåíèå âèäà q u pd c� � �� 1 0, â êîòîðîì êîýôôèöèåíòû q d , pc âçàèìíî ïðîñòû. Äàííîå óðàâíåíèå èìååò åäèíñòâåííîå ðåøåíèå ( , )u1 1� . Òîãäà ( )q u p x xd c 1 1� � �� � � � � � � � � � � � � � �� � � �u a e a e a s a sn n n n1 11 1 1 1 1 1 21 1 2 1( ) (� �� 1 ), ò.å. âåêòîð x ïðåäñòàâëÿåòñÿ â âèäå ëèíåéíîé êîìáèíàöèè âåêòîðîâ èç B B B� 1 2� . Ñëó÷àé, êîãäà íåêîòîðûå êîîðäèíàòû âåêòîðà x áîëüøå pc è q d , ëåãêî ñâî- äèòñÿ ê ïðèâåäåííîìó âûøå ñëó÷àþ. Äëÿ ýòîãî äîñòàòî÷íî ðàññìîòðåòü ïðåä- ñòàâëåíèå x x p xc� �11 12 â B1 è x x q xd� �21 22 â B2 ãäå âåêòîðû x11 è x21 èìåþò êîîðäèíàòû, ìåíüøèå pc è q d , è ÿâëÿþòñÿ ðåøåíèÿìè ËÎÄÓ (11) è ËÎÄÓ (12) ñî- oòâåòñòâåííî. Ñëåäîâàòåëüíî, x a e a e a e p xn n c� � � � �� �11 1 12 2 1 1 1 12� â B1, x a s a s a s q xn n d� � � � �� �21 1 22 2 2 1 1 22� â B2 . Íî òîãäà èìåþò ìåñòî ïðåäñòàâëåíèÿ q x a e a e a e q p xd n n d c� � � � � � � � � � � �� �11 1 12 2 1 1 1 12� � � � � � � � � � �� �a e a e a en n11 1 12 2 1 1 1� â B1, p x a s a s a s p q xc n n c d� � � � � � � � � � � �� �21 1 22 2 2 1 1 22� � � � � � � � � � �� �a s a s a sn n21 1 22 2 2 1 1� â B2 , ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 155 ãäå � �a a qi i d 1 1 , � �a a pi i c 2 2 . Òàêèì îáðàçîì, çàäà÷à ñâåëàñü ê ðàññìîòðåííî- ìó âûøå ñëó÷àþ. � Åñëè ìîäóëü m èìååò ïðåäñòàâëåíèå m p p p k k r kr� 1 2 1 2� , òî ìíîæåñòâî âñåõ ðåøåíèé ËÎÄÓ îáðàçóåò ìîäóëü V íàä êîëüöîì Zm . À ìíîæåñòâî ðåøåíèé, êî- òîðûå ïðåäñòàâëÿþòñÿ ëèíåéíûìè êîìáèíàöèÿìè âåêòîðîâ èç Bi , i r�1, ..., , ÿâ- ëÿþòñÿ ïîäìîäóëÿìè Vi ìîäóëÿ V , êîòîðûå ïîðîæäåíû áàçèñàìè Bi . Òîãäà ìî- äóëü V ðàçëàåòñÿ â ïðÿìóþ ñóììó ïîäìîäóëåé Vi , ò.å. â äàííîì ñëó÷àå V V V Vr� � � �1 2 � . Ýòî çíà÷èò, ÷òî ïðîèçâîëüíûé ýëåìåíò x V� èìååò âèä x x x xr� � � �1 2 � , ãäå x d s d s d si i i j iji i � � � �1 1 2 2 � ïðèíàäëåæèò Vi , s Bij ii � , à d d d ji1 2, , ,� ïðèíàä- ëåæàò Z Mi , M m p i i ki � , i r�1 2, , ,� . Äàííàÿ ñèòóàöèÿ äåìîíñòðèðóåòñÿ ñëåäóþùèì ïðèìåðîì. Ïðèìåð 1. Ïîñòðîèòü áàçèñ ìíîæåñòâà âñåõ ðåøåíèé â êîëüöå Z24 äëÿ ËÎÄÓ 2 3 8 6 4 0x y z u� � � � �� . Ðåøåíèå. Ìîäóëü m � � �24 3 8, îòñþäà ïîëó÷àåì äâà ËÎÄÓ: L x x y z u1 2 0 2 0 0( ) � � � � � �� â ïîëå F3 , L x x y z u2 2 3 0 6 4 0( ) � � � � � �� â êîëüöå Z8 . Ñòðîèì áàçèñû ìíîæåñòâ ðåøåíèé ýòèõ ËÎÄÓ TSS-ìåòîäîì: � �B1 2 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1{( , , , , ), ( , , , , ), ( , , , , ), ( , , , , 0)}, � �B2 5 2 0 0 0 0 0 1 0 0 0 6 0 5 0 0 4 0 0{( , , , , ), ( , , , , ), ( , , , , ), ( , , , , 5)}. Ñëåäîâàòåëüíî, B B1 18 16 0 8 0 0 0 8 0 0 0 8 0 0 0 8 0� � � � {( , , , , ), ( , , , , ), ( , , , , ), ( , 0 0 8 0, , , )}, B B2 23 15 6 0 0 0 0 0 3 0 0 0 18 0 15 0� � � � {( , , , , ), ( , , , , ), ( , , , , ), (0 12 0 0 15, , , , )}. Îòñþäà ïîëó÷àåì áàçèñ ìíîæåñòâà ðåøåíèé ËÎÄÓ B B B� �1 2 16 0 8 0 0 0 8 0 0 0 8 0 0 0 8 0 0� {( , , , , ), ( , , , , ), ( , , , , ), ( , , , , ),0 8 0 ( , , , , ), ( , , , , ), ( , , , , ), ( , , , ,15 6 0 0 0 0 0 3 0 0 0 18 0 15 0 0 12 0 0 15)}. Òàê, ðåøåíèÿ (0, 0, 0, 4, 0) è (3, 0, 1, 1, 1) èìåþò ñëåäóþùèå ïðåäñòàâëåíèÿ ÷åðåç áàçèñíûå ðåøåíèÿ: ( , , , , ) ( , , , , ) ( , , , , ) ( , , ,0 0 0 4 0 2 0 0 0 8 0 4 0 18 0 15 0 0 72 0 76� � � , )0 , ( , , , , ) ( , , , , ) ( , , , , ) ( , , , ,3 0 1 1 1 2 16 0 8 0 0 2 8 0 0 0 8 2 0 0 0 8 0� � � ) ( , , , , )� �5 15 6 0 0 0 � � � �3 0 0 3 0 0 7 0 18 0 15 0 7 0 12 0 0 15 75 24( , , , , ) ( , , , , ) ( , , , , ) ( , 0 25 121 121, , , ). Êîíåö ïðèìåðà. TSS-ÌÅÒÎÄ ÐÅØÅÍÈß ÎÁÙÅÃÎ ÂÈÄÀ ÑËÎÄÓ Èç ïðèâåäåííûõ òåîðåì âûòåêàåò ïðîöåäóðà ïîñòðîåíèÿ áàçèñà ìíîæåñòâà ðå- øåíèé ÑËÎÄÓ (1) â êîëüöå Zm , êîòîðàÿ ñîñòîèò â ðàçáèåíèè ÑËÎÄÓ S íà r ïîäñèñòåì S S r1, ,� ïî ìîäóëÿì p p k r kr 1 1, ,� ñîîòâåòñòâåííî. Êàæäàÿ èç ýòèõ ïîäñèñòåì ðåøàåòñÿ îòäåëüíî TSS-àëãîðèòìîì, íàõîäÿòñÿ áàçèñû B Br1, ,� ñî- 156 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 îòâåòñòâåííî äëÿ S S r1, ,� , à çàòåì ñòðîèòñÿ áàçèñ B m p B m p B k r k r r � 1 1 1 �� � , ãäå m p B i k i i îçíà÷àåò óìíîæåíèå êàæäîãî âåêòîðà èç Bi íà m pi ki . Ïðèìåð 2. Ïîñòðîèòü áàçèñ ìíîæåñòâà âñåõ ðåøåíèé ÑËÎÄÓ S x y z u x y z u x y z u � � � � � � � � � � � � � � � 2 3 8 6 4 0 4 6 2 3 2 0 2 3 2 2 8 � � � , , � � � �� 0 120(mod ). Ðåøåíèå.  ðåçóëüòàòå ðàçëîæåíèÿ ìîäóëÿ m � � � �120 3 5 8� ïîëó÷àåì òðè ÑËÎÄÓ: S L x y z u L x y z u L 1 11 12 13 2 0 2 0 1 0 1 0 2 0 2 0 2 � � � � � � � � � � � � � � � � , , x y z u� � � � � � � �� 0 2 2 2 0 3 � (mod ), S L x y z u L x y z u L 2 21 22 23 2 3 3 1 4 0 4 1 2 3 2 0 2 � � � � � � � � � � � � � � � � , , x y z u� � � � � � � �� 3 2 2 3 0 5 � (mod ), S L x y z u L x y z u L 3 31 32 33 2 3 0 6 4 0 4 6 2 3 2 0 2 � � � � � � � � � � � � � � � � , , x y z u� � � � � � � �� 3 2 2 0 0 8 � (mod ). Ðåøåíèÿ ÑËÎÄÓ S1 èùåì â ïîëå F3 , ÑËÎÄÓ S 2 — â ïîëå F5 , à ÑËÎÄÓ S 3 — â ïðèìàðíîì êîëüöå Z8 . Áàçèñû �B1 ÑËÎÄÓ S1 è �B2 ÑËÎÄÓ S 2 íàõîäÿòñÿ TSS-àëãîðèòìîì â ïîëÿõ Z2 è Z3 , êîòîðûé îïèñàí â ðàáîòå [4]. Ýòè áàçèñû ñîñòîÿò èç âåêòîðîâ � �B1 0 1 0 0 0 1 0 0 1 1{( , , , , ), ( , , , , )} è � �B2 1 1 0 0 0 0 0 0 3 3{( , , , , ), ( , , , , )}. Ðàññìîòðèì TSS-àëãîðèòì ïîñòðîåíèÿ áàçèñà �B3 äëÿ ÑËÎÄÓ S 3 . Ñòðîèì áà- çèñ ìíîæåñòâà ðåøåíèé äëÿ ËÎÄÓ L31 0� îïèñàííûì âûøå ñïîñîáîì. Äëÿ ýòîãî çàìåíèì êîýôôèöèåíò 3 åãî äîïîëíåíèåì � � �5 3 8 è ñòðîèì áàçèñíûå ðåøåíèÿ: B31 5 2 0 0 0 0 0 1 0 0 0 6 0 5 0 0 4 0 0� {( , , , , ), ( , , , , ), ( , , , , ), ( , , , , 5)}. Ïîäñòàâëÿÿ íàéäåííûå ðåøåíèÿ èç B31 â L32 , íàõîäèì çíà÷åíèÿ: 0, 2, 3, 2. Ñîñòàâëÿåì óðàâíåíèå 0 2 3 2 0x y z u� � � � (mod )8 . Çàìåíÿåì êîýôôèöèåíò 3 åãî äîïîëíåíèåì �5 è íàõîäèì ðåøåíèÿ: (1, 0, 0, 0), (0, 5, 2, 0), (0, 0, 2, 5). Ýòèì ðå- øåíèÿì ñîîòâåòñòâóþò áàçèñíûå ðåøåíèÿ: B32 5 2 0 0 0 0 4 5 2 0 0 0 0 2 1� {( , , , , ), ( , , , , ), ( , , , , )}. Çíà÷åíèÿ L33 íà âåêòîðàõ èç B32 : 0, 2, 4, è ïîñêîëüêó ÍÎÄ (0, 2, 4) � 2, òî ðå- øåíèÿìè óðàâíåíèÿ 0 2 0x y z� � � (mod )4 áóäóò âåêòîðû (1, 0, 0), (0, 2, 1) è (0, 4, 0). Ýòèì ðåøåíèÿì ñîîòâåòñòâóþò áàçèñíûå ðåøåíèÿ � � �B B3 33 0 0 4 0 0{ } {( , , , , )}(5, 2, 0, 0, 0), (0, 0, 2, 6,1) � . Äîìíîæàÿ âåêòîðû èç �B1 íà 2 5 403 1� � , ïîëó÷àåì áàçèñ ìíîæåñòâà ðåøåíèé äëÿ ñèñòåìû S1: B1 0 40 0 0 0 40 0 0 40 40� {( , , , , ), ( , , , , )}. Äîìíîæàÿ âåêòîðû èç �B2 íà 2 3 243 � � , ïîëó÷àåì áàçèñ ìíîæåñòâà ðåøåíèé äëÿ ñèñòåìû S 2 : B2 24 24 0 0 0 0 0 0 72 72� {( , , , , ), ( , , , , )}. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 157 Äîìíîæàÿ âåêòîðû èç �B3 íà 3 5 151 1� � , ïîëó÷àåì áàçèñ äëÿ ñèñòåìû S 3 : B3 75 30 0 0 0 0 0 30 90 15 0 0 60 0 0� {( , , , , ), ( , , , , ), ( , , , , )}. Òàêèì îáðàçîì, îêîí÷àòåëüíî áàçèñ ìíîæåñòâà ðåøåíèé äëÿ äàííîé ÑËÎÄÓ ïðèíèìàåò âèä B B B B� �1 2 3 0 40 0 0 0 40 0 0 40 40 24 24 0 0� � ( , , , , ), ( , , , , ), ( , , , , 0), ( , , , , ), ( , , , , ), ( , , , , ), ( , ,0 0 0 72 72 15 30 0 0 0 0 0 30 90 15 0 0 60, , )0 0 }. Êîíåö ïðèìåðà. Ïðèíèìàÿ âî âíèìàíèå, ÷òî àðèôìåòè÷åñêàÿ ñëîæíîñòü âûïîëíåíèÿ îïåðàöèé ñëîæåíèÿ è âû÷èòàíèÿ â êîëüöå Zm ïðîïîðöèîíàëüíà s (s — ìàêñèìàëüíàÿ ðàçðÿä- íîñòü ÷èñåë), ñëîæíîñòü îïåðàöèé óìíîæåíèÿ è äåëåíèÿ, êàê è âû÷èñëåíèÿ ÍÎÄ äâóõ ÷èñåë, ìåíüøèõ m, ïðîïîðöèîíàëüíà s2 , òî àðèôìåòè÷åñêàÿ ñëîæíîñòü ïîñòðî- åíèÿ áàçèñà ìíîæåñòâà ðåøåíèé ÑËÎÄÓ èìååò òàêèå ñîñòàâëÿþùèå: � l3 — ðåøåíèå îäíîãî ËÎÄÓ è ðåøåíèå îäíîãî ïðîìåæóòî÷íîãî ËÎÄÓ; � n l2 3 — âû÷èñëåíèå çíà÷åíèé è ñîêðàùåíèå L x( ) íà ÍÎÄ; � n l2 3 — ïîñòðîåíèå êîìáèíàöèé âåêòîðîâ, êîòîðûå ñîñòàâëÿþò áàçèñ ìíî- æåñòâà ðåøåíèé ËÎÄÓ (l n s r� max ( , , )). Ñëåäîâàòåëüíî, àðèôìåòè÷åñêàÿ ñëîæíîñòü ïåðåõîäà îò ïðåäûäóùåãî ê ñëåäó- þùåìó ËÎÄÓ â îäíîé ïîäñèñòåìå ïðîïîðöèîíàëüíà âåëè÷èíå l5 , ãäå l n s r� max ( , , ), s m� log . Òàêàÿ ïðîöåäóðà ïîâòîðÿåòñÿ r ðàç, â ðåçóëüòàòå èìååì O l( )6 , ãäå l n s k r� max ( , , , ). Òàêèì îáðàçîì, èìååò ìåñòî ñëåäóþùåå óòâåðæäåíèå. Òåîðåìà 7. Ìíîæåñòâî B , ïîñòðîåííîå TSS-ìåòîäîì, ÿâëÿåòñÿ áàçèñîì ìíî- æåñòâà ðåøåíèé ÑËÎÄÓ (1). Àðèôìåòè÷åñêàÿ ñëîæíîñòü ïîñòðîåíèÿ B ïðîïîð- öèîíàëüíà âåëè÷èíå O l( )6 , ãäå l n s k r� max ( , , , ). TSS-ÌÅÒÎÄ ÐÅØÅÍÈß ÑËÍÄÓ Ïîñòðîåíèå áàçèñà ìíîæåñòâà ðåøåíèé ÑËÍÄÓ ñâîäèòñÿ ê ïîñòðîåíèþ áàçèñà ìíîæåñòâà ðåøåíèé ðàñøèðåííîé ÑËÎÄÓ âèäà (2), êîòîðàÿ ñîîòâåòñòâóåò ÑËÍÄÓ. Íàéäÿ áàçèñ ìíîæåñòâà ðåøåíèé ðàñøèðåííîé ÑËÎÄÓ, ïîñòðîèì â íåì ðåøåíèÿ x xt1, ,� , â êîòîðûõ ïîñëåäíÿÿ êîîðäèíàòà ðàâíà åäèíèöå (åñëè äëÿ íåêîòîðîé ïîäñèñòåìû òàêîãî ðåøåíèÿ íå ñóùåñòâóåò, òî èñõîäíàÿ ÑËÍÄÓ íåñîâìåñòíà). Ñîñòàâëÿåì ñðàâíåíèå c m c m mt t1 1 1� � �� (mod ), (13) è åñëè îíî èìååò ðåøåíèå ( , , )u ut1 � , òî ÑËÍÄÓ ñîâìåñòíà è ëèíåéíàÿ êîì- áèíàöèÿ x u x u xt t 1 1 1� � �� ïðåäñòàâëÿåò ÷àñòíîå ðåøåíèå ÑËÍÄÓ, îñòàëüíûå âåêòîðû èç áàçèñà ÑËÎÄÓ áóäóò ðåøåíèÿìè ÑËÎÄÓ, êîòîðàÿ ñîîòâåòñòâóåò äàííîé ÑËÍÄÓ. Ïðàâèëüíîñòü îïèñàííîé ïðîöåäóðû âûòåêàåò èç äîêàçàííûõ âûøå òåîðåì è ëåìì. Õàðàêòåðèñòèêó âðåìåííîé ñëîæíîñòè îïðåäåëÿåò òåîðåìà 7. Ðàññìîòðèì èëëþñòðèðóþùèé ïðèìåð. Ïðèìåð 3 (çàäà÷à î ìàòåìàòè÷åñêîì ñåéôå [5]). Ìàòåìàòè÷åñêèì ñåéôîì íà- çûâàåòñÿ ñèñòåìà S Z b A k( , , , ), ãäå Z z z z zm n mn� �{ , , , ,11 12 1� } — ìíîæåñòâî çà- ìêîâ, ðàñïîëîæåííûõ â âèäå ïðÿìîóãîëüíîé ìàòðèöû A ðàçìåðà m n� , êîòîðàÿ îïðåäåëÿåò âåêòîð ñîñòîÿíèÿ çàìêîâ b b b bmn� ( , , , )1 2 � , ãäå b ki � �{ , , ,0 1 1� }, à k N� — ìîäóëü êîëüöà âû÷åòîâ Zk , â êîòîðîì ðåøàåòñÿ çàäà÷à.  ðåçóëüòàòå îä- íîãî ïîâîðîòà êëþ÷à aij ïî ÷àñîâîé ñòðåëêå âñå çàìêè â ñòðîêå i è ñòîëáöå j ìàòðè- öû A ïåðåõîäÿò èç ñîñòîÿíèÿ b â ñîñòîÿíèå ( ) (mod )b k�1 . Ñåéô ñ÷èòàåòñÿ îòêðû- 158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 òûì, åñëè îí íàõîäèòñÿ â ñîñòîÿíèè b � ( , , , )0 0 0� . Ðåøåíèå çàäà÷è ñîñòîèò â íà- õîæäåíèè äëÿ êàæäîãî çàìêà zij òàêîãî êîëè÷åñòâà ïîâîðîòîâ xij êëþ÷îì, ÷òîáû ñåéô îòêðûëñÿ. Ïóñòü X xij� | | | | — ðåøåíèå çàäà÷è, ãäå xij ðàâíî ÷èñëó ïîâîðîòîâ êëþ÷à â çàìêå zij . Òîãäà ñåéô îòêðîåòñÿ, åñëè t n it t t i m tj ijx x b � � � � �� � � 1 1 0 , (mod )k . Îáîçíà÷èì x x x x x x x x xn n mn mn� �( , , , , , , , , , , )11 12 1 21 22 2 1� � � âåêòîð-ñòîëáåö, ïîëó÷åííûé èç ìàòðèöû X ïîñëåäîâàòåëüíîé çàïèñüþ åå ñòðîê. Ïóñòü òðåáóåòñÿ îòêðûòü ñåéô Z z z� { , ,11 24� } â êîëüöå âû÷åòîâ ïî ìîäó- ëþ k � 6 c ìàòðèöåé A � � � � � � � 2 0 2 2 1 2 2 1 . Ðåøåíèå. Ñòðîèì ÑËÎÄÓ âèäà (ïîñêîëüêó â âû÷èñëåíèÿõ ôèãóðèðóþò òîëüêî êîýôôèöèåíòû ìàòðèöû ñèñòåìû, íåèçâåñòíûå xij â çàïèñè ñèñòåì îïóñêàþòñÿ) Cx � � � � � 1 1 1 1 1 0 0 0 2 0 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 2 0 1 1 1 1 0 0 0 1 2 0 , , , , , , , 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 2 0 0 0 1 0 1 1 1 1 2 0 0 0 0 1 1 1 1 1 1 0 � � � � � � � � � � � � � � � � (mod )6 , êîòîðàÿ ñîîòâåòñòâóåò âåêòîðó b � ( , , , , , , , )2 0 2 2 1 2 2 1 , ïîëó÷åííîìó èç ìàòðèöû A. Ðåøåíèå òàêîé ÑËÍÄÓ ñâîäèòñÿ ê ðåøåíèþ ÑËÎÄÓ â ïîëå F2 è ïîëå F3 , ïîñêîëüêó ìîäóëü k � 6 èìååò ðàçëîæåíèå íà ïðîñòûå ìíîæèòåëè: k . � �2 3. Ðå- øàåì ÑËÎÄÓ Cx � � � � � 1 1 1 1 1 0 0 0 2 0 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 2 0 1 1 1 1 0 0 0 1 2 0 , , , , , , , 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 2 0 0 0 1 0 1 1 1 1 2 0 0 0 0 1 1 1 1 1 1 0 � � � � � � � � � � � � � � � � (mod )2 , Cx � � � � � 1 1 1 1 1 0 0 0 2 0 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 2 0 1 1 1 1 0 0 0 1 2 0 , , , , , , , 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 2 0 0 0 1 0 1 1 1 1 2 0 0 0 0 1 1 1 1 1 1 0 � � � � � � � � � � � � � � � � (mod )3 . Ðåøåíèåì ïåðâîé ÑËÎÄÓ ÿâëÿåòñÿ âåêòîð x2 1 0 0 1 0 0 0 0 1� ( , , , , , , , , ), à âòîðîé ÑËÎÄÓ — âåêòîð x3 0 2 2 0 0 2 0 0 1� ( , , , , , , , , ). Äîìíîæàåì ïåðâîå ðåøåíèå íà 3, à âòîðîå íà 2, ïîëó÷àåì âåêòîðû � �x2 3 0 0 3 0 0 0 0 3( , , , , , , , , ) è � �x3 0 4 4 0 0 4 0 0 2( , , , , , , , , ). Ïî ïîñëåäíèì êîîðäèíàòàì ñòðîèì ñðàâíåíèå 3 2 1 6u � �� (mod ). Ýòî ñðàâ- íåíèå èìååò ðåøåíèå ( , ) ( , )u � � 1 5 . Ñòðîèì ëèíåéíóþ êîìáèíàöèþ � � � � � �x x x2 35 � ( , , , , , , , , )3 2 2 3 0 2 0 0 1 , êîòîðàÿ äàåò åäèíñòâåííîå ðåøåíèå èñõîäíîé ÑËÍÄÓ x � ( , , , , , , , )3 2 2 3 0 2 0 0 è ðåøåíèå çàäà÷è î ñåéôå ñî çíà÷åíèÿìè x11 3� , x12 2� , ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 159 x13 2� , x14 3� è x22 2� . Äåéñòâèòåëüíî, ÇÀÊËÞ×ÅÍÈÅ Ïðèâåäåííûå àëãîðèòìû èìåþò ïîëèíîìèàëüíûå îöåíêè âðåìåííîé ñëîæíîñòè ïðè óñëîâèè èçâåñòíîãî ðàçëîæåíèÿ ìîäóëÿ íà ïðîñòûå ìíîæèòåëè. Ïðîáëåìà ðàçëîæåíèÿ íàòóðàëüíîãî ÷èñëà íà ïðîñòûå ìíîæèòåëè (òàê íàçûâàåìàÿ ïðîáëå- ìà ôàêòîðèçàöèè) ÿâëÿåòñÿ îäíîé èç íàèáîëåå àêòóàëüíûõ ïðîáëåì òåîðèè ÷è- ñåë. Ñóùåñòâóåò íåñêîëüêî àëãîðèòìîâ åå ðåøåíèÿ: àëãîðèòìû Ïîëëàðäà, Ïîë- ëàðäà–Øòðàññåíà, à òàêæå àëãîðèòì ðåøåòà ÷èñëîâîãî ïîëÿ [6], êîòîðûé â íà- ñòîÿùåå âðåìÿ ÿâëÿåòñÿ íàèáîëåå ýôôåêòèâíûì. Âñå ýòè àëãîðèòìû èìåþò ýêñïîíåíöèàëüíûå îöåíêè âðåìåííîé ñëîæíîñòè, è ïîèñê áîëåå ýôôåêòèâíûõ àëãîðèòìîâ ôàêòîðèçàöèè ïðîäîëæàåòñÿ. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ê ð û â û é Ñ . Ë . Àëãîðèòìû ðåøåíèÿ ñèñòåì ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé â êîëüöàõ âû÷åòîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007. — ¹ 6. — Ñ. 27–40. 2. Ê ð û â û é Ñ . Ë . Àëãîðèòìû ðåøåíèÿ ñèñòåì ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé â öåëî÷èñëåííûõ îáëàñòÿõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 2. — Ñ. 3–17. 3. Ê ð û â û é Ñ . Ë . Àëãîðèòìû ðåøåíèÿ ñèñòåì ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé â ïîëÿõ âû÷åòîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007. — ¹ 2. — Ñ. 15–23. 4. Ä î í å ö à . À . Ðåøåíèå çàäà÷è î ñåéôå íà (0, 1)-ìàòðèöàõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2002. — ¹ 1. — Ñ. 98–105. 5. Ä î í å ö à . À . , À ã à è À ã à à ì è ø ß ê ó á . Çàäà÷à î ìàòåìàòè÷åñêîì ñåéôå íà ìàòðèöàõ. — Êèåâ: Èí-ò êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍÓ, 2013. — Ñ. 124–131. 6. × å ð å ì ó ø ê è í À .  . Ëåêöèè ïî àðèôìåòè÷åñêèì àëãîðèòìàì â êðèïòîãðàôèè. — Ì.: ÌÖÍÌÎ, 2002. — 103 ñ. Íàä³éøëà äî ðåäàêö³¿ 08.02.2016 Ñ.Ë. Êðèâèé ÀËÃÎÐÈÒÌÈ ÐÎÇÂ’ßÇÀÍÍß ÑÈÑÒÅÌ Ë²Í²ÉÍÈÕ Ð²ÂÍßÍÜ Â Ê²ËÜÖßÕ ËÈØʲ Àíîòàö³ÿ. Çàïðîïîíîâàíî ïîë³íîì³àëüí³ àëãîðèòìè ïîáóäîâè áàçèñó ìíîæè- íè ðîçâ’ÿçê³â ñèñòåìè ë³í³éíèõ îäíîð³äíèõ ³ íåîäíîð³äíèõ ä³îôàíòîâèõ ð³âíÿíü â ê³ëüö³ ëèøê³â çà ìîäóëåì äåÿêîãî ÷èñëà ïðè óìîâ³ â³äîìîãî ðîç- êëàäó ìîäóëÿ íà ïðîñò³ ìíîæíèêè. Êëþ÷îâ³ ñëîâà: ê³ëüöå ëèøê³â, ë³í³éí³ ä³îôàíòîâ³ ð³âíÿííÿ, áàçèñ ìíîæèíè ðîçâ’ÿçê³â. S.L. Kryvyi SOLUTION ALGORITHMS FOR SYSTEMS OF LINEAR EQUATIONS OVER RESIDUE RINGS Abstract. The author proposes polynomial algorithms to construct the base of the set of solutions of a system of linear Diophantine homogeneous and inhomogeneous equations in residue ring modulo some number provided that prime factorization of the modulo is known. Keywords: ring of residues, linear Diophantine equations, set of basis solutions. Êðûâûé Ñåðãåé Ëóêüÿíîâè÷, äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî, e-mail: krivoi@i.com.ua. 160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 3 2 0 2 2 1 2 2 1 2 5 3 5 5 4 2 2 1 2 1 5 1 1 4 4 2 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 3 3 1 3 3 4 4 4 1 � � � � � � � � � � � � � � � � 0 4 0 0 4 4 4 4 2 0 0 0 0 0 0 0 0 .

Ähnliche Einträge