2021, випуск 1, c. 16-28

Одержано 06.12.2020; Виправлено 30.01.2021; Прийнято 25.03.2021

Надруковано 30.03.2021; Вперше Online 03.04.2021

https://doi.org/10.34229/2707-451X.21.1.2

Попередня  |  Повний текст  |  Наступна

 

УДК 51.681.3

Задача про математичний сейф та її розв'язання (частина 2)

С.Л. Кривий 1 * ORCID ID favicon Big,   Г.І. Гогерчак 1 ORCID ID favicon Big

1 Київський національний університет імені Тараса Шевченка, Україна

* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Вступ. Задачa про математичний сейф виникає в теорії комп'ютерних ігор та криптографічних застосуваннях. У статті розглядаються численні варіації  задачі про математичний сейф та приклади її розв’язання за допомогою систем лінійних рівнянь в скінченних кільцях та полях.

Мета статті. Представлення методів розв’язання задачі про математичний сейф (в матричному та графовому виглядах) для різноманітних її варіацій, які пов’язані як з областю, над якою розглядається задача, так і зі структурою  систем лінійних рівнянь над цими областями. Розглянуто розв’язання відповідних систем у скінченних простих полях, скінченних полях, примарних кільцях лишків та скінченних кільцях. Всі наведені алгоритми  мають оцінки часової складності.

Результати. Наведено приклади розв’язання задачі про математичний сейф, умови існування розв’язків в різних областях, над якими ця задача розглядається (скінченні прості поля, скінченні поля, примарні кільця, і асоціативно-комутативні кільця з одиницею). Вибір відповідної області над якою розглядається задача про математичний сейф, та відповідного алгоритму розв’язання залежить від кількості позицій засувів сейфа. Всі наведені алгоритми супроводжуються оцінками їх часової складності, які розглядалися в першій частині даної роботи..

Висновки. Розглянуті методи та алгоритми розв’язання лінійних рівнянь та систем лінійних рівнянь в скінченних кільцях та полях дозволяють розв’язувати задачу про математичний сейф у великій кількості варіацій її постановки. 

 

Ключові слова: математичний сейф, скінченні кільця, скінченні поля, метод, алгоритм.

 

Цитувати так: Кривий С.Л., Гогерчак Г.І. Задача про математичний сейф та її розв'язання (частина 2). Cybernetics and Computer Technologies. 2021. 1. С. 16–28. https://doi.org/10.34229/2707-451X.21.1.2

 

Список літератури

           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 с.

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  Повний текст  |  Наступна

 

 

 

© Вебсайт та оформлення. 2019-2021,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.