ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО МАТЕМАТИЧНИЙ СЕЙФ

Автор(и)

  • Сергій Кривий Київський національний університет імені Тараса Шевченка

Ключові слова:

математичний сейф, скінченні кільця, скінченні поля, системи лінійних рівнянь

Анотація

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

Опубліковано

2021-09-15

Як цитувати

Кривий, С. (2021). ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО МАТЕМАТИЧНИЙ СЕЙФ. Вісник Університету «Україна» Серія Інформатика, обчислювальна техніка та кібернетика, 1(22). вилучено із https://visn-it.uu.edu.ua/index.php/visn-icct/article/view/23