Статті

Назва статті

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

Номер віснику

22

DOI:

10.36994/2707-4110-2019-1-22-23

Автори

Кривий С. Л., д.ф.-м.н,, проф., Київський націрнальний університет імені Тараса Шевченка,Київ, Україна. sl.krivoi@gmail.com

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

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

Анотація

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