Задача про математичний сейф та її розв'язання (частина 1)
Робота присвячена розв’язанню задачі про математичний сейф. Розглядається математична постановка задачі про математичний сейф, де показано що її розв’язання зводиться до розв’язання систем лінійних рівнянь у скінченних кільцях та полях. Також розглядаються методи та алгоритми розв’язання такого типу...
Збережено в:
| Дата: | 2020 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Назва видання: | Кібернетика та комп’ютерні технології |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/179344 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Задача про математичний сейф та її розв'язання (частина 1) / С.Л. Кривий, Г.І. Гогерчак // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 4. — С. 15-38. — Бібліогр.: 11 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-179344 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1793442021-04-30T01:26:12Z Задача про математичний сейф та її розв'язання (частина 1) Кривий, С.Л. Гогерчак, Г.І. Методи оптимізації та екстремальні задачі Робота присвячена розв’язанню задачі про математичний сейф. Розглядається математична постановка задачі про математичний сейф, де показано що її розв’язання зводиться до розв’язання систем лінійних рівнянь у скінченних кільцях та полях. Також розглядаються методи та алгоритми розв’язання такого типу систем, де наводяться методи та алгоритми побудови базису множини розв'язків систем лінійних рівнянь для цих областей та приклади для ілюстрації їх роботи. The purpose of the article is to formulate a mathematical model of the mathematical safe problem and its reduction to systems of linear equations in different domains; to consider solving the corresponding systems in finite rings and fields; to consider the principles of constructing extensions of residue fields and solving sys-tems in the relevant areas. Results. The formulation of the mathematical safe problem is given and the way of its reduction to sys-tems of linear equations is considered. Methods and algorithms for solving this type of systems are considered, where exist methods and algorithms for constructing the basis of a set of solutions of linear equations and de-rivative methods and algorithms for constructing the basis of a set of solutions of systems of linear equations for residue fields, ghost rings, finite rings and finite fields. Examples are given to illustrate their work. The principles of construction of extensions of residue fields by the module of an irreducible polynomial, and ex-amples of operations tables for them are considered. The peculiarities of solving systems of linear equations in such fields are considered separately. All the above algorithms are accompanied by proofs and estimates of their time complexity. 2020 Article Задача про математичний сейф та її розв'язання (частина 1) / С.Л. Кривий, Г.І. Гогерчак // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 4. — С. 15-38. — Бібліогр.: 11 назв. — укр. DOI:10.34229/2707-451X.20.4.2 2707-4501 http://dspace.nbuv.gov.ua/handle/123456789/179344 51.681.3 uk Кібернетика та комп’ютерні технології Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Методи оптимізації та екстремальні задачі Методи оптимізації та екстремальні задачі |
| spellingShingle |
Методи оптимізації та екстремальні задачі Методи оптимізації та екстремальні задачі Кривий, С.Л. Гогерчак, Г.І. Задача про математичний сейф та її розв'язання (частина 1) Кібернетика та комп’ютерні технології |
| description |
Робота присвячена розв’язанню задачі про математичний сейф. Розглядається математична постановка задачі про математичний сейф, де показано що її розв’язання зводиться до розв’язання систем лінійних рівнянь у скінченних кільцях та полях. Також розглядаються методи та алгоритми розв’язання такого типу систем, де наводяться методи та алгоритми побудови базису множини розв'язків систем лінійних рівнянь для цих областей та приклади для ілюстрації їх роботи. |
| format |
Article |
| author |
Кривий, С.Л. Гогерчак, Г.І. |
| author_facet |
Кривий, С.Л. Гогерчак, Г.І. |
| author_sort |
Кривий, С.Л. |
| title |
Задача про математичний сейф та її розв'язання (частина 1) |
| title_short |
Задача про математичний сейф та її розв'язання (частина 1) |
| title_full |
Задача про математичний сейф та її розв'язання (частина 1) |
| title_fullStr |
Задача про математичний сейф та її розв'язання (частина 1) |
| title_full_unstemmed |
Задача про математичний сейф та її розв'язання (частина 1) |
| title_sort |
задача про математичний сейф та її розв'язання (частина 1) |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2020 |
| topic_facet |
Методи оптимізації та екстремальні задачі |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/179344 |
| citation_txt |
Задача про математичний сейф та її розв'язання (частина 1) / С.Л. Кривий, Г.І. Гогерчак // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 4. — С. 15-38. — Бібліогр.: 11 назв. — укр. |
| series |
Кібернетика та комп’ютерні технології |
| work_keys_str_mv |
AT krivijsl zadačapromatematičnijsejftaíírozvâzannâčastina1 AT gogerčakgí zadačapromatematičnijsejftaíírozvâzannâčastina1 |
| first_indexed |
2025-07-15T18:22:58Z |
| last_indexed |
2025-07-15T18:22:58Z |
| _version_ |
1837738261892562944 |
| fulltext |
МЕТОДИ ОПТИМІЗАЦІЇ ТА ЕКСТРЕМАЛЬНІ ЗАДАЧІ
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 15
КІБЕРНЕТИКА
та КОМП'ЮТЕРНІ
ТЕХНОЛОГІЇ
Робота присвячена розв’язанню задачі про
математичний сейф. Розглядається мате-
матична постановка задачі про математи-
чний сейф, де показано що її розв’язання зво-
диться до розв’язання систем лінійних рів-
нянь у скінченних кільцях та полях. Також
розглядаються методи та алгоритми розв’я-
зання такого типу систем, де наводяться
методи та алгоритми побудови базису
множини розв'язків систем лінійних рівнянь
для цих областей та приклади для ілюстра-
ції їх роботи.
Ключові слова: математичний сейф, скін-
ченні кільця, скінченні поля, метод, алго-
ритм, розв’язок.
С.Л. Кривий, Г.І. Гогерчак, 2020
УДК 51.681.3 DOI:10.34229/2707-451X.20.4.2
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ
ТА ЇЇ РОЗВ'ЯЗАННЯ
1
(Ч. 1)
1. Вступ. Задачa про математичний сейф виникає у
теорії комп'ютерних ігр та криптографічних застосу-
ваннях і перше формулювання цієї задачі було дано
в роботі [1].
Неформально під математичним сейфом розуміють
таку систему 1 2= ( , , , )nZ z z z взаємнопов'язаних між
собою засувів, що коли виконується поворот ключа
в одному із засувів, то такий же поворот виконується
і у всіх засувах, які пов'язані з даним. Математичний
сейф може задаватися двома способами:
за допомогою прямокутної матриці елементи
якої відповідають засувам, а значення її елементів –
позиціям засувів, тобто у вигляді матриці =|| ||ijZ z ,
=1, , , =1, ,i m j n , і
за допомогою графа ( , ),G V E вершини якого
відповідають засувам.
Далі ці способи будемо називати матричним
сейфом і графовим сейфом відповідно. В матричному
сейфі кожний засув ijz пов'язаний з тими засувами,
які розміщені в i -му рядку і в j -му стовпчику.
А в графовому сейфі, пов'язаними з засувом у вершині
u є ті, які відповідають засувам розміщеним у вер-
шинах, суміжних з вершиною u . Кожний із засувів
може знаходитися в одній із декількох позицій. Всіх
можливих позицій скінченне число: 0,1, , 1k .
Засув відкритий, якщо він знаходиться в позиції 0.
В довільній іншій позиції засув вважається закритим.
Початковий стан сейфа Z при першому способі
задання визначається матрицею =|| ||ijB b , а при
другому позиціями засувів у вершинах. При цьому,
якщо в якомусь засуві виконується поворот ключа, то
всі засуви, які пов'язані з даним засувом, збільшують
свої позиції на одиницю за модулем .k
Необхідно розв'язати таку задачу. Виходячи з по-
чаткового стану сейфа, знайти таку послідовність
засувів і число поворотів ключа в них, щоб сейф
перейшов у положення відкритого, тобто коли всі
засуви знаходяться в позиції 0. Розглянемо строгу
математичну постановку задачі про матричний
математичний сейф.
1 За фінансової підтримки НАН України (проект 0118U005227)
https://doi.org/10.34229/2707-451X.20.4.2
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
16 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Математична постановка задачі. Нехай матриця =|| ||ijX x – шуканий розв'язок задачі, де ijx
дорівнює числу поворотів ключа в засуві ijz . Тоді умовою того, що елемент ijb перетвориться
матрицею X в нуль, виражається співвідношенням
=1 =1, =
0 ( ),
n m
is sj ij
s s s i
x x b mod k (1)
де =1, , , =1, ,i m j n .
Позначимо 11 1 21 2 1= ( , , , , , , , , , )n n m mnx x x x x x x вектор-стовпчик, отриманий з матриці X
послідовним записом її рядків. Аналогічно з матриці B початкових станів засувів отримаємо
вектор-стовпчик b . Крім того, нехай nJ – матриця розмірністю n n , яка складається із одиниць,
nE – одинична матриця тієї ж розмірності. Тоді розв'язок задачі про математичний сейф зводиться
до перетворення (1) для всієї матриці B і записується у вигляді системи лінійних неоднорідних
діофантових рівнянь (СЛНДР) за модулем k :
0 ( ),Ax b mod k (2)
де матриця A розмірністю mn mn складається із 2m клітинок:
= .
n n n n
n n n n
n n n n
n n n n
J E E E
E J E E
E E J EA
E E E J
(3)
Таким чином, розв'язання задачі про математичний сейф зводиться до пошуку розв'язків
системи лінійних діофантових рівнянь у скінченних полях і кільцях лишків зa модулем k .
Така постановка задачі про математичний сейф, як зазначалося вище, була дана в [1] і цю
постановку будемо називати первинною. В другій частині роботи будуть розглянуті численні
модифікації цієї постановки та методи розв'язання задачі про матетаичний сейф для цих
модифікацій над такими областями як кільце лишків mZ за модулем складеного числа m ,
поле лишків pF за модулем простого числа p та розширення поля лишків kp
F з kp елементами,
де p – просте.
2. Системи лінійних рівнянь у скінченних кільцях та полях
Кільце лишків за модулем m N – це алгебра = ( ={0,1, , 1},mZ A m 1= { , , , ,0,1}) ,
де і – бінарні асоціативно-комутативні операції додавання і множення за модулем m , пов'язані
законом дистрибутивності, унарні операції і 1 взяття протилежного і оберненого елемента
відносно операцій і відповідно, 0 і 1 – нульарні операції – адитивний нуль і мультиплікативна
одиниця [2]. Операція взяття оберненого елемента в кільці mZ у загальному випадку є частковою,
оскільки модуль m не є простим числом, то mZ матиме дільники нуля, а для дільників нуля ця
операція не визначена. На підставі законів для операцій у кільці mZ справедлива така тотожність:
( ) = = 0mx y Z x y m .
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 17
З цієї тотожності випливає, що в кільці mZ =x m y , а =y x m , що дає можливість
замінити додатне число x на від'ємне число =y x m і навпаки. Елементи x і y будемо
називати протилежними ( x протилежний до y і навпаки).
Кільце лишків mZ називається примарним, якщо модуль m є степенем простого числа p ,
тобто = tm p , де >1,t t N . Оскільки m не обов'язково просте число, то порівняння
( )ax b mod m в кільці mZ при = 0a не завжди матиме розв'язок. Це порівняння матиме
розв'язок, якщо найбільший спільний дільник (НСД) НСД( , )a m = 1 або НСД( , ) =a m d
і d – дільник числа b .
Кільце лишків mZ стає полем лишків, якщо модуль m просте число.
Розглянемо СЛНДР над кільцем mZ
1 11 1 1 1
2 21 1 2 2
1 1
( ) = = ,
( ) = = ,
= ( ),
... ... ... ... ... ... ... ... ...
( ) = = ,
q q
q q
s s sq q s
L x a x a x b
L x a x a x b
S mod m
L x a x a x b
(4)
де ,ij i ma b Z , =1, , , =1, ,i s j q .
Нехай модуль має розклад на прості множники 1 2
1 2=
k k kr
rm p p p , де 1 2< < < rp p p . Тоді
системі S відповідає еквівалентна їй система із r s рівнянь вигляду [3]
1 11 1 1 1
2 21 1 2 2 1
1
1 1
1 11 1 1 1
2 21 1 2 2
1 1
( ) = = ,
( ) = = ,
( )
... ... ... ... ... ... ... ... ...
( ) = = ,
( ) = = ,
( ) = = ,
= ... ... ... ... ... ... ... ... ...
( ) =
q q
kq q
s s sq q s
q q
q q
s s
L x a x a x b
L x a x a x b
mod p
L x a x a x b
L x a x a x b
L x a x a x b
S
L x a x
2
2
1 11 1 1 1
2 21 1 2 2
1 1
( )
= ,
( ) = = ,
( ) = = ,
( )
... ... ... ... ... ... ... ... ...
( ) = = .
k
sq q s
q q
kq q r
r
s s sq q s
mod p
a x b
L x a x a x b
L x a x a x b
mod p
L x a x a x b
(5)
Дійсно, еквівалентність систем випливає з того, що коли x – розв'язок системи S , то він буде
розв'язком і кожної із підсистем за модулем
ki
ip , оскільки модуль m ділиться на кожне з чисел
ki
ip , =1,2 ,i r . Якщо ж x – розв'язок системи S , то він буде розв'язком кожної із її підсистем за
модулем
ki
ip , а тому і розв'язком системи S за модулем m , оскільки числа
ki
ip взаємно прості та
їх добуток дорівнює m .
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
18 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Перейдемо від системи S до системи однорідних рівнянь
1 11 1 1 1 0
2 21 1 2 2 0 1
1
1 1 0
1 11 1 1 1 0
2 21 1 2 2 0
( ) = = 0,
( ) = = 0,
( )
... ... ... ... ... ... ... ... ... ...
( ) = = 0,
( ) = = 0,
( ) = = 0,
= ... ... ... ... ...
q q
kq q
s s sq q s
q q
q q
L x a x a x b x
L x a x a x b x
mod p
L x a x a x b x
L x a x a x b x
L x a x a x b x
S
2
2
1 1 0
1 11 1 1 1 0
2 21 1 2 2 0
1 1 0
( )
... ... ... ... ...
( ) = = 0,
( ) = = 0,
( ) = = 0,
( )
... ... ... ... ... ... ... ... ... ...
( ) = = 0.
k
s s sq q s
q q
kq q r
r
s s sq q s
mod p
L x a x a x b x
L x a x a x b x
L x a x a x b x
mod p
L x a x a x b x
(6)
Нехай x – розв’язок підсистеми вигляду
1 11 1 1 1 0
2 21 1 2 2 0 1
1 1
1 1 0
( ) = = 0,
( ) = = 0,
= ( )
... ... ... ... ... ... ... ... ... ...
( ) = = 0.
q q
kq q
s s sq q s
L x a x a x b x
L x a x a x b x
S mod p
L x a x a x b x
Тоді вектор 1m x , де 1
1
1
=
k
m
m
p
є розв'язком системи S . Дійсно, для другої системи 2S ,
аналогічної попередній за модулем 2
2
k
p , дістаємо для довільного її рівняння iL
2
1 1 1 2( ) = ( ) = 0 ( )
k
i i iL m x m L x m d mod p ,
=1,2 ,i s , оскільки 1m кратне 2
2
k
p , а id кратне 1
1
k
p .
Аналогічно, якщо y – розв'язок 2S , то 2m y , де 2
2
2
=
k
m
m
p
, буде розв'язком системи S і так
далі для довільної із систем 3, , rS S . Тоді загальний розв'язок системи S набуває вигляду
1 1 2 2= ,r rx m x m x m x
де ix – розв'язок системи iS .
Позначимо =i i ie m x , де ix – розв'язок системи , =1,2, ,iS i r . Покажемо, що ці вектори
лінійно незалежні над кільцем mZ . Для цього подамо вектори ie в координатній формі
1 11 1 2 21 2 1= ( , , ), = ( , , ), , = ( , , )q q k k kqe c c e c c e c c
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 19
і припустимо, що існують числа 1 2, , , ka a a , де <
ki
i ia p , такі, що
1 1 2 2 0 ( )k ka e a e a e mod m
або, що те саме 2 2 1 1 ( )k ka e a e b e mod m , де 1b протилежний до 1a в кільці mZ
і 1 1 0( )a e mod m . Приймаючи до уваги координатну форму векторів , =1,2, .ie i k , дістаємо
систему
2 2 21 1 1 1 11
2 2 22 2 1 1 12' 1
1 1
2 2 2 1 1 1
' ',
' ',
= ( ),
... ... ... ... ... ...
' ',
k k k
kk k k
q k k kq q
a m c a m c b m c
a m c a m c b m c
S mod p
a m c a m c b m c
де 'ijc – координати векторів , =1,2, ,ix i r .
З порівнянь системи '
1S випливає, що ліва частина кожного з порівнянь кратна 1
1
k
p , як і сам
модуль m . Але тоді система '
1S буде мати розв'язок тільки у випадку кратності числа 1 1b m (і тим
самим кратності 1 1ia c ) числу 1
1
k
p . Але якщо всі числа 1 1ia c кратні 1
1
k
p , то отримуємо
1 1 0 ( )a e mod m , що суперечить припущенню 1 1 0a e ( )mod m . Отримана суперечність показує
несумісність системи '
1S , а це означає лінійну незалежність сукупності векторів 1 2, , , ke e e .
Таким чином, достатньо вміти розв'язувати систему S . А розв'язання такої системи зводиться
до розв'язання систем або в полі лишків pF , або в примарному кільці за модулем степеня простого
числа.
2.1. Системи лінійних рівнянь в полі pF
Оскільки p – просте число, то в полі pF при = 0a завжди існує розв'язок порівняння
( )ax b mod p , причому цей розв'язок єдиний.
Нехай дано СЛНДР в полі pF
1 11 1 1 1
2 21 1 2 2
1 1
( ) = = ,
( ) = = ,
= ( )
... ... ... ... ... ... ... ... ...
( ) = = ,
n n
n n
q q qn n q
L x a x a x b
L x a x a x b
S mod p
L x a x a x b
(7)
де , , , =1, , , =1, ,ij i i pa b x F i n j q .
Розглянемо TSS -метод побудови базиса множини розв'язків систем лінійних однорідних
діофантових рівнянь (СЛОДР) в полі pF . Цей метод детально описаний в [4, 5], а в цьому розділі
наведемо його модифікацію орієнтовану на розв'язання задачі побудови базиса множини всіх
розв'язків СЛНДР в полі лишків pF .
Випадок лінійного однорідного діофантового рівняння (ЛОДР). Нехай дано ЛОДР
1 1( ) = = 0,i i n nL x a x a x a x (8)
де , , =1, ,i i pa x F i n . Припустимо, що = 0ia , тоді має місце таке просте твердження.
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
20 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Лема 1. Якщо 1= ( , , )nc c c – розв'язок ЛОДР (8) в pF , то він буде розв'язком ЛОДР
1 1 = 0i i n na x b x a x , де ib – протилежний до коефіцієнта ia .
Доведення. За умовою леми маємо 1 1 = 0i i n na c a c a c , але тоді
1 1 1 1= = 0i i n n i i i n na c b c a c pc a c a c a c .
Зауважимо, що коли =c k c , де =k НСД 1 2( , , , )nc c c , то 1 2= ( , , , )nc c c c теж буде
розв'язком (8). Дійсно, якщо c – розв'язок, то
1 1 2 2 1 1 2 2= ( ) = 0n n n na c a c a c k a c a c a c
і оскільки = 0k , то 1 1 2 2 = 0n na c a c a c .
Розглянемо множину векторів канонічного базису 0 1={ ,M e 2 , , }ne e і функцію
1 1 2 2( ) = n nL x a x a x a x ЛОДР (8). Замінимо в функції ( )L x перший ненульовий коефіцієнт
ka його протилежним kb і побудуємо множину векторів:
0={(0, , ,0, ,0, ,0, ,0)}j kB a b M ,
де 0 1={ : ( ) = 0}r rM e L e , = 0ja , а kb є j -ю координатою у векторах із B . Причому, якщо для
деякого ia НСД( , ) = 1i ka b , то скоротимо координати такого вектора на цей спільний дільник
(це можна зробити на підставі леми 1). Таким чином, можна вважати, що всі вектори в множині B
такі, що ia і kb взаємно прості, а множина B будується шляхом комбінування протилежного
елемента до першого ненульового коефіцієнта, взятого з від'ємним знаком, з рештою ненульових
коефіцієнтів і поповненого векторами канонічного базису, які відповідають нульовим
коефіцієнтам ЛОДР (8). Побудована таким чином множина буде називатися TSS -множиною.
Очевидно, що вектори із множини B є розв'язками ЛОДР (8).
Лема 2. Якщо = (0, ,0, ,0, ,0, ,0, ,0)i jd d d – розв'язок ЛОДР (8) , то він або є елементом B,
або представляється у вигляді невід'ємної лінійної комбінації векторів із B.
Доведення. Якщо d B , то доводити немає чого. Якщо = (0,d
,0, ,0, ,0, ,0, ,0)i jd d B , то можливі два випадки.
Випадок 1. У множині B існують вектори 1 = (0, ,0, ,is a 0, ,0, ,0, ,0)ka і
2 = (0, ,0, ,0, ,0, ,j ks a a 0, ,0) , в яких ia і ja є k -ми координатами, а ka в 1s і 2s є
відповідно i -ю і j -ю координатами. Розглянемо вектор
1 2= = (0, ,0, ,0, ,0, ,0, ,0, ,0, ,0)i j i js us vs a u a v d d ,
де ,u v – розв'язки порівнянь ( )k ia x d mod p і ( )k ja y d mod p , відповідно. В полі pF розв'язки
u і v єдині. Покажемо, що =i ja u a v 0. Для цього підставимо вектор s в ЛОДР (8):
( ) = ( ) = ( ) 0 = ( ) = 0k i j i i j j k i j k i jL s a a u a v a d a d a a u a v a a u a v
і оскільки = 0ka , то = 0i ja u a v , а це і вимагалося показати.
Випадок 2. У B існує вектор 1 = (0, ,0, ,0, ,0, ,0, ,0)i js b b . Розглянемо вектор
1= = (0, ,0, ,0, ,0, ,0, ,0)i js ys c yb ,
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 21
де y – єдиний розв'язок порівняння ( )i ib y c mod p . Оскільки x і s – розв'язки ЛОДР (8), то x s
теж буде розв'язком цього ЛОДР, тобто = (0, ,0, ,0, ,0)j jx s d b y і
( ) = ( ) = 0j j jL x s a d yb .
Оскільки = 0ja , то =j jd yb .
Теорема 1. TSS ЛОДР (8) B, побудована комбінуванням протилежного до першого
ненульового коефіцієнта, взятого з від'ємним знаком, з рештою ненульових коефіцієнтів
і поповнена векторами канонічного базису, які відповідають нульовим коефіцієнтам ЛОДР (8) ,
є базисом множини всіх розв'язків цього ЛОДР.
Часова складність алгоритму пропорціональна величині 3l , де = max( , ),l m n m – кількість
розрядів у двійковому зображенні модуля p , а n – кількість невідомих в ЛОДР.
Доведення проводиться індукцією за числом k ненульових координат у розв'язку ЛОДР.
Нехай 1 2= ( , , , )nx x x x – довільний розв'язок ЛОДР (8).
Базис індукції. Якщо =1k , то x має збігатися з одним із векторів канонічного базиса (який
за побудовою є елементом B ) і доводити немає чого. При = 2k справедливість теореми випливає
з леми 2.
Крок індукції. Припустимо, що теорема справедлива для всіх 2 <k m і x має m ненульових
координат. Розглянемо ненульові координати ,i jx x вектора x . Можливі три випадки.
Випадок 1. У B існує вектор канонічного базису s з i -ю координатою, яка дорівнює 1. Тоді
вектор = iy x x s буде мати 1m ненульових координат. За припущенням індукції для цього
вектора існує подання
1 1=i r rx x s d e d e ,
де , =1, ,ie B i r . Але тоді
1 1= i r rx x s d e d e .
Випадок 2. У B існує вектор = (0, ,0, ,0, ,0, ,i js b b 0, ,0) з ненульовими координатами ib
і jb . Розглянемо вектор
1 1 1= ( , , ,0, , , , , )i i j j nx us x x x x ub x ,
де u – розв'язок порівняння ( )i ib u x mod p . Побудований вектор має 1m ненульових координат
і за припущенням індукції отримуємо, що
1 1= r rx us d e d e або 1 1= r rx us d e d e .
Випадок 3. У B існують вектори 1 = (0, ,0, ,0, ,0, ,i ks b b 0, ,0) і 2 = (0, ,0, ,0, ,0,js b
,0, ,0)kb з ненульовими координатами ,i jb b і kb . Побудуємо вектор
1 2= = (0, ,0, ,0, ,0, ,0, ,0)j i k j k is b s b s b b b b ,
у якого після заміни k ib b його додатним протилежним ненульовими координатами будуть
координати з номерами i і j . Очевидно, що вектор s є розв'язком ЛОДР (8) і тоді на підставі
леми 2 він виражається через вектори із множини B . Нехай
1 1= (0, ,0, ,0, ,0, ,0, ,0) =j i r rs b b d e d e
це подання. Після цього доведення зводиться до випадку 2, який був вище розглянутий.
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
22 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
При отриманні оцінки часової складності елементарними вважаються операції додавання
і віднімання. При побудові TSS для ЛОДР обчислюються 1n векторів і не більше, ніж 1n
разів НСД двох чисел у полі pF . Побудова векторів вимагає, очевидно, не більше ніж ( 1)n n
кроків,
а складність обчислення НСД за допомогою алгоритма Евкліда пропорціональна 2m ,
де m – розрядність чисел, для яких обчислюється НСД [6, 7]. Додаючи всі ці величини, отримуємо
оцінку 3( )O l , де = max( , )l m n .
Приклад 1. Побудувати базис множини всіх розв'язків ЛОДР 1 2 3 4 52 0 2 = 0x x x x x
в полі лишків 3F .
Розв'язання. Перший ненульовий коефіцієнт в даному ЛОДР є 1 = 2a , а його протилежний
дорівнює 2 – 3 = –1. Отримуємо ЛОДР 1 2 3 4 50 2 = 0x x x x x . Застосовуючи TSS -метод,
отримуємо такі базисні розв'язки: 1 2 3 4= (1,1,0,0,0), = (1,0,0,1,0), = (2,0,0,0,1), = (0,0,1,0,0)e e e e .
Наприклад, очевидними розв'язками даного ЛОДР є вектори 1 = (1,1,1,1,1)c і 2 = (0,2,0,1,0)c .
Подання цих векторів через базисні вектори виглядає так:
1 1 2 3 4= = (4 ( 3),1,1,1,1) = (1,1,1,1,1)c e e e e mod , 2 1 2= 2 = (0,2,0,1,0)c e e .
Примітка: – кінець приклада.
Випадок СЛОДР. Нехай дана СЛОДР S (7). Розглянемо множину векторів канонічного
базису '
0 1 2= { , ,..., }nM s s s і перше рівняння 1 11 1 12 2 1( ) = = 0q nL x a x a x a x системи S .
Побудуємо базис 1 1={ , , }mB e e множини всіх розв'язків цього ЛОДР вище описаним способом.
Візьмемо функцію 2( )L x 21 1 22 2 2= n na x a x a x і розглянемо ЛОДР
2 1 1 2 2 2 2( ) ( ) ( ) = 0.m mL e y L e y L e y (9)
Зазначимо, що коли всі 2( ) = 0iL e , то рівняння 2( )L x лінійно виражається через 1( )L x і його
можна вилучити із СЛОДР S . Через це будемо вважати, що всі рівняння в S лінійно незалежні.
Знайдемо TSS -методом базис 1 2 1={ , , , }mB r r r множини розв'язків ЛОДР (9) і побудуємо
за векторами із B відповідні лінійні комбінації векторів із 1B . Позначимо цю множину
1={ ,M s 2 1, , }ms s .
Лема 3. Множина M – базис множини всіх розв'язків СЛОДР
1 11 1 1
2 21 1 2
( ) = = 0,
=
( ) = = 0.
n n
n n
L x a x a x
S
L x a x a x
(10)
Доведення. Очевидно, що всі елементи із M – розв'язки СЛОДР S . Нехай 1= ( , , )nx x x –
довільний розв'язок СЛОДР S , тоді 1 1= ,m mx d e d e де 1, =1, ,ie B i m . Підставляючи x
в 2( )L x , дістаємо ЛОДР
1 2 1 2 1 1( ) ( ) = = 0,m m m md L e d L e c d c d
тобто вектор 1 2( , , , )md d d є розв'язком ЛОДР (9) і, отже, він представляється у вигляді
невід'ємної лінійної комбінації векторів із B :
1 1 1 1 1( , , ) = .m m md d f r f r
Але тоді отримуємо 1 1 1 1 1 1= = ,m m m mx d e d e f s f s а це означає, що x
представляється у вигляді невід'ємної лінійної комбінації векторів із M . На підставі довільності
вектора x отримуємо справедливість леми.
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 23
Теорема 2. Нехай M – TSS -множина, побудована вищеописаним способом для СЛОДР S ,
тоді M є базисом множини всіх розв'язків цієї СЛОДР.
Складність побудови базиса пропорціональна величині 3ql , де q – число рівнянь СЛОДР,
= max( , ),l m n m – кількість розрядів у двійковому зображенні модуля p , а n – кількість
невідомих СЛОДР.
Доведення виконується індукцією за числом k рівнянь в СЛОДР S .
Базис індукції при = 2k має місце на підставі леми 3.
Крок індукції. Припустимо, що теорема справедлива для всіх <k q . Тоді TSS -множина
розв'язків СЛОДР S , що складається з перших 1q рівнянь, за припущенням індукції є базисом
множини розв'язків S .
Повторюючи викладки, аналогічні тим, які використовувалися при доведенні леми 3,
отримуємо справедливість теореми.
Оцінка часової складності, що наведена у формулюванні теореми, очевидним чином випливає
з теореми 1.
Приклад 2. Знайти в полі 3F базис множини розв'язків СЛОДР
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 0 2 = 0,
= 2 1 0 = 0,
2 2 0 = 0.
x x x x x
S x x x x x
x x x x x
Розв'язання. В прикладі 1 знайдено базис множини розв'язків першого ЛОДР цієї системи:
1 2 3 4= (1,1,0,0,0), = (1,0,0,1,0), = (2,0,0,0,1), = (0,0,1,0,0)e e e e .
Знаходимо 2 1 2 2 2 3 2 4( ) = 0, ( ) =1, ( ) = 0, ( ) =1L e L e L e L e і будуємо ЛОДР 1 20y y
3 4 1 2 3 40 = 0 2 0 = 0.y y y y y y
Базис множини розв'язків складається із векторів
1 2 3= (1,0,0,0), = (0,1,0,2), = (0,0,1,0)r r r .
Базисні вектори множини розв'язків для перших двох рівнянь із S , що відповідають векторам
1 2 3, ,r r r , є такими:
' ' '
1 1 2 2 4 3 3=1 = (1,1,0,0,0), = 2 = (1,0,2,1,0), =1 = (2,0,0,0,1)e e e e e e e .
Знаходимо значення ' ' '
3 1 3 2 3 3( ) = 2, ( ) =1, ( ) = 2L e L e L e , будуємо ЛОДР
1 2 3 1 2 32 2 = 2 = 0y y y y y y
і знаходимо його розв'язки: 1 2= (1,1,0), = (2,0,1)r r . Відповідні їм вектори базису множини
розв'язків СЛОДР S мають вигляд: ' ' ' '
1 1 2 2 1 3= = (2,1,2,1,0), = 2 = (1,2,0,0,1)s e e s e e .
2.2. TSS-метод розв'язання СЛНДР
Випадок ЛНДР. Нехай дано ЛНДР в полі pF
1 1 2 2 = .n na x a x a x b (11)
Розглянемо рівняння 1 1 2 2 0 = 0n na x a x a x bx , розв'язки якого при 0 =1x будуть
розв'язками (11). Застосовуючи TSS -метод до цього ЛОДР, знаходимо
1 1= ( ,0, , ), , = (0, ,0, , )n ns b a s b a .
Серед цих розв'язків необхідно знайти ті, у яких 0 =1x . Але 0 1 2{ , , , }nx a a a і тоді
шуканими розв'язками будуть ті розв'язки x , які є розв'язками порівняння 1( )ia x mod p .
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
24 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
На підставі простоти p це порівняння має єдиний розв'язок, причому це має місце для довільного
= 0, =1,2, ,ia i n . Отже, можна вибрати довільне = 0ia і для нього розв'язувати порівняння.
Оскільки порівняння 1( )ia x mod p має розв'язок, то і порівняння (11) теж буде мати розв'язок.
Нехай 1
1 2= ( , , , )nx c c c – деякий окремий розв'язок (11), знайдений вищеописаним способом,
а 1 2={ , , , }mB e e e базис множини розв'язків ЛОДР
1 1 2 2 = 0.n na x a x a x (12)
Лема 4. Довільний розв'язок u ЛНДР (11) записується у вигляді 1
=1
=
m
i i
i
u x b e ,
де 1x – окремий розв'язок ЛНДР (11) , а 1, , me e – базисні вектори множини розв'язків ЛОДР (12) ,
яке відповідає ЛНДР (11) .
Доведення. Нехай 1 2= ( , , , ,1)nu u u u – довільний розв'язок ЛНДР (11), а 1 2={ , , , }mB e e e –
базис множини розв'язків ЛОДР, яке відповідає (11). Розглянемо вектор
1
1 2= = ( , , , )ny u x d d d .
Якщо деякі з координат вектора y стали від'ємними, то замінимо їх додатними
протилежними. Вектор y є розв'язком ЛОДР і, отже, представляється у вигляді невід'ємної
лінійної комбінації векторів із B , тобто
=1
=
m
i i
i
y b e , , =1,2, ,ie B i m . Але тоді
1
=1
=
m
i i
i
u x b e .
Приклад 3. Знайти в полі 13F загальний розв'язок ЛНДР 2 3 5 6 4 = 7x y z u v .
Розв'язання. Виберемо перший ненульовий коефіцієнт 1 = 2a і побудуємо вектор
(7,0,0,0,0,2) . Розв'язуємо порівняння 2 1( 13)s mod . Розв'язком цього порівняння буде, очевидно,
= 7s . Тоді вектор 1 = 7(7,0,0,0,0) = (10,0,0,0,0)x буде шуканим окремим розв'язком ЛНДР.
Знайдемо базис множини розв'язків ЛОДР 2 3 5 6 4 = 0x y z u v . Замінивши, наприклад,
коефіцієнт 3 його протилежним –10 і побудуємо базис множини розв'язків ЛОДР
2 10 5 6 4 = 0x y z u v . Цими розв'язками будуть вектори:
1 2= (5,1,0,0,0), = (0,1,2,0,0),e e 3 4= (0,3,0,5,0), = (0,2,0,0,5)e e .
Отже, загальний розв'язок даного ЛНДР матиме вигляд: 1
1 1 2 2 3 3 4 4=x x b e b e b e b e .
Наприклад, при 1 2 3 4= = = =1b b b b отримуємо = (2,7,2,5,5)u .
Випадок СЛНДР. Нехай дана СЛНДР
1 11 1 1 1
2 21 1 2 2
1 1
( ) = = ,
( ) = = ,
=
... ... ... ... ... ... ... ... ...
( ) = = ,
n n
n n
q q qn n q
L x a x a x b
L x a x a x b
S
L x a x a x b
(13)
де , , , =1, , , =1, , , <ij i i pa b x F i n j q q n . Оскільки рівняння можна додавати і віднімати,
то перетворимо S до вигляду (вважаючи, що = 0qb )
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 25
' ' '
1 11 1 1
' ' '
2 21 1 2
' ' '
1 11 1 1
1 1
( ) = = 0,
( ) = = 0,
... ... ... ... ... ... ... ... ...=
( ) = = 0,
( ) = = .
n n
n n
q q q n n
q q qn n q
L x a x a x
L x a x a x
S
L x a x a x
L x a x a x b
(14)
Нехай ' ' '
1 2= { , , , }mB e e e – базис множини розв'язків СЛОДР, яка складається із перших 1q
рівнянь системи S , а 1 2={ , , , }kB e e e – базис множини розв'язків СЛОДР, яка відповідає S .
Побудуємо рівняння
' '
1 1( ) ( ) =q q m m qL e y L e y b .
Якщо всі
'( ) = 0q iL e , то дане рівняння не має розв'язків, а разом з ним не має розв'язків і
початкова СЛНДР (в цьому випадку ( )qL x лінійно залежить від
' '
1 1( ), , ( )qL x L x ). Якщо хоча б
одне
'( ) = 0q iL e , то розв'язок завжди існує і нехай 1= ( , , )my d d – розв'язок цього ЛОДР. Тоді
вектор 1 ' '
1 1= m mx d e d e є окремим розв'язком рівняння ( ) =q qL x b . Отже, загальний розв'язок
СЛОДР S , а разом з ним і розв'язок системи S , подається у вигляді
1
=1
=
k
i i
i
u x b e ,
де , =1,2, ,ie B i k .
Підсумовує сказане таке твердження.
Теорема 3. СЛНДР S, всі рівняння якої лінійно незалежні і розмірність якої q n , при <q n
завжди сумісна над полем pF і її загальний розв'язок має вигляд
1
=1
=
k
i i
i
u x b e , де 1x – деякий
окремий розв'язок S, а ie – базисні вектори множини розв'язків СЛОДР, яка відповідає даній
СЛНДР S.
Часова складність побудови загального розв'язку СЛНДР пропорціональна величині 3ql ,
де q – кількість рівнянь у системі, = max( , ),l m n m – кількість разрядів у двійковому зображенні
модуля p , а n – число невідомих в СЛНДР.
Приклад 4. Знайти в полі 3F базис множини розв'язків СЛНДР
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 0 2 = 2,
= 2 1 0 = 1,
2 2 0 = 2.
x x x x x
S x x x x x
x x x x x
Розв'язання. СЛОДР S для цієї системи отримуємо шляхом почленного віднімання третього
рівняння (хоча краще було б почленно додавати друге рівняння до першого і третього)
з відповідним коефіцієнтом від першого і другого рівнянь, тобто
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
26 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
0 1 2 2 = 0,
= 0 0 1 2 = 0,
2 2 0 = 2.
x x x x x
S x x x x x
x x x x x
Базис B підсистеми, що складається з перших двох рівнянь, включає такі вектори:
' ' '
1 2 3= (1,0,0,0,1), = (0,1,0,0,0), = (0,0,1,2,2)e e e .
Будуємо ЛОДР ' ' '
3 1 1 3 2 2 3 3 3( ) ( ) ( ) = 2L e y L e y L e y , тобто 1 2 30 = 2y y y .
Знаходимо його корені шляхом розв'язання порівняння 1 2 ( 3)x mod : '
1 = (2,0,0)x ,
'
2 = (0,2,0)x .
Вибираємо один із отриманих векторів, наприклад, другий. Цьому вектору відповідає окремий
розв'язок 1 = (0,2,0,0,0)x .
В прикладі 2.5.2 знайдений базис множини розв'язків СЛОДР, що відповідає даній СЛНДР S :
1 2= (2,1,2,1,0), = (1,2,0,0,1)s s . Отже, загальний розв'язок СЛНДР приймає вигляд:
1
1 1 2 2=u x b s b s .
Наприклад, коли 1 2= =1b b , то отримуємо 1 = (0,2,2,1,1)u .
На закінчення підрозділу наведемо висновок загального характеру. Оскільки поле pF
є простим (тобто, полем, яке не має власних підполів), а кожне просте скінченне поле ізоморфне
відповідному полю pF [2], то наведені алгоритми застосовні в кожному скінченному простому
полі.
2.3. Системи лiнiйних рiвнянь в примарному кільцi yp
Z
Нехай дано ЛОДР в кільцi y
p
Z
1 1( ) = = 0,i i n nL x a x a x a x (15)
де , , >1,i i y
p
a x Z y p – просте число, =1, ,i n , які задовольняють таку умову.
Умова 1. Серед коефіцієнтів ЛОДР існує коефіцієнт, який взаємно простий з модулем
= ym p .
Зауважимо, що для такого типу ЛОДР справедлива лемма 1. Припустимо, що в даному ЛОДР
коефіцієнтом, який задовольняє умові 1, є перший ненульовий коефіцієнт ka , [1, ]k n .
Розглянемо функцію 1 1 2 2( ) = n nL x a x a x a x ЛОДР (15). Замінимо в ній перший ненульовий
коефіцієнт ka , який взаємно простий з модулем, його протилежним kb і побудуємо множину
векторів
0={(0, , ,0, ,0, ,0, ,0)}j kB a b M ,
де 0 ={ : ( ) = 0}r rM e L e , = 0ja , а kb є j -ю координатою у векторах із B . Причому, якщо для
деякого ja НСД( , ) = 1j ka b , то скоротимо координати такого вектора на цей спільний дільник.
Отже, можна вважати, що всі вектори в множині B такі, що ja і kb взаємно прості. Побудована
таким чином множина також будемо називати TSS . Очевидно, що вектори із множини B
є розв'язками ЛОДР (15).
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 27
Лема 5. Якщо = (0, ,0, ,0, ,0, ,0, ,0)i jd d d – розв'язок ЛОДР (15), то він або є елементом
B, або представляється у вигляді невід'ємної лінійної комбінації векторів із B.
Доведення. Якщо d B , то доводити нічого. Якщо = (0,d ,0, ,0,id ,0, ,0, ,0)jd B ,
то можливі два випадки.
Випадок 1. В множині B існують вектори 1 = (0, ,0, ,is a 0, ,0, ,0, ,0)ka і 2 = (0, ,0,s
,0, ,0, ,0, ,0)j ka a , в яких ia і ja є k -ми координатами, а ka в 1s і 2s є відповідно
i -ю і j -ю координатами. Оскільки 1s і 2s – розв'язки ЛОДР (15), то 1 2= =s us vs
(0, ,0, ,0, ,0, ,0, ,0, ,0, ,0)i j i ja u a v d d теж є розв'язком цього ЛОДР, де ,u v – розв'язок
порівнянь ( )k ia x d mod m і ( )k ja y d mod m відповідно. В кільці mZ розв'язки u і v єдині на
підставі взаємної простоти ka і = ym p . Покажемо, що = 0i ja u a v . Для цього підставимо вектор
s в ЛОДР (15):
( ) = ( ) = ( ) 0 = ( ) = 0k i j i i j j k i j k i jL s a a u a v a d a d a a u a v a a u a v .
Оскільки = 0ka і не є дільником нуля, то = 0i ja u a v , що і потрібно було показати.
Випадок 2. В множині B існує вектор 1 = (0, ,0, ,is a 0, ,0, ,0, ,0)ka . Розглянемо вектор
1= = (0, ,0, ,0, ,0, ,0, ,0)i js ys ya d , де y – єдиний розв'язок порівняння ( )k ja y d modm .
Оскільки x і s – розв'язки ЛОДР (15), то d s теж буде розв'язком цього ЛОДР, тобто
= (0, ,0, ,0, ,0)i id s d a y і ( ) = ( ) = 0k i iL d s a d a y . Оскільки = 0ka і не є дільником
нуля, то =i id a y .
Теорема 4. Множина B розв'язків ЛОДР (15), побудована комбінуванням протилежного
до першого ненульового коефіцієнта, що задовольняє умові 1, з рештою ненульових коефіцієнтів
і поповнена векторами канонічного базиса, які відповідають нульовим коефіцієнтам ЛОДР (15),
є базисом множини всіх розв'язків цього ЛОДР.
Складність алгоритма побудови базиса пропорціональна величині 3l , де = max( , ),l t n
= logt m – кількість двійкових розрядів числа m , а n – кількість невідомих в ЛОДР.
Доведення проводиться індукцією за числом k ненульових координат у розв'язку ЛОДР.
Нехай 1 2= ( , , , )nx x x x – довільний розв'язок ЛОДР (15).
Базис індукції. Якщо =1k , то x має збігатися з одним із векторів канонічного базису (який за
побудовою є елементом B ) або збігатися з одним із векторів, у якого ненульова координата
є дільником нуля в кільці mZ . Перший випадок очевидний. У другому випадку вектор має вигляд
(0, ,0, ,0, ,0)jc . Виберемо розв'язок з B , в якого j -а координата ka не дорівнює нулю (такий
розв'язок має існувати за побудовою множини B ). Нехай це буде вектор
1 = (0, ,0, ,0, ,0, ,0, ,0)i ks a a . Розглянемо вектор 1=z ys , де y – розв'язок порівняння
( )k ja y c mod m (такий розв'язок існує і єдиний на підставі взаємної простоти ka і = ym p ).
Але тоді вектор z x буде мати єдину ненульову координату iya і при підстановці його в ( )L x
дістаємо 0 ( )i kya a n modm , тобто число = 0 ( )j ic a mod m . Отже, =x z .
При = 2k справедливість теореми випливає з леми 5.
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
28 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Крок індукції. Припустимо, що теорема справедлива для всіх 1 <k n і вектор-розв'язок x має
n ненульових координат. Розглянемо ненульові координати ,i jx x вектора x . Можливі такі
випадки.
Випадок 1. У B є вектор канонічного базиса s з i -ю координатою рівною одиниці.
Тоді вектор = iy x x s буде мати 1n ненульових координат. За припущенням індукції
для цього вектора існує зображення 1 1=i p px x s d e d e , де , =1, ,ie B i p . Але тоді
1 1= i p px x s d e d e .
Випадок 2. У B є вектор канонічного базиса s з єдиною ненульовою j -ю координатою
равною a , тобто a – дільник нуля в mZ . Виберемо розв'язок із B , в якому j -а координата ka не
дорівнює нулю (такий розв'язок має існувати за побудовою множини B ). Нехай це буде вектор
1 = (0, ,0, ,0, ,0, ,0, ,0)i ks a a . Розглянемо вектор 1=z ds , де d – розв'язок порівняння
( )k ja y c mod m (такий розв'язок існує і єдиний на підставі взаємної простоти ka і m ). Але тоді
вектор x z буде мати на одну ненульову координату менше, ніж x . За припущенням індукції
вектор x z має зображення (від'ємні координати заміняються своїми додатними протилежними)
1 1= p px z d e d e або 1 1 1= p px ds d e d e .
Випадок 3. У B є вектор = (0, ,0, ,0, ,0, ,0, ,0)j ks a a з k -ю і j -ю ненульовими
координатами. Розглянемо вектор
1 1 1= ( , , , , , ,0, , )k k j k nx us x x x ua x x ,
де u – розв'язок порівняння ( )k ja u x mod m . Побудований вектор має 1n ненульових
координат і за припущенням індукції отримуємо, що
1 1= p px us d e d e або 1 1= p px us d e d e .
Випадок 4. У B є вектори 1 = (0, ,0, ,0, ,0, ,0, ,0)i ks a a і 2 = (0, ,0, ,0, ,0, ,0, ,0)j ks a a
з i -ю, j -ю і k -ю ненульовими координатами. Побудуємо вектор
1 2= = (0, ,0, ,0, ,0, ,0, ,0)j i k j k is a s a s a a a a ,
у якого після заміни k ia a його додатними протилежними ненульовими координатами будуть
координати з номерами i і j . Очевидно, що вектор s є розв'язком ЛОДР (15), і тоді на підставі
леми 5 він виражається через вектори із множини B . Нехай = (0, ,0, ,0, ,0, ,0, ,0)j is b b і
1 1= r rs d e d e ці вирази. Далі доведення зводиться до вищерозглянутого випадку 3.
При отриманні оцінки складності елементарними вважаються операції додавання і віднімання
(арифметична складність виконання яких пропорціональна t ). При побудові множини TSS для
ЛОДР обчислюється 1n вектор і не більше, ніж 1n разів обчислюється НСД двох чисел
в кільці mZ . Побудова векторів потребує, очевидно, не більше ніж ( 1)n n операцій, а складність
обчислення НСД за допомогою алгоритма Евкліда пропорціональна 2t , де t – розрядність чисел
в двійковому зображенні, для яких обчислюється НСД [6, 7]. Додаючи всі ці величини, дістаємо
3l , де = max( , )l t n .
Наслідок 1. Якщо модуль m є простим числом, то множина B розв'язків ЛОДР (15) є базисом
множини всіх розв'язків цього ЛОДР.
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 29
Складність алгоритма побудови цього базиса пропорціональна величині 3l , де = max( , ),l t n
= logt m – число двійкових розрядів простого числа m , а n – кількість невідомих в ЛОДР.
Дійсно, якщо модуль m – просте число, то умова 1 виконується автоматично.
Приклад 5. Побудувати базис множини всіх розв'язків ЛОДР 1 2 3 4 52 5 7 3 6 = 0x x x x x
в кільці 12Z .
Розв'язання. Вибираємо ненульовий коефіцієнт 7, який взаємно простий з модулем 12,
замінюємо його протилежним –5 і отримуємо ЛОДР 1 2 3 4 52 5 5 3 6 = 0x x x x x . Застосовуючи
TSS -метод, знаходимо такі базисні розв'язки: 1 = (5,0,2,0,0)e , 2 = (0,1,1,0,0)e , 3 = (0,0,3,5,0)e ,
4 = (0,0,6,0,5)e .
Випадок ЛНДР. Нехай дано ЛНДР
1 1 = ,k k n na x a x a x b (16)
в якому коефіцієнт ka взаємно простий з модулем m . Знайдемо розв'язок порівняння
( )ka y b mod m , який за даних умов буде єдиним. Нехай цим числом буде c , тобто вектор
1 = (0,x ,0, ,0, ,0)c буде розв'язком (16). Застосовуючи TSS -метод до ЛОДР, яке відповідає
(16), знаходимо базис B множини його розв'язків.
Нехай 1
1 2= ( , , , )nx c c c – деякий окремий розв'язок (16), знайдений описаним вище способом,
а 1 2={ , , , }mB e e e – базис множини розв'язків ЛОДР
1 1 2 2 = 0.n na x a x a x (17)
Теорема 5. Довільний розв'язок ЛНДР (16) має вигляд =u
1
=1
m
i i
i
x b e , де 1x – окремий
розв'язок ЛНДР (16), а 1, , me e – базисні вектори множини розв'язків ЛОДР (17), яке відповідає
ЛНДР (16).
Доведення. Нехай 1 2= ( , , , )nu u u u – довільний розв'язок ЛНДР (16), а 1 2={ , , , }mB e e e –
базис множини розв'язків ЛОДР, яке відповідає (16). Розглянемо вектор 1
1 2= = ( , , , )ny u x d d d .
Якщо деякі координати у векторі y стали від'ємними, то замінимо їх додатними протилежними.
Вектор y є розв'язком ЛОДР і тому представляється у вигляді невід'ємної лінійної комбінації
векторів із B , тобто
=1
=
m
i i
i
y b e , , =1,2, ,ie B i m . Але тоді
1
=1
=
m
i i
i
u x b e .
Приклад 6. Знайти в кільці 12F загальний розв'язок ЛНДР 2 3 5x y z 6 4 = 7u v .
Розв'язання. Вибираємо ненульовий коефіцієнт 3 = 5a , який взаємно простий з 12. Розв'язуємо
порівняння 5 7( 12)s mod . Розв'язком цього порівняння є =11s . Тоді вектор 1 = (0,0,11,0,0)x
є шуканим окремим розв'язком ЛНДР.
Знайдемо базис множини розв'язків ЛОДР 2 3 5 6 4 = 0x y z u v . Для цього замінимо
коефіцієнт 5 його протилежним –7 і побудуємо базис множини розв'язків ЛОДР
2 3 7 6 4 = 0x y z u v . Цими розв'язками будуть вектори
1 2 3 4= (7,0,2,0,0), = (0,7,3,0,0), = (0,0,6,7,0), = (0,0,4,0,7)e e e e .
Отже, загальний розв'язок даного ЛНДР матиме вигляд 1
1 1 2 2 3 3 4 4=x x b e b e b e b e .
Наприклад, при 1 2 3 4= 2, = 7, = = 0b b b b дістаємо = (2,1,0,0,0)u .
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
30 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Розглянемо ЛОДР загального вигляду над примарним кільцем mZ
1 1( ) = = 0,i i n nL x a x a x a x (18)
де , , = , >1, , =1, ,y
i i ma x Z m p y y N i n . Нехай НСД( 1 2, , , , ) = ,u
na a a m p тоді, скорочуючи
(18) на ,up дістаємо ЛОДР
1 1 2 2 = 0n nb x b x b x (19)
над примарним кільцем mZ , де = , = .vm p v y u
Отримане рівняння має ту властивість, що довільний розв'язок ЛОДР (18) буде розв'язком
ЛОДР (19). Обернене твердження не має місця. Дійсно, нехай 1b в (19) взаємно простий з модулем
m . Тоді будуємо TSS цього ЛОДР, яке на підставі теореми 4 буде базисом його множини
розв'язків:
1 2 2 3= ( , ,0,0,0, ,0), = ( ,0, ,0,,0 ,0),s b c s b c
3 4 1= ( ,0,0, ,0, ,0), , = ( ,0,0,0, ,0, ),n ns b c s b c
де 1= vc b p – протилежний до коефіцієнта 1b . Оскільки кільце mZ з дільниками нуля,
то очевидним розв'язком (18) буде вектор = ( ,0,0, ,0)v
ns p , який не виражається невід'ємною
лінійною комбінацією векторів із TSS , так як 0( )vc x mod p тоді і тільки тоді, коли = vx p
на підставі взаємної простоти c і vp .
Справедлива
Теорема 6. TSS рівняння (19), серед коефіцієнтів якого є коефіцієнти, які задовольняють
умові 1, доповнена вектором ns = ( ,0,0, ,0)vp , складає базис множини розв'язків ЛОДР (18).
Доведення. Нехай 1 2= ( , , , )nx d d d – довільний розв'язок рівняння (18). Побудуємо вектор
1 1 1 1 1 2= = (n ny c s c s c b 1 2, , , ),n n nc b d d тобто ( ), = 2, ,i id c c mod m i n , 1= vc b p ,
і розглянемо вектор
1 2 1 1 1 2 1 1= ( ,0, ,0) = ( , ,0, ,0),n n n n n ny x c s c b c b d c b c b d
де 1d – протилежний до 1 1 ( )nd c d mod m . Отриманий вектор є розв'язком (18), а отже,
є розв'язком (19). Подамо 1d у вигляді 1b d , де 1 1 ( )vb d d mod p (таке подання єдине на підставі
взаємної простоти 1b і vp ). Тоді 1 2 1 1= ( ,0, ,0)n n n ny x c s c b c b b d , і після підстановки
y x в ЛОДР (19) дістаємо
1 1 2 1 1( , ) 0 ( ).v
n nb b d b c b c mod p
Отже, можливі два випадки:
а) 1 2 1 1, = 0( )l y
n nb d b c b c gp mod p ;
б) 1 2 1 1, = 0( )l y
n nb d b c b c gp mod p .
У випадку а) доводити нічого. У випадку б) для остаточного подання вектора x необхідно від
вектора x y відняти вектор ngs : ( ) = 0n nx y c g s і = ( )n nx y c g s .
Якщо для ЛОДР не виконується умова 1, то цього завжди можна досягти. Це випливає з такого
простого твердження.
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 31
Лема 6. ЛОДР (19) задовольняє умові 1, тобто в цьому рівнянні існує принаймні один
коефіцієнт, який взаємно простий з модулем = ym p .
Доведення. Розглянемо довільний ненульовий коефіцієнт ia ЛОДР (18). Якщо ia і m взаємно
прості, то доведення не потрібне. Якщо таких коефіцієнтів немає, тобто НСД( 1 2, , , ,na a a m ) =
= , <up u y , то скорочуючи на up коефіцієнти і модуль, дістаємо рівняння, яке еквівалентне
початковому і для якого виконується умова 1.
Звідси випливає, що ЛОДР (19) задовольняє умові 1. Тоді базис множини розв'язків
перетвореного ЛОДР будується TSS -алгоритмом.
2.4. TSS-метод розв'язання СЛОДР
З вищенаведених теорем випливає така процедура побудови базиса множини розв'язків
СЛОДР над примарним кільцем mZ , де = ym p . Вона зводиться до розв'язання ЛОДР
в примарному кільці mZ за допомогою TSS -метода. Проілюструємо це на прикладах.
Приклад 7, а) побудувати базис множини всіх розв'язків в кільці 8Z для СЛОДР
2 3 8 6 4 = 0,
= 4 6 2 3 2 = 0,
2 3 2 2 8 = 0.
x y z u v
S x y z u v
x y z u v
Розв'язання. В результаті приведення коефіцієнтів системи отримуємо СЛОДР:
1
1 2
3
= 2 3 0 6 4 = 0,
= = 4 6 2 3 2 = 0,
= 2 3 2 2 0 = 0.
L x y z u v
S L x y z u v
L x y z u v
Будуємо базис B СЛОДР 1S , вибираючи коефіцієнт 12 = 3a і його протилежний = 5b :
1 1 2 3 4={ = (5,2,0,0,0), = (0,0,1,0,0), = (0,6,0,5,0), = (0,4,0,0,5)}B e e e e .
Значення 2L на векторах із 1B : 0, 2, 3, 2. Дістаємо порівняння 1 2 30 2 3d d d
22 = 0 ( 8)d mod , яке має базисні розв'язки (1,0,0), (0,5,2,0), (0,0,2,5). Цим розв'язкам відповідають
базисні вектори
2 1 1 2 2 3={ =1 = (5,2,0,0,0), = 5 2 = (0,4,5,2,0),B s e s e e
3 3 4= 2 5 = (0,0,0,2,1)}s e e .
Значення 2L на векторах із 2B : 0, 2, 4. Дістаємо порівняння 1 2 30 2 4 = 0 ( 8)d d d mod , яке
має розв'язки (1,0,0), (0,2,3) і (0,4,0) (скільки НСД(2,4) = 2). Цим розв'язкам відповідають базисні
вектори початкової системи S
1 1 2 2 3 2 3={ =1 = (5,2,0,0,0), = 4 = (0,0,4,0,0), = 2 3 = (0,0,2,2,3)}B v s v s v s s .
б) побудувати базис множини всіх розв'язків в кільці 24Z для СЛОДР
2 3 8 6 4 = 0,
= 4 6 2 3 2 = 0,
2 3 2 2 8 = 0.
x y z u v
S x y z u v
x y z u v
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
32 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Розв'язання. В результаті розкладу модуля = 24 = 3 8m дістаємо дві СЛОДР:
11
1 12
13
= 2 0 0 0 1 = 0,
= = 1 0 2 0 2 = 0,
= 2 0 2 2 2 = 0,
L x y z u v
S L x y z u v
L x y z u v
21
2 22
23
= 2 3 0 6 4 = 0,
= = 4 6 2 3 2 = 0,
= 2 3 2 2 0 = 0.
L x y z u v
S L x y z u v
L x y z u v
Розв'язки СЛОДР 1S знаходимо в полі 3F , а СЛОДР 2S – в примарному кільці 8Z .
Будуємо базис 1B СЛОДР 1S : 11 ={(2,0,1,0,0),(0,1,0,0,0),(0,0,0,1,0),(1,0,0,0,1)}B .
Значення 12L на векторах із 11B : 1,0,0,0. Тоді 12 ={(0,1,0,0,0),(0,0,0,1,0),(1,0,0,0,1)}B .
Значення 13L на векторах із 12B : 0,2,1. Тоді 1 13= ={(0,1,0,0,0),(1,0,0,1,1)}B B .
Базис 2B СЛОДР 2S вищепобудований у п. а):
2 ={(5,2,0,0,0),(0,0,2,2,3)} {(0,0,4,0,0)}B .
Таким чином, остаточно отримуємо базис множини розв'язків початкової СЛОДР
1 2= 8 3 ={(0,8,0,0,0),(8,0,0,8,8),(15,6,0,0,0),(0,0,6,6,9),(0,0,12,0,0)}B B B .
В загальному випадку, якщо модуль m має розклад, який включає більше двох множників,
тобто 1 2
1 2=
y y yr
rm p p p , то отримуємо r підсистем. Приймаючи до уваги те, що арифметична
складність виконання операцій додавання і віднімання в кільці mZ пропорціональна s
( s – максимальна розрядність чисел), операцій множення і ділення, як і обчислення НСД двох
чисел, менших від m –
2s , то арифметична складність побудови базиса множини розв'язків
СЛОДР має такі складові:
3l – розв'язок одного ЛОДР і розв'язок одного проміжного ЛОДР;
2 3n l – обчислення значень і скорочення на НСД ( )L x ;
2 3n l – побудова комбінацій векторів, які складають базис множини розв'язків ЛОДР
( = max( ,l n s )).
Отже, арифметична складність переходу від попереднього до наступного ЛОДР в одній
підсистемі пропорціональна величині 5l , де = max( , , ), = logl n s r s m . Така процедура
повторюється r разів і в результаті маємо 6( )O l , де = max( , , )l n s r . Іншими словами, має місце
наступна
Теорема 7. Множина B, побудована TSS -методом, є базисом множини розв'язків СЛОДР (4) .
Арифметична складність побудови B пропорціональна величині 6( )O l , де = max( , , )l n s r .
2.5. TSS-метод розв'язання СЛНДР
Побудова базиса множини розв'язків СЛНДР зводиться до пошуку окремого розв'язку СЛНДР
і базиса множини розв'язків відповідної СЛОДР. Ця побудова виконується шляхом переходу до
розширенної СЛОДР, у якої до початкової СЛОДР додається стовпчик з вільних членів з
додатковим невідомим. Побудувавши базис множини розв'язків такої СЛОДР, виділяємо базисні
розв'язки, у яких остання координата (вона відповідає додатковій невідомій) відмінна від нуля.
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 33
Якщо таких координат немає, то початкова СЛНДР несумісна. В протилежному випадку складаємо
порівняння
1 1 =1( ),r rc z c z mod m (20)
де 1, , rc c – значення останнiх ненульових координат виділенних векторів. Якщо це порівняння
не має розв'язків, то початкова СЛНДР несумісна, в протилежному випадку за одним із його
розв'язків будуємо окремий розв'язок СЛНДР, який разом з базисними розв'язками СЛОДР, що
відповідає дані СЛНДР, утворює базис множини всіх розв'язків початкової СЛНДР.
Приклад 8. Знайти базис множини всіх розв'язків у кільці 24Z для СЛНДР
2 3 8 6 = 20,
= 4 6 2 3 = 22,
2 3 2 2 = 16.
x y z u
S 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,
x y z u v
S x y z u v
x y z u v
у якої останній стовпчик відповідає вільним членам з додатковим невідомим v . Базис множини
розв'язків даної СЛОДР знайдений у попередньому прикладі
1 2= 8 3 ={(0,8,0,0,0),(8,0,0,8,8),(15,6,0,0,0),(0,0,6,6,9),(0,0,12,0,0)}B B B .
Виділяємо вектор (8,0,0,8,8) і вектор (0,0,6,6,9) з ненульовими останніми координатами
і будуємо порівняння 8 9 =1( 24)x y mod за цими останніми координатами виділених векторів.
Це порівняння має розв'язок (-1,1) = (23,1), якому відповідає окремий розв'язок початкової СЛОДН
1 = (16,0,6,22)x . Тоді загальний розв'язок початкової СЛНДР набуває вигляду:
1= (0,8,0,0) (15,6,0,0) (0,0,12,0)x x a b c , де 24, ,a b c Z – довільні сталі.
Можна запропонувати і такий спосіб пошуку загального розв'язку СЛНДР, який виконується
за такою послідовністю кроків:
1) =1;i
2) Знайти окремий розв'язок 1x ЛНДР ( ) =i iL x b . Якщо 1x не існує, то (СТОП: розв'язків
немає), інакше на крок 3);
3) Побудувати базис 1 2={ , , , }i i i iwB e e e ЛОДР, яке відповідає ЛНДР ( ) =i iL x b ;
4) Знайти 1
1 1 1 1 1= ( ), = ( ), , = ( )i i i w i iwc L x c L e c L e , де , =1,2, ,ij ie B j w ;
5) Знайти окремий розв'язок 1y ЛНДР
1 1 1= .w w ic y c y b c (21)
Якщо 1y не існує, то (СТОП: розв'язків немає), інакше на крок 6);
6) Побудувати базис iB ЛОДР, яке відповідає (21);
7) Побудувати базис 1iB для ЛНДР 1 1( ) =i iL x b , виходячи з iB ;
8) Якщо 1<i r , то ( = 1i i ; на крок 4)), інакше (СТОП: друкувати 1iB ).
Правильність цієї процедури випливає з доведених вище теорем і лем.
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
34 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Приклад 9, а) знайти в кільці 12Z загальний розв'язок СЛНДР
1 2 3 4 5
1 2 3 4 5
2 3 8 6 4 = 8,
=
4 3 6 6 8 = 6.
x x x x x
S
x x x x x
Розв'язання. Розширена СЛОДР для даної СЛНДР має вигляд:
1 2 3 4 5 6
1 2 3 4 5 6
2 3 8 6 4 4 = 0,
=
4 3 6 6 8 6 = 0.
x x x x x x
S
x x x x x x
Оскільки розклад 12 на прості множники має вигляд =12 = 3 4m , то побудова базиса
множини розв'язків розширеної СЛОДР розпадається на дві підсистеми:
1 2 3 4 5 6
1
1 2 3 4 5 6
2 0 2 0 1 1 = 0,
=
1 0 0 0 2 0 = 0,
x x x x x x
S
x x x x x x
розв'язки якої шукаються в полі 3F і
1 2 3 4 5 6
2
1 2 3 4 5 6
2 3 0 2 0 0 = 0,
=
0 3 2 2 0 2 = 0,
x x x x x x
S
x x x x x x
розв'язки якої шукаються в примарному кільці 4Z .
Базис множини розв'язків системи 1S складають вектори:
1 ={(0,1,0,0,0,0),(1,0,0,0,1,0),(0,0,0,1,0,0),(0,0,1,0,0,1)}B .
Базис множини розв'язків системи 2S складають вектори:
2 ={(1,2,1,0,0,0),(1,2,0,0,0,1),(0,2,0,1,0,0),(0,0,0,0,1,0),(2,0,0,0,0,0)}B .
Тоді базис множини розв'язків розширеної СЛОДР для даної СЛНДР приймає вигляд:
1 2 1 2 1=12 / 3 12 / 4 = 4 3 ={ = (0,4,0,0,0,0),B B B B B s
2 3 4 1( = (4,0,0,0,4,0), = (0,0,4,0,0,4), = (0,0,0,4,0,0), = (3,6,3,0,0,0),s s s v
2 3 4 5= (3,6,0,0,0,3), = (0,6,0,3,0,0), = (6,0,0,0,0,0), = (0,0,0,0,3,0)}v v v v .
Складаємо порівняння за останніми координатами розв'язків 3s і 2v : 3 4 1( 12)x y mod .
Це порівняння має єдиний розв'язок 1 2( , ) = (11,1)u u , що дає окремий розв'язок СЛНДР
1 =11(3,6,0,0,0) (0,0,4,0,0) = (33,66,4,0,0) = (9,6,4,0,0)x .
Таким чином, загальний розв'язок СЛНДР має вигляд:
1
1 1 2 2 3 4 1 1 2 3 3 4 4 5=x x a s a s a s b v b v b v b v ,
де 3 4,i ja F b Z .
б) знайти в кільці 12Z загальний розв'язок СЛНДР
1 2 3 4 5
1 2 3 4 5
2 3 8 6 4 = 8,
=
4 3 6 6 8 = 5.
x x x x x
S
x x x x x
Розв'язання. Загальний розв'язок першого ЛНДР був знайдений в попередньому прикладі:
8
1
=1
= ,i i
i
x x a e де 1 = (4,4,0,0,0),x а
1 2 3 4= (2,0,1,0,0), = (0,4,0,0,0), = (0,0,0,2,0), = (2,0,0,0,2),e e e e
5 6 7 8= (3,6,0,0,0), = (0,2,0,1,0), = (0,0,3,0,0), = (0,0,0,0,3).e e e e
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 35
Підставляючи ці вектори в друге рівняння СЛНДР, дістаємо такі значення: 1
2 ( )L x = 4, а на
решті векторів – значення 2, 0, 0, 0, 6, 0, 6, 0. Будуємо рівняння (для простоти пропущені нульові
коефіцієнти) 1 2 32 6 6 = 5 4 =1y y y . Отримане рівняння не має розв'язків, оскільки НСД модуля
і коефіцієнтів дорівнює 2, а 2 не ділить вільний член 1. Отже, початкова СЛНДР несумісна.
Зауважимо, що наведені алгоритми мають поліноміальні оцінки часової складності за умови
відомого розкладу модуля на прості множники. Проблема розкладу натурального числа на прості
множники (яка називається проблемою факторизації) є однією з важливих проблем теорії чисел.
Існує декілька алгоритмів її розв'язання: алгоритм Полларда, Полларда – Штрассена, решета
числового поля [8]. Найбільш ефективним алгоритмом в даний час є останній з алгоритмів. Всі ці
алгоритми мають експоненціальні оцінки часової складності, найкраща з яких для заданого числа
n має вигляд
ln ln ln(2 )c n nO .
2.6. Скінченні поля та системи лiнiйних рiвнянь над цими полями
Відомо, що виходячи з поля лишків Fp можна побудувати скінченне поле, яке має pn елементів
[2, 8, 9]. Спосіб побудови такого поля грунтується на викориcтанні незвідного полінома над
полем Fp.
Означення 1. Поліном ( ) ( )f x G x називається незвідним над полем G, якщо він має
додатний степінь, і з рівності ( ) = ( )f x g x ( )h x , де ( ), ( ) ( )g x h x G x , випливає, що або поліном
( )g x
є константою, або поліном ( )h x є константою.
Зауважимо, що для поліномів ( )f x і ( )g x , де ( ) = 0g x як і при діленні цілих чисел, має місце
теорема про ділення поліномів з остачею
( ) = ( ) ( ) ( ),f x g x h x r x (22)
де ( ), ( ) ( )g x r x G x і ( ) < ( )deg r deg g . Це означає, що при діленні многочленів можна
застосовувати алгоритм Евкліда, подібно до того як цим алгоритмом користуються при діленні
цілих чисел.
Означення 2. Нехай ( ), ( ), ( ) ( )f x g x h x G x , де ( ) = 0g x , задовольняють умові (22). Тоді
поліном ( )r x називається остачею від ділення полінома ( )f x на поліном ( )g x . Цей поліном
позначається як = ( )r f mod g . Остачі від ділення всіх поліномів із множини ( )G x за модулем
полінома ( )g x називаються поліномами із множини ( )G x за модулем полінома ( )g x . Множина
всіх таких поліномів позначимо ( )gG x .
Очевидно, що степені всіх поліномів із ( )gG x менші ( )deg g .
Теорема 8. Нехай G – поле, а ( )f x – ненульовий поліном із ( )G x . Тоді ( )fG x буде полем
тоді і тільки тоді, коли f незвідний поліном над полем ( )G x [8–10].
Незвідний поліном ( )f x називається визначальним поліномом поля ( )fG x .
Теорема 9. Нехай G скінченне поле, порядок якого p , де p – просте число, а f – незвідний
поліном над полем G степеня n . Тоді | ( ) |= n
fG x p .
Доведення. Із означення поля ( )fG x випливає, що множина ( )G x складається із поліномів,
степінь яких менший = ( )n deg f , а їх коефіцієнти належать полю G . Але таких поліномів
буде np .
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
36 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
Наслідок 2. Для кожного простого числа p і кожного n N існує скінченне поле, яке
складається із np елементів.
Побудова такого поля виконується за допомогою лишків від ділення незвідного полінома над
полем pF . Реалізація алгоритму побудови полів kp
F з оцінками часової складності розглядалися
в роботах [8, 9], тому розглянемо лише прості приклади побудови таких полів (див. [10, 11]).
Приклад 10, a) нехай F2 – поле лишків за модулем 2. Поліном 2( ) = 1f x x x незвідний над
полем 2F . Множина
2 ( )fG x є полем, яке має 22 елементів. Їх степені менші 2 і тому довільний
елемент y із цього поля буде таким: 1 0=y b x b , де 2ib F , = 0,1i . Табл. 1, 2 Келі для поля 2
fG
набувають вигляду:
ТАБЛИЦЯ 1 ТАБЛИЦЯ 2
+ 0 1 x 1x * 0 1 x 1x
0 0 1 x 1x 0 0 0 0 0
1 1 0 1x x 1 0 1 x 1x
x x 1x 0 1 x 0 x 1x 1
1x 1x x 1 0 1x 0 1x 1 x
Якщо позначити поліноми x i 1x числами 2 і 3 відповідно, то табл. 3, 4 Келі для операцій
набувають вигляду:
ТАБЛИЦЯ 3 ТАБЛИЦЯ 4
+ 0 1 2 3 0 1 2 3
0 0 1 2 3 0 0 0 0 0
1 1 0 3 2 1 0 1 2 3
2 2 3 0 1 2 0 2 3 1
3 3 2 1 0 3 0 3 1 2
б) аналогiчним чином будується поле i друге поле 23
F над полем лишків 3F за допомогою
незвідного полінома 2 2x x (табл. 5 і 6):
ТАБЛИЦЯ 5 ТАБЛИЦЯ 6
+ 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8
0 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0
1 1 2 0 4 5 3 7 8 6 1 0 1 2 3 4 5 6 7 8
2 2 0 1 5 3 4 8 6 7 2 0 2 1 6 8 7 3 5 4
3 3 4 5 6 7 8 0 1 2 3 0 3 6 7 1 4 5 8 2
4 4 5 3 7 8 6 1 2 0 4 0 4 8 1 5 6 2 3 7
5 5 3 4 8 6 7 2 0 1 5 0 5 7 4 6 2 8 1 3
6 6 7 8 0 1 2 3 4 5 6 0 6 3 5 2 8 7 4 1
7 7 8 6 1 2 0 4 5 3 7 0 7 5 8 3 1 4 2 6
8 8 6 7 2 0 1 5 3 4 8 0 8 4 2 7 3 1 6 5
де x позначене числом 3, 1x – числом 4, 2x – числом 5, 2x – числом 6, 2 1x – числом 7,
2 2x – числом 8.
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.4 37
Застосування TSS -алгоритма в таких полях, на відміну від поля, розглянутого вище Fp,
вимагає наявності таблиць операцій додавання і множення.
Приклад 11. Розв'язати в полi 22
F СЛОДР
1 1 1 1 0 0 1
1 1 1 0 1 0 2
1 1 1 0 0 1 3
= 0.
1 0 0 1 1 1 0
0 1 0 1 1 1 1
0 0 1 1 1 1 1
Ax
(23)
Розв'язання. Застосовуючи TSS -алгоритм, дiстаємо розв'язки першого рiвняння
(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).
Значення лiвої частині другого рівняння, обчислені за таблицями додавання і множення в полі
22
F , дорівнюють: 3,3,3,2,1,0. За цими значеннями комбінуванням першого розв'язку з рештою,
дістаємо розв'язки першого і другого рівнянь системи:
(1,1,0,0,0,0,0), (1,0,1,0,0,0,0), (2,0,0,3,0,0,1), (1,0,0,0,3,0,1), (0,0,0,0,0,1,0).
Значення лівої частини третього рівняння дорівнюють: 0,0,1,2,1. За цими значениям
комбінуванням останнього розв'язку з третім і четвертим, отримуємо розв'язки перших трьох
рівнянь системи:
(1,1,0,0,0,0,0), (1,0,1,0,0,0,0), (2,0,0,3,0,1,1), (1,0,0,0,3,2,1).
Значення лівої частини четвертого рівняння: 1,1,0,0. За цими значеннями комбінуванням
першого з другим розв'язком, дістаємо розв'язки перших чотирьох рівнянь системи:
(0,1,1,0,0,0,0), (2,0,0,3,0,1,1), (1,0,0,0,3,2,1).
Значення лівої частини п'ятого рівняння: 1,3,0. За цими значеннями комбінуванням першого
з другим розв'язком, дістаємо розв'язки перших п'яти рівнянь системи:
(2,3,3,3,0,1,1), (1,0,0,0,3,2,1).
Значення лівої частини шостого рівняння: 0,0. Це означає, що обидва вектори є розв'язками
початкової системи.
Добре відомо, що скінченні поля однакових порядків ізоморфні між собою. Отже, наведені
методи розв’язання систем лінійних рівнянь застосовні в довільному такому полі.
Висновки. В першій частині роботи наведено формулювання задачі про математичний сейф
та її редукція до задачі розв’язання систем лінійних рівнянь у скінченних кільцях та полях.
Розглянуто методи і алгоритми побудови базисів множини розв’язків систем лінійних рівнянь у
скінченних кільцях і полях та наведені оцінки часової складності алгоритмів та особливості їх
застосувань.
Розглянуті методи і алгоритми будуть застосовані до розв’язання задачі про математичний
сейф, що становить предмет розгляду другої частини даної роботи.
Список літератури
1. Донец Г.А. Решение задачи о сейфе на (0,1) – матрицах. Кибернетика и системный анализ. 2002. 38 (1).
С. 98–105.
2. Калужнин Л.А. Введение в общую алгебру. М.: Наука, 1973. 447 с.
3. Крывый С.Л. Алгоритмы решения систем линейных диофантовых уравнений в кольцах вычетов. Кибернетика
и системный анализ. 2016. 52 (5). С. 149–160.
4. Крывый С.Л. Алгоритмы решения систем линейных диофантовых уравнений в полях вычетов. Кибернетика
и системный анализ. 2007. 43 (2). C. 15–23.
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
38 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 4
5. Кривий С.Л. Лінійні діофантові обмеження та їх застосування. Чернівці-Київ: Букрек, 2015. 224 с.
6. Коблиц Н. Курс теории чисел и криптографии. М.: Изд-во ТВП, 2001. 260 с.
7. Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии. М.: МЦНМО, 2002. 103 с.
8. Крывый С.Л., Гогерчак Г.И. Алгоритм решения систем линейных уравнений в поле
.kpF Проблемы управле-
ния и информатики. 2019. 5. С. 5–22.
9. Lidl R., Niederreiter H. Finite fields. Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading
MA, 1982. 20. P. 273–280.
10. Menezes A.J., Van Oorschot P.C., Vanstons S.A. Handbook of Applied Cryptography. CRC Press, 1996. 661 p.
11. Гаврилкевич М.В., Солодовников В.И. Эффективные алгоритмы решения задач линейной алгебры над полем
из двух элементов. Обозрение прикладной промышленной математики. 1995. 2 (3). С. 400 – 437.
Одержано 06.11.2020
Кривий Сергій Лук’янович,
доктор фізико-математичних наук, професор
Київського національного університету імені Тараса Шевченка, Київ,
https://orcid.org/0000-0003-4231-0691
sl.krivoi@gmail.com
Гогерчак Григорій Іванович,
аспірант Київського національного університету імені Тараса Шевченка, Київ.
https://orcid.org/0000-0002-6898-2536
gogerchak.g@gmail.com
UDC 51.681.3
S. Kryvyi, H. Hoherchak
The Mathematical Safe Problem and Its Solution (P. 1)
Taras Shevchenko National University of Kyiv, Ukraine
Correspondence: sl.krivoi@gmail.com
Introduction. The problem of the mathematical safe arises in the theory of computer games and crypto-
graphic applications. The article considers the formulation of the mathematical safe problem and the approach
to its solution using systems of linear equations in finite rings and fields.
The purpose of the article is to formulate a mathematical model of the mathematical safe problem and
its reduction to systems of linear equations in different domains; to consider solving the corresponding systems
in finite rings and fields; to consider the principles of constructing extensions of residue fields and solving sys-
tems in the relevant areas.
Results. The formulation of the mathematical safe problem is given and the way of its reduction to sys-
tems of linear equations is considered. Methods and algorithms for solving this type of systems are considered,
where exist methods and algorithms for constructing the basis of a set of solutions of linear equations and de-
rivative methods and algorithms for constructing the basis of a set of solutions of systems of linear equations
for residue fields, ghost rings, finite rings and finite fields. Examples are given to illustrate their work. The
principles of construction of extensions of residue fields by the module of an irreducible polynomial, and ex-
amples of operations tables for them are considered. The peculiarities of solving systems of linear equations in
such fields are considered separately. All the above algorithms are accompanied by proofs and estimates of
their time complexity.
Conclusions. The considered methods and algorithms for solving linear equations and systems of linear
equations in finite rings and fields allow to solve the problem of a mathematical safe in many variations of its
formulation. The second part of the paper will consider the application of these methods and algorithms to
solve the problem of mathematical safe in its various variations.
Keywords: mathematical safe, finite rings, finite fields, method, algorithm, solution.
https://orcid.org/0000-0003-4231-0691
mailto:sl.krivoi@gmail.com
https://orcid.org/0000-0002-6898-2536
mailto:gogerchak.g@gmail.com
mailto:sl.krivoi@gmail.com
|