Задача про математичний сейф та її розв'язання (частина 2)
Мета статті. Представлення методів розв’язання задачі про математичний сейф (в матричному та графовому виглядах) для різноманітних її варіацій, які пов’язані як з областю, над якою розглядається задача, так і зі структурою систем лінійних рівнянь над цими областями. Розглянуто розв’язання відповідн...
Gespeichert in:
| Veröffentlicht in: | Кібернетика та комп’ютерні технології |
|---|---|
| Datum: | 2021 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2021
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/179350 |
| 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: | Задача про математичний сейф та її розв'язання (частина 2) / С.Л. Кривий, Г.І. Гогерчак // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 1. — С. 16-28. — Бібліогр.: 3 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-179350 |
|---|---|
| record_format |
dspace |
| spelling |
Кривий, С.Л. Гогерчак, Г.І. 2021-04-29T19:04:12Z 2021-04-29T19:04:12Z 2021 Задача про математичний сейф та її розв'язання (частина 2) / С.Л. Кривий, Г.І. Гогерчак // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 1. — С. 16-28. — Бібліогр.: 3 назв. — укр. MSC 12F05, 68W05 2707-4501 DOI: https://doi.org/10.34229/2707-451X.21.1.2 https://nasplib.isofts.kiev.ua/handle/123456789/179350 51.681.3 Мета статті. Представлення методів розв’язання задачі про математичний сейф (в матричному та графовому виглядах) для різноманітних її варіацій, які пов’язані як з областю, над якою розглядається задача, так і зі структурою систем лінійних рівнянь над цими областями. Розглянуто розв’язання відповідних систем у скінченних простих полях, скінченних полях, примарних кільцях лишків та скінченних кільцях. Всі наведені алгоритми мають оцінки часової складності. Результати. Наведено приклади розв’язання задачі про математичний сейф, умови існування розв’язків в різних областях, над якими ця задача розглядається (скінченні прості поля, скінченні поля, примарні кільця, і асоціативно-комутативні кільця з одиницею). Вибір відповідної області над якою розглядається задача про математичний сейф, та відповідного алгоритму розв’язання залежить від кількості позицій засувів сейфа. Всі наведені алгоритми супроводжуються оцінками їх часової складності, які розглядалися в першій частині даної роботи.. Цель статьи. Представить методы решения задачи о математическом сейфе для различных ее вариаций, которые связаны как с областью, над которой рассматривается задача, так и со структурой систем линейных уравнений над этими областями. Рассмотреть задачу о математическом сейфе (в матричном и графовом видах) в разных вариациях над различными конечными областями и продемонстрировать работу методов решения этой задачи и их эффективность (системы над конечными простыми полями, конечными полями, примарными кольцами и конечными ассоциативно-коммутативными кольцами). Результаты. Приведены различные вариации задачи о математическом сейфе, условия существования решений в различных областях, над которыми эта задача рассматривается. Каждая вариация задачи о математическом сейфе и метод ее решения иллюстрируется на примерах. Выбор области, над которой рассматривается задача о математическом сейфе, зависит от числа позиций замков. Описываются вариации задачи как на основе изменения структуры матрицы системы, так и комбинации, открывающей сейф над конечным полями и кольцами. Все приведенные алгоритмы имеют оценки временной сложности, которые приводились в первой части этой работы. The purpose of the article. To present methods for solving the problem of a mathematical safe for its various variations, which are related both to the domain over which the problem is considered and to the structure of systems of linear equations over these domains. To consider the problem of a mathematical safe (in matrix and graph forms) in different variations over different finite domains and to demonstrate the work of methods for solving this problem and their efficiency (systems over finite simple fields, finite fields, ghost rings and finite associative-commutative rings). Results. Examples of solving the problem of a mathematical safe, the conditions for the existence of solutions in different areas, over which this problem is considered. The choice of the appropriate area over which the problem of the mathematical safe is considered, and the appropriate algorithm for solving it depends on the number of positions of the latches of the safe. All these algorithms are accompanied by estimates of their time complexity, which were considered in the first part of this paper. За фінансової підтримки НАН України (проект 0118U005227) uk Інститут кібернетики ім. В.М. Глушкова НАН України Кібернетика та комп’ютерні технології Методи оптимізації та екстремальні задачі Задача про математичний сейф та її розв'язання (частина 2) Задача о математическом сейфе и ее решение (часть 2) The mathematical safe problem and its solution (part 2) Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Задача про математичний сейф та її розв'язання (частина 2) |
| spellingShingle |
Задача про математичний сейф та її розв'язання (частина 2) Кривий, С.Л. Гогерчак, Г.І. Методи оптимізації та екстремальні задачі |
| title_short |
Задача про математичний сейф та її розв'язання (частина 2) |
| title_full |
Задача про математичний сейф та її розв'язання (частина 2) |
| title_fullStr |
Задача про математичний сейф та її розв'язання (частина 2) |
| title_full_unstemmed |
Задача про математичний сейф та її розв'язання (частина 2) |
| title_sort |
задача про математичний сейф та її розв'язання (частина 2) |
| author |
Кривий, С.Л. Гогерчак, Г.І. |
| author_facet |
Кривий, С.Л. Гогерчак, Г.І. |
| topic |
Методи оптимізації та екстремальні задачі |
| topic_facet |
Методи оптимізації та екстремальні задачі |
| publishDate |
2021 |
| language |
Ukrainian |
| container_title |
Кібернетика та комп’ютерні технології |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Задача о математическом сейфе и ее решение (часть 2) The mathematical safe problem and its solution (part 2) |
| description |
Мета статті. Представлення методів розв’язання задачі про математичний сейф (в матричному та графовому виглядах) для різноманітних її варіацій, які пов’язані як з областю, над якою розглядається задача, так і зі структурою систем лінійних рівнянь над цими областями. Розглянуто розв’язання відповідних систем у скінченних простих полях, скінченних полях, примарних кільцях лишків та скінченних кільцях. Всі наведені алгоритми мають оцінки часової складності. Результати. Наведено приклади розв’язання задачі про математичний сейф, умови існування розв’язків в різних областях, над якими ця задача розглядається (скінченні прості поля, скінченні поля, примарні кільця, і асоціативно-комутативні кільця з одиницею). Вибір відповідної області над якою розглядається задача про математичний сейф, та відповідного алгоритму розв’язання залежить від кількості позицій засувів сейфа. Всі наведені алгоритми супроводжуються оцінками їх часової складності, які розглядалися в першій частині даної роботи..
Цель статьи. Представить методы решения задачи о математическом сейфе для различных ее вариаций, которые связаны как с областью, над которой рассматривается задача, так и со структурой систем линейных уравнений над этими областями. Рассмотреть задачу о математическом сейфе (в матричном и графовом видах) в разных вариациях над различными конечными областями и продемонстрировать работу методов решения этой задачи и их эффективность (системы над конечными простыми полями, конечными полями, примарными кольцами и конечными ассоциативно-коммутативными кольцами). Результаты. Приведены различные вариации задачи о математическом сейфе, условия существования решений в различных областях, над которыми эта задача рассматривается. Каждая вариация задачи о математическом сейфе и метод ее решения иллюстрируется на примерах. Выбор области, над которой рассматривается задача о математическом сейфе, зависит от числа позиций замков. Описываются вариации задачи как на основе изменения структуры матрицы системы, так и комбинации, открывающей сейф над конечным полями и кольцами. Все приведенные алгоритмы имеют оценки временной сложности, которые приводились в первой части этой работы.
The purpose of the article. To present methods for solving the problem of a mathematical safe for its various variations, which are related both to the domain over which the problem is considered and to the structure of systems of linear equations over these domains. To consider the problem of a mathematical safe (in matrix and graph forms) in different variations over different finite domains and to demonstrate the work of methods for solving this problem and their efficiency (systems over finite simple fields, finite fields, ghost rings and finite associative-commutative rings). Results. Examples of solving the problem of a mathematical safe, the conditions for the existence of solutions in different areas, over which this problem is considered. The choice of the appropriate area over which the problem of the mathematical safe is considered, and the appropriate algorithm for solving it depends on the number of positions of the latches of the safe. All these algorithms are accompanied by estimates of their time complexity, which were considered in the first part of this paper.
|
| isbn |
MSC 12F05, 68W05 |
| issn |
2707-4501 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/179350 |
| citation_txt |
Задача про математичний сейф та її розв'язання (частина 2) / С.Л. Кривий, Г.І. Гогерчак // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 1. — С. 16-28. — Бібліогр.: 3 назв. — укр. |
| work_keys_str_mv |
AT kriviisl zadačapromatematičniiseiftaíírozvâzannâčastina2 AT gogerčakgí zadačapromatematičniiseiftaíírozvâzannâčastina2 AT kriviisl zadačaomatematičeskomseifeieerešeniečastʹ2 AT gogerčakgí zadačaomatematičeskomseifeieerešeniečastʹ2 AT kriviisl themathematicalsafeproblemanditssolutionpart2 AT gogerčakgí themathematicalsafeproblemanditssolutionpart2 |
| first_indexed |
2025-11-25T20:32:26Z |
| last_indexed |
2025-11-25T20:32:26Z |
| _version_ |
1850524510103535616 |
| fulltext |
МЕТОДИ ОПТИМІЗАЦІЇ ТА ЕКСТРЕМАЛЬНІ ЗАДАЧІ
16 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1
КІБЕРНЕТИКА
та КОМП'ЮТЕРНІ
ТЕХНОЛОГІЇ
Дана стаття – продовження частини 1 [1].
В цій частині роботи розглядаються засто-
сування методів та алгоритмів, описаних в
ч. 1 до розв’язання задачі про математичний
сейф в різних варіаціях. Досліджені матрич-
ний та графовий варіанти математичного
сейфа, розглянуті умови існування розв'язку,
алгоритми розв'язання задачі для різних
представлень та їх ефективність.
Ключові слова: математичний сейф, скін-
ченні комутативні кільця, скінченні поля.
С.Л. Кривий, Г.І. Гогерчак, 2021
УДК 51.681.3 DOI:10.34229/2707-451X.21.1.2
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ
ТА ЇЇ РОЗВ'ЯЗАННЯ
1
(ЧАСТИНА 2)
Вступ. Нагадаємо, що математичним сейфом
називається система 1 2= ( , , , )nZ z z z взаємнопо-
в'язаних між собою засувів так, що коли виконується
поворот ключа в одному із засувів, то такий же
поворот виконується і у всіх засувах, які пов'язані з
даним. При повороті ключа в даному засуві він і всі
засуви, пов’язані з цим засувом, збільшують свою
позицію на одиницю за мождулем k. Кожний із
засувів може знаходитися в одній із декількох
позицій. Всіх можливих позицій скінченне число:
0,1, , 1k . Засув відкритий, якщо він знаходиться в
позиції 0. В довільній іншій позиції засув вважається
закритим. Сейф може задаватися двома способами за
допомогою матриці (матричний сейф) і за допомогою
графа (графовий сейф). Початкові позиції засувів
сейфа Z при першому способі задання визначаються
матрицею =|| ||ijB b , де пов’язаними з засувом zij
є засуви, які знаходяться в i-му рядку і j-му стовпчику,
а при другому – позиціями засувів у вершинах,
де пов’язаними з засувом у вершиі u є засуви, розмі-
щені у суміжних вершинах з вершиною u.
Необхідно розв'язати таку задачу. Виходячи з по-
чаткових позицій сейфа, знайти таку послідовність
засувів і число поворотів ключа в них, щоб сейф
перейшов у положення відкритого, тобто коли всі
засуви знаходяться в позиції 0. Як було показано
в першій частині даної роботи [1], розв’язання задачі
про матемематичний сейф зводиться до розв’язання
системи лінійних рівнянь вигляду:
0(mod )Ax b k . (1)
1. Pозв'язання задачі про математичний сейф
Розглянемо задачу про математичний сейф та мож-
ливі її варіації над скінченними кільцями і полями [2].
Вибір області, над якою розглядається сейф, залежить
від числа позицій засувів.
Випадок 1. Число позицій засувів p просте.
Оскільки число позицій є простим числом, то задача
про матричний сейф розглядається над полем лишків
1 За фінансової підтримки НАН України (проект 0118U005227)
https://doi.org/10.34229/2707-451X.21.1.2
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ …
ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 17
за модулем .p Побудова цього розв’язку зводиться до розв’язання системи лінійних рівнянь
вигляду (1) і це розв’язання виконується TSS -методом. Нехай маємо сейф в полі 3F з матрицею
2 0 2 2
= .
1 2 2 1
B
Тоді = (2,0,2,2,1,2,2,1)b і система рівнянь 0 ( 3)Ax b mod має вигляд:
1 1 1 1 1 0 0 0 2
1 1 1 1 0 1 0 0 0
1 1 1 1 0 0 1 0 2
1 1 1 1 0 0 0 1 2
= 0 ( 3).
1 0 0 0 1 1 1 1 1
0 1 0 0 1 1 1 1 2
0 0 1 0 1 1 1 1 2
0 0 0 1 1 1 1 1 1
A x b mod
Застосовуючи TSS -алгоритм для розв’язання цієї системи, знаходимо розв’язок CЛНДР
= (0,2,2,0,0,2,0,0)x , тобто 11 12 13 14 21 22= 0, = 2, = 2, = 0, = 0, = 2,x x x x x x 23 24= 0, = 0x x .
Цьому розв’язку відповідають такі перетворення матриці B :
12
2 0 2 2 1 2 1 1
( = 2)
1 2 2 1 1 1 2 1
x
13 22
0 1 0 0 0 0 0 0
( = 2) ( = 2)
1 1 1 1 0 0 0 0
x x
.
Отже, знайдена послідовність поворотів ключа відкриває сейф. Ця сама задача за модулем 13
має розв’язок 11 12 13 14 21 22 23 24= 8, = 7, = 7, = 8, = 7, = 9, = 7, = 7,x x x x x x x x який відкриває сейф
(в чому можна переконатися безпосередньою перевіркою).
Зауважимо, що в тому випадку коли число 1m n , де m n розмірність матриці ,B кратне
модулю, a сума кoефіцієнтів матриці B не кратна модулю, то задача про сейф не має розв'язку.
Це випливає з теореми 3 (див. част. 1). Дійсно, якщо розв'язувати задачу про сейф з матрицею B
за модулем 5
1 1 1 1 1 0 0 0 2
1 1 1 1 0 1 0 0 0
1 1 1 1 0 0 1 0 2
1 1 1 1 0 0 0 1 2
= 0 ( 5),
1 0 0 0 1 1 1 1 1
0 1 0 0 1 1 1 1 2
0 0 1 0 1 1 1 1 2
0 0 0 1 1 1 1 1 1
A x b mod
то задача не має розв'язку, оскільки 1= 2 4 1= 5 0 ( 5)m n mod (це означає, що останній
рядок матриці A лінійно залежить від попередніх рядків), а сума елементів матриці B дорівнює
12 і не кратна 5.
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
18 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1
Випадок 2. Число позицій засувів k складене. Тоді область над якою розглядається
математичний сейф є кільце лишків kZ . Нехай маємо сейф в кільці 12Z з матрицею
4 5 2
= .
1 3 1
B
Тоді система (1) набуває вигляду:
11 12 13 21
11 12 13 22
11 12 13 23
11 21 22 23
12 21 22 23
13 21 22 23
4 = 0
5 = 0
2 = 0
( 12).
1 = 0
3 = 0
1 = 0
x x x x
x x x x
x x x x
mod
x x x x
x x x x
x x x x
Застосовуючи TSS -алгоритм для розв’язання цієї системи в кільці 12Z , отримуємо такі
розв'язки:
1 2= (0,6,0,6,9,0,9), = (4,8,4,4,0,0,4)s s .
З цих розв’язків потрібно отримати розв’язок, у якого остання координата дорівнює 1, що
відповідає початковим позиціям засувів. Для цього розв'язуємо порівняння 9 4 1( 12)x y mod .
Очевидним розв’язком цього порівняння є =1, = 2x y або з урахуванням доповнення
=1, =10x y . Лінійна комбінація 1 210s s дає розв'язок задачі про математичний сейф
= (4,2,4,10,9,0)z . Дійсно,
11 12 13
4 5 2 8 9 6 10 11 8 2 3 0
( = 4) ( = 2) ( = 4)
1 3 1 5 3 1 5 5 1 5 5 5
x x x
21 22
0 3 0 0 0 0
( =10) ( = 9) .
3 3 3 0 0 0
x x
Випадок 3. Число позицій засувів k=
rp , де p – просте число. В цьому випадку областю
стає поле rp
F . Для цього поля математична постановка залишається незмінною, але всі операції
здійснюються в полі rp
F . Розглянемо задачу про математичний сейф в полі 22
F (таблиці 1 і 2
операцій якого наведені нижче), оскільки всі викладки для більших значень p і r аналогічні [3].
ТАБЛИЦЯ 1 ТАБЛИЦЯ 2
+ 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
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ …
ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 19
Нехай матриця сейфа в полі 22
F є така:
1 2 3
= .
0 1 1
B
Тоді = (1,2,3,0,1,1)b і система 0Ax b в полі 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 b
Застосуємо TSS -алгоритм для розв'язання цієї системи в полі 22
F . Оскільки доповнення 1
дорівнює 1 в полі 22
F , то дістаємо такі розв’язки першого рівняння:
(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).
Значення лівої частини другого рівняння, знайдені за таблицями 1 і 2, які були наведені вище
для поля 22
F , дорівнюють: 3,3,3,2,1,0. За цими значеннями комбінуванням першого розв'язку з
рештою, отримуємо розв'язки першого і другого рівняння системи:
(1,1,0,0,0,0,0), (1,0,1,0,0,0,0), (1,0,0,2,0,0,3), (1,0,0,0,3,0,1), (0,0,0,0,0,1,0).
Значення лівої частини третього рівняння, знайдені за цими ж таблицями, дорівнюють:
0,0,3,2,1. За цими значеннями комбінуванням останнього розв’язку з третім і четвертим, отримуємо
розв’язки перших трьох рівнянь системи:
(1,1,0,0,0,0,0), (1,0,1,0,0,0,0), (1,0,0,2,0,3,3), (1,0,0,0,3,2,1).
Значення лівої частини четвертого рівняння дорівнюють: 1,1,0,0. За цими значеннями
комбінуванням першого розв'язку з другим, отримуємо розв’язки перших чотирьох рівнянь
системи:
(0,1,1,0,0,0,0), (1,0,0,2,0,3,3), (1,0,0,0,3,2,1).
Значення лівої частини п'ятого рівняння дорівнюють: 1,2,0. За цими значеннями дістаємо
розв'язки перших п'яти рівнянь системи:
(1,2,2,2,0,3,3), (1,0,0,0,3,2,1).
Значення лівої частини шостого рівняння дорівнюють: 0,0. Це означає, що обидва вектори
є розв'язками початкової системи. Другий розв'язок справді є розв’язком неоднорідної системи,
а перший стає її розв’язком, якщо його помножити на 2 згідно таблиць 1 і 2 в полі 22
F .
В результаті знаходимо вектор (2,3,3,3,0,1) – другий розв’язок цієї системи.
Безпосередньою перевіркою переконуємося, що отримані розв'язки дійсно відкривають сейф.
Для першого розв’язку маємо:
11 22 23
1 2 3 0 3 2 0 0 2 0 0 0
( =1) ( = 3) ( = 2) .
0 1 1 1 1 1 2 2 2 0 0 0
x x x
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
20 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1
Для другого розв’язку маємо:
11 12 13
1 2 3 3 0 1 0 3 2 3 0 1
( = 2) ( = 3) ( = 3)
0 1 1 2 1 1 2 2 1 2 2 2
x x x
21 23
0 0 1 0 0 0
( = 3) ( =1) .
1 1 1 0 0 0
x x
Для існування розв’язку задачі про сейф в цьому полі, як і в попередньому випадку, повинна
виконуватися умова: якщо 1 0 ( ),m n mod p то
1
=1
( ),
mn
i mn
i
b b mod p
де сума обчислюється за
таблицями поля rp
F . Дійсно, якщо 1 0 ( ),m n mod p то останнє рівняння цієї системи є сумою
(лінійною комбінацією) попередніх рівнянь цієї системи, а звідси і випливає справедливість умови.
Наприклад, приведена вище задача про сейф, у якої останнє значення вільного члена дорівнює
2 (а не 1), не має розв'язку в полі 22
F оскільки 1=1 1 1 1 0 ( 2)m n mod і
5
=1
1i
i
b , a останнє
рівняння, яке є сумою попередніх п’яти рівнянь, дорівнює 2. Отримана суперечність говорить про
несумісність системи (1). Справді, комбінація розв’язків
1 2= (1,2,2,2,0,3,3), = (1,0,0,0,3,2,1)s s
для значень 2, 3 (результат підстановки в останнє рівняння) дає розв’язок 1 22 = (3,3,3,3,3,3,0)s s ,
який не є розв’язком задачі.
2. Варіації задачі про математичний сейф
Випадок 1. Розглянемо матричний сейф в полі лишків kF в такій постановці: сейф вважається
відкритим не при нульових станах всіх засувів, а при певній комбінації цих засувів. Тоді система
(1) набуває вигляду
( ),Ax b c mod k (2)
де c позиції засувів, при яких сейф буде відкритим, а b – вектор початкових позицій засувів.
Очевидно, що дана задача зводиться до розглянутих вище випадків, оскільки система (2)
редукується до СЛОДР
0 ( ),Ax d mod k (3)
де =d b c .
Складність обчислення перебірним методом вектора d , не знаючи потрібної комбінації
позицій засувів, пропорціональна величині mnk , де m n – розмірність матриці A . При невеликих
значеннях , ,k m n обчислення вектора d не складає труднощів. Але коли модуль k досить велике
число, то навіть при невеликих m і n складність обчислення стає великою. Наприклад, якщо
=101, = 4,k m = 5n , то складність перебірного методу 20 41 123=101 10 2P . Це вже досить
велика кількість комбінацій, яку необхідно в найгіршому випадку розглянути.
Нехай дана матриця сейфа
14 0 0
= 0 0 0 ,
0 0 11
B
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ …
ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 21
а задача розв’язується в полі за модулем 17 з такою комбінацією, яка відкриває сейф,
1 2 3
= 4 5 6 .
7 8 9
c
Тоді СЛНДР ( 17)Ax b c mod набуває вигляду:
1 1 1 1 0 0 1 0 0 14 = 1
1 1 1 0 1 0 0 1 0 0 = 2
1 1 1 0 0 1 0 0 1 0 = 3
1 0 0 1 1 1 1 0 0 0 = 4
( 17).0 1 0 1 1 1 0 1 0 0 = 5
0 0 1 1 1 1 0 0 1 0 = 6
1 0 0 1 0 0 1 1 1 0 = 7
0 1 0 1 1 1 1 0 1 0 = 8
0 0 1 0 0 1 1 1 1 11 = 9
mod
Після перетворення цієї СЛНДР до СЛОДР, отримуємо
1 1 1 1 0 0 1 0 0 13 = 0
1 1 1 0 1 0 0 1 0 15 = 0
1 1 1 0 0 1 0 0 1 14 = 0
1 0 0 1 1 1 1 0 0 13 = 0
( 17).0 1 0 1 1 1 0 1 0 12 = 0
0 0 1 1 1 1 0 0 1 11 = 0
1 0 0 1 0 0 1 1 1 10 = 0
0 1 0 1 1 1 1 0 1 9 = 0
0 0 1 0 0 1 1 1 1 2 = 0
mod
Розв’язком цієї системи є вектор = (3,13,5,1,13,,5,15,10,6,5)y . Для побудови розв’язку задачі
про сейф необхідно розв'язати порівняння 5 1( 17)z mod . Розв’язок цього порівняння = 7z .
Помноживши вектор y на = 7,z дістаємо розв'язок задачі про сейф: = (4,6,1,7,6,1,3,2,8)x .
Дійсно,
11 12 13
14 0 0 1 4 4 7 10 10 8 11 11
0 0 0 ( = 4) 4 0 0 ( = 6) 4 6 0 ( =1) 4 6 1
0 0 11 4 0 11 4 6 11 4 6 12
x x x
21
15 11 11
( = 7) 11 13 8
11 6 12
x
22 23
15 0 11 15 0 12
( = 6) 0 2 14 ( =1) 1 3 15
11 12 12 11 12 13
x x
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
22 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1
31 32 33
1 0 12 1 2 12 1 2 3
( = 3) 4 3 15 ( = 2) 4 5 15 ( = 8) 4 5 6 .
14 15 16 16 0 1 7 8 9
x x x
Випадок 2. Розглянемо задачу про сейф в полі rp
F , який вважається відкритим при певній
комбінації засувів.
Система (2) тепер розв'язується в полі rp
F . Складність обчислення вектора ,d не знаючи
потрібної комбінації позицій засувів, в найгіршому випадку пропорціональна величині
( ) =r mn rmnp p , що вже при невеликих , , ,p m n r складає великі труднощі обчислювального
характеру. Наприклад, при = 3, = 2, = 4, = 5p m n r отримуємо 403 варіантів для аналізу (таблиці
операцій 3 і 4 поля 23
F відносно незвідного полінома
2 2x x над F2 наведені нижче,
де x позначений числом 3, 1x – числом 4, 2x – числом 5, 2x – числом 6, 2 1x – числом 7,
2 2x – числом 8).
ТАБЛИЦЯ 3 ТАБЛИЦЯ 4
+ 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
Цю складність можна ще збільшити, якщо таблиці 3 i 4 поля rp
F задавати з точністю до
ізоморфізму. Такий варіант пошуку розв’язку за своєю складністю є гіршим за повний перебір
розв’язків. В цьому випадку необхідно знайти ізоморфізм між таблицями 3 і 4 та таблицями 5 і 6,
приведеними нижче, для поля 23
F . Наприклад, перенумеруємо елементи цього поля таким чином:
x позначимо числом 8, 1x – числом 7, 2x – числом 6, 2x – числом 5, 2 1x – числом 4,
2 2x – числом 3. Тоді таблиці 3 і 4 поля 23
F набувають вигляду:
ТАБЛИЦЯ 5 ТАБЛИЦЯ 6
+ 0 1 2 8 7 6 5 4 3 * 0 1 2 8 7 6 5 4 3
0 0 1 2 8 7 6 5 4 3 0 0 0 0 0 0 0 0 0 0
1 1 2 0 7 6 8 4 3 5 1 0 1 2 8 7 6 5 4 3
2 2 0 1 6 8 7 3 5 4 2 0 2 1 5 3 4 8 6 7
8 8 7 6 5 4 3 0 1 2 8 0 8 5 4 1 7 6 3 2
7 7 6 8 4 3 5 1 2 0 7 0 7 3 1 6 5 2 8 4
6 6 8 7 3 5 4 2 0 1 6 0 6 4 7 5 2 3 1 8
5 5 4 3 0 1 2 8 7 6 5 0 5 8 6 2 3 4 7 1
4 4 3 5 1 2 0 7 6 8 4 0 4 6 3 8 1 7 2 5
3 3 5 4 2 0 1 6 8 7 3 0 3 7 2 4 8 1 5 6
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ …
ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 23
Навіть при = 3p таких ізоморфізмів буде
2 6(3 3)!= 6!= 720 3 .
Якщо в задачі, крім всього іншого, невідомий також і модуль поля, то задача ще більше
ускладнюється. В цьому випадку необхідно знайти модуль поля і саме поле, що потребує
додаткових часових і обчислювальних затрат.
Випадок 3. В цьому випадку розв'язки задачі про сейф шукаються в кільці лишків за модулем
складeного числа m при заданій комбінації засувів, яка відкриває сейф.
Нехай задача про сейф розв'язується в кільці лишків за модулем 15 з матрицею
14 2 3
= 4 5 6
7 8 11
B
і з такою комбінацією, яка відкриває сейф,
0 2 3
= 4 5 6 .
7 8 0
c
Тоді СЛНДР ( 15)Ax b c mod набуває вигляду:
1 1 1 1 0 0 1 0 0 14 = 0
1 1 1 0 1 0 0 1 0 2 = 2
1 1 1 0 0 1 0 0 1 3 = 3
1 0 0 1 1 1 1 0 0 4 = 4
( 15).0 1 0 1 1 1 0 1 0 5 = 5
0 0 1 1 1 1 0 0 1 6 = 6
1 0 0 1 0 0 1 1 1 7 = 7
0 1 0 1 1 1 1 0 1 8 = 8
0 0 1 0 0 1 1 1 1 11 = 0
mod
Після перетворення цієї СЛНДР до СЛОДР, отримуємо
1 1 1 1 0 0 1 0 0 14 = 0
1 1 1 0 1 0 0 1 0 0 = 0
1 1 1 0 0 1 0 0 1 0 = 0
1 0 0 1 1 1 1 0 0 0 = 0
( 15).0 1 0 1 1 1 0 1 0 0 = 0
0 0 1 1 1 1 0 0 1 0 = 0
1 0 0 1 0 0 1 1 1 0 = 0
0 1 0 1 1 1 1 0 1 0 = 0
0 0 1 0 0 1 1 1 1 11 = 0
mod
Розв'язком цієї системи є вектор = (5,13,0,13,5,7,0,7,5)x , який відкриває сейф. Дійсно,
11 12
14 2 3 4 7 8 2 5 6
4 5 6 ( = 5) 9 5 6 ( =13) 9 3 6
7 8 11 12 8 11 12 6 11
x x
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
24 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1
21 22 23
0 5 6 0 10 6 0 10 13
( =13) 7 1 4 ( = 5) 12 6 9 ( = 7) 4 13 1
10 6 11 10 11 11 10 11 3
x x x
32 33
0 2 13 0 2 3
( = 7) 4 5 1 ( = 5) 4 5 6 .
2 3 10 7 8 0
x x
Випадок 4. Розв’язки задачі про сейф шукаються в кільці лишків за модулем складеного числа
m при заданій комбінації засувів, яка відкриває сейф, і модифікованої матриці системи (2).
Нехай задача про сейф розв'язується в кільці за модулем 27 з матрицею
1 2 0
= 0 0 0
0 0 0
B
і з такою комбінацією, яка відкриває сейф,
1 2 3
= 4 5 6 .
7 8 9
c
Модифікована матриця A системи має вигляд:
1 1 1 3 0 0 2 0 0
1 1 1 0 3 0 0 2 0
1 1 1 0 0 3 0 0 2
1 0 0 3 3 3 2 0 0
.0 1 0 3 3 3 0 2 0
0 0 1 3 3 3 0 0 2
1 0 0 3 0 0 2 2 2
0 1 0 0 3 0 2 2 2
0 0 1 0 0 3 2 2 2
Тоді СЛНДР ( 27)Ax b c mod набуває вигляду:
1 1 1 3 0 0 2 0 0 1 = 1
1 1 1 0 3 0 0 2 0 2 = 2
1 1 1 0 0 3 0 0 2 0 = 3
1 0 0 3 3 3 2 0 0 0 = 4
= ( 27).0 1 0 3 3 3 0 2 0 0 = 5
0 0 1 3 3 3 0 0 2 0 = 6
1 0 0 3 0 0 2 2 2 0 = 7
0 1 0 0 3 0 2 2 2 0 = 8
0 0 1 0 0 3 2 2 2 0 = 9
Ax b c mod
Розв'язком цієї системи є вектор = (4,5,18,20,20,7,24,24,x 24,18) , який не відкриває сейф.
Для того, щоб цей розв’язок відкривав сейф, необхідно його перетворити таким чином:
перші три координати, які відповідають коефіцієнтам 1, залишаються незмінними;
другі три координати, які відповідають коефіцієнтам 3, множаться на 3 за модулем 27;
треті три координати, які відповідають коефіцієнтам 2, множаться на 2 за модулем 27.
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ …
ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 25
В результаті дістаємо розв’язок = (4,5,18,6,6,21,21,21,9)a , який відкриває сейф. Дійсно,
11 12 13
1 2 0 5 6 4 10 11 9 1 2 0
0 0 0 ( = 4) 4 0 0 ( = 5) 4 5 0 ( =18) 4 5 18
0 0 0 4 0 0 4 5 0 4 5 18
x x x
21 22 23
7 8 21
7 2 0 7 8 0
10 11 24
( = 6) 10 11 24 ( = 6) 16 17 3 ( = 21)
10 11 12
10 5 18 10 11 18
x x x
31 32 33
1 8 21 1 2 21 1 2 3
( = 21) 4 11 24 ( = 21) 4 5 24 ( = 9) 4 5 6 .
4 5 6 25 26 0 7 8 9
x x x
Нехай задача про сейф розв'язується, як і раніше, в кільці за модулем 27 з матрицею
6 6 0
= 0 0 0
0 0 0
B
і з такою комбінацією, яка відкриває сейф
0 0 6
= 0 3 0 .
0 3 0
c
Крім того, матриця A системи має вигляд:
1 3 2 1 0 0 1 0 0
1 3 2 0 3 0 0 3 0
1 3 2 0 0 2 0 0 2
1 0 0 1 3 2 1 0 0
.0 3 0 1 3 2 0 3 0
0 0 2 1 3 2 0 0 2
1 0 0 1 0 0 1 3 2
0 3 0 0 3 0 1 3 2
0 0 2 0 0 2 1 3 2
Тоді СЛНДР ( 27)Ax b c mod набуває вигляду:
1 3 2 1 0 0 1 0 0 6 = 0
1 3 2 0 3 0 0 3 0 6 = 0
1 3 2 0 0 2 0 0 2 0 = 6
1 0 0 1 3 2 1 0 0 0 = 0
= ( 27).0 3 0 1 3 2 0 3 0 0 = 3
0 0 2 1 3 2 0 0 2 0 = 0
1 0 0 1 0 0 1 3 2 0 = 0
0 3 0 0 3 0 1 3 2 0 = 3
0 0 2 0 0 2 1 3 2 0 = 0
Ax B c mod
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
26 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1
Розв’язком цієї системи є вектор = (0,19,24,12,13,9,12,13,9)x , який не відкриває сейф (в чому
можно переконатися). Для того, щоб цей розв’язок відкривав сейф, необхідно його редукувати
таким чином:
перша, четверта і сьома координати, які відповідають коефіцієнту 1, залишаються
незмінними;
друга, п’ятая і восьма координати, які відповідають коефіцієнту 3, множаться на 3
за модулем 27;
третя, шоста і дев’ята координати, які відповідають коефіцієнту 2, множаються на 2
за модулем 27.
В результаті дістаємо розв'язок = (0,3,21,12,12,18,12,12,18),a який відкриває сейф. Дійсно,
12 13 21
6 6 0 9 9 3 3 3 24 15 3 24
0 0 0 ( = 3) 0 3 0 ( = 21) 0 3 21 ( =12) 12 15 6
0 0 0 0 3 0 0 3 21 12 3 21
x x x
22 23 31
15 15 24 15 15 15 0 15 15
( =12) 24 0 18 ( =18) 15 18 9 ( =12) 0 18 9
12 15 21 12 15 12 24 0 24
x x x
32 33
0 0 15 0 0 6
( =12) 0 3 9 ( =18) 0 3 0 .
9 12 9 0 3 0
x x
Система (2) буде несумісною, якщо хоча б по одному з модулів розкладу числа k вона
несумісна, тобто не має розв'язків. Оцінки складності збільшуються, оскільки необхідно знайти
матрицю A .
Якщо підсумувати сказане, то найбільш складною задачею про сейф при невідомому модулі
і невідомій комбінації позицій засувів, яка відкриває сейф, є задача в полі rp
F або в кільці kZ .
3. Задання математичного сейфа за допомогою графа
Нагадаємо формулювання задачі про математичний сейф за допомогою графа. У вершинах
графа = ( , )G V E знаходяться засуви, які можуть знаходитися в одній з позицій із множини
{0,1, , 1}k . Якщо у вершині u засув знаходиться в позиції ,i то поворот ключа в цій вершині
переводить її засув в позицію ( 1) ( )i mod k а також всі засуви вершин, які суміжні з вершиною .u
Початкові позиції засувів у вершинах задаються вектором 1 2 | |= ( , , , )Vb b b b .
Розв’язання задачі виконується тими самими алгоритмами, що і при розв’язанні задачі на
матрицях. Але при такому заданні структура матриці СЛНДР ( )Ax b c mod k може бути,
взагалі кажучи, довільною. Нехай дано граф, показаний на рисунку, і = (1,2,1,1,3)b .
РИСУНОК
ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ ТА ЇЇ РОЗВ'ЯЗАННЯ …
ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 27
Будується СЛОДР 0 ( )Ax b mod k для задачі про МС цього графа ( = 5k ):
1 2 3 4 5
1 1 1 0 0 0 1
2 1 1 1 0 0 2
= 0 ( 5).
3 1 1 1 1 0 1
4 0 0 1 1 1 1
5 1 0 0 1 1 3
b
A mod
Розв'язком даної СЛОДР є вектор = (0,1,2,1,1)x
1 2 1 1 3,
2 =1b
2 3 2 1 3,
3 = 2b
4 0 4 3 3,
4 =1b
0 0 0 4 4,
5 =1b
0 0 0 0 0.
Таким чином сейф відкрито.
Висновки. Розглянуті варіації задачі про математичний сейф та способи її розв’язання.
В залежності від області, над якою розглядається задача про математичний сейф, застосовуються
різні варіації TSS-алгоритму для побудови базису множини всіх розв’язків системи Bx b c
та алгоритми побудови таблиць операцій відповідних областей. Області, над якими розв’язується
задача про математичний сейф є скінченні поля, примарні кільця та загального вигляду асоціатив-
но-комутативні кільця з одиницею. Алгоритми побудови таблиць операцій та алгоритми побудови
базисних розв’язків мають поліноміальні оцінки складності (в кільцях за умови відомого розкладу
на прості множники модуля).
Список літератури
1. Кривий С.Л., Гогерчак Г.І. Задача про математичний сейф та її розв’язання (частина 1). Cybernetics and
Computer Technologies. 2020. 4. С. 24–35. https://doi.org/10.34229/2707-451X.20.4.2
2. Крывый С.Л. Численные методы решения задачи о математическом сейфе. Кибернетика и системный анализ.
2019. 55 (5). С.18–34.
3. Кострикин А.И. Введение в алгебру. М.: Наука, 1977. 495 с.
Одержано 06.12.2020
Кривий Сергій Лук’янович,
доктор фізико-математичних наук, професор, професор кафедри інтелектуальних програмних систем
Київського національного університету імені Тараса Шевченка, Київ,
https://orcid.org/0000-0003-4231-0691
sl.krivoi@gmail.com
Гогерчак Григорій Іванович,
аспірант факультету комп’ютерних наук та кібернетики
Київського національного університету імені Тараса Шевченка, Київ.
https://orcid.org/0000-0002-6898-2536
gogerchak.g@gmail.com
https://doi.org/10.34229/2707-451X.20.4.2
https://orcid.org/0000-0003-4231-0691
mailto:sl.krivoi@gmail.com
https://orcid.org/0000-0002-6898-2536
mailto:gogerchak.g@gmail.com
С.Л. КРИВИЙ, Г.І. ГОГЕРЧАК
28 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1
MSC 12F05, 68W05
Sergii Kryvyi 1 *, Hryhorii Hoherchak 1
The Mathematical Safe Problem and Its Solution (Part 2)
1 Taras Shevchenko National University of Kyiv, Ukraine
* Correspondence: sl.krivoi@gmail.com
Introduction. The problem of mathematical safe arises in the theory of computer games and cryptograph-
ic applications. The article considers numerous variations of the mathematical safe problem and examples of its
solution using systems of linear Diophantine equations in finite rings and fields.
The purpose of the article. To present methods for solving the problem of a mathematical safe for its
various variations, which are related both to the domain over which the problem is considered and to the struc-
ture of systems of linear equations over these domains. To consider the problem of a mathematical safe (in ma-
trix and graph forms) in different variations over different finite domains and to demonstrate the work of meth-
ods for solving this problem and their efficiency (systems over finite simple fields, finite fields, ghost rings and
finite associative-commutative rings).
Results. Examples of solving the problem of a mathematical safe, the conditions for the existence of so-
lutions in different areas, over which this problem is considered. The choice of the appropriate area over which
the problem of the mathematical safe is considered, and the appropriate algorithm for solving it depends on the
number of positions of the latches of the safe. All these algorithms are accompanied by estimates of their time
complexity, which were considered in the first part of this paper.
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 a large number of vari-
ations of its formulation (over finite prime field, finite field, primary associative-commutative ring and finite
associative-commutative ring with unit).
Keywords: mathematical safe, finite rings, finite fields, method, algorithm.
mailto:sl.krivoi@gmail.com
|