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
Попередня | Повний текст | Наступна
Задача про математичний сейф та її розв'язання (частина 2)
С.Л. Кривий 1 *
,
Г.І. Гогерчак 1
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)
Попередня | Повний текст | Наступна