2020, випуск 4, c. 15-38
Одержано 06.11.2020; Виправлено 12.12.2020; Прийнято 17.12.2020
Надруковано 31.12.2020; Вперше Online 22.01.2021
https://doi.org/10.34229/2707-451X.20.4.2
Попередня | Повний текст | Наступна
Задача про математичний сейф та її розв'язання (частина 1)
С.Л. Кривий 1 *
,
Г.І. Гогерчак 1
1 Київський національний університет імені Тараса Шевченка, Україна
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Задача про математичний сейф виникає в теорії комп'ютерних ігор та криптографічних застосуваннях. У статті розглядається постановка задачі про математичний сейф та підхід до її розв’язання за допомогою систем лінійних рівнянь в скінченних кільцях та полях.
Мета роботи. Сформулювати математичну модель задачі про математичний сейф та її зведення до систем лінійних рівнянь у різних областях. Розглянути розв’язання відповідних систем у скінченних кільцях та полях. Розглянути принципи побудови розширень полів лишків та розв’язання систем у відповідних областях.
Результати. Подано постановку задачі про математичний сейф та розглянуто спосіб її зведення до систем лінійних рівнянь. Розглядаються методи та алгоритми розв’язання такого типу систем, де наводяться методи та алгоритми побудови базису множини розв'язків лінійних рівнянь та похідні від них методи та алгоритми побудови базису множини розв'язків систем лінійних рівнянь для полів лишків, примарних кілець, скінченних кілець та скінченних полів. Подано приклади для ілюстрації їх роботи. Розглянуто принципи побудови розширень полів лишків за модулем незвідного полінома, а також приклади таблиць операцій для них. Окремо розглядаються особливості розв’язання систем лінійних рівнянь в таких полях. Всі наведені алгоритми супроводжуються доведеннями та оцінками їх часової складності.
Висновки. Розглянуті методи та алгоритми розв’язання лінійних рівнянь та систем лінійних рівнянь в скінченних кільцях та полях дозволяють розв’язувати задачу про математичний сейф у великій кількості варіацій її постановки. В другій частині роботи будуть розглянуті застосування цих методів та алгоритмів до розв’язання задачі про математичний сейф в різних її варіаціях.
Ключові слова: математичний сейф, скінченні кільця, скінченні поля, метод, алгоритм, розв’язок.
Цитувати так: Кривий С.Л., Гогерчак Г.І. Задача про математичний сейф та її розв'язання (частина 1). Cybernetics and Computer Technologies. 2020. 4. С. 15–38. https://doi.org/10.34229/2707-451X.20.4.2
Список літератури
1. Донец Г.А. Решение задачи о сейфе на (0,1) – матрицах. Кибернетика и системный анализ. 2002. 38 (1). С. 98–105.
2. Калужнин Л.А. Введение в общую алгебру. М.: Наука, 1973. 447 с.
3. Крывый С.Л. Алгоритмы решения систем линейных диофантовых уравнений в кольцах вычетов. Кибернетика и системный анализ. 2016. 52 (5). С. 149–160.
4. Крывый С.Л. Алгоритмы решения систем линейных диофантовых уравнений в полях вычетов. Кибернетика и системный анализ. 2007. 43 (2). C. 15–23.
5. Кривий С.Л. Лінійні діофантові обмеження та їх застосування. Чернівці-Київ: Букрек, 2015. 224 с.
6. Коблиц Н. Курс теории чисел и криптографии. М.: Изд-во ТВП, 2001. 260 с.
7. Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии. М.: МЦНМО, 2002. 103 с.
8. Крывый С.Л., Гогерчак Г.И. Алгоритм решения систем линейных уравнений в поле Fpk. Проблемы управления и информатики. 2019. 5. С. 5–24.
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.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | Повний текст | Наступна