Алгоритм синтезу незвідних поліномів лінійної складності

Автор(и)

  • Анатолий Яковлевич Белецкий Національний авіаційний університет
  • Арсен Віталійович Ковальчук Національний авіаційний університет
  • Костянтин Андрійович Новиков Національний авіаційний університет
  • Дмитро Анатолійович Полторацький Національний авіаційний університет

DOI:

https://doi.org/10.18372/2410-7840.22.14868

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

незвідні та складові поліноми, сингулярні поліноми, реперні сітки, порівнянність за модулем

Анотація

Незвідні поліноми знаходять широке застосування в різноманітних областях науки і техніки. Незважаючи на велику затребуваність синтез незвідних поліномів до теперішнього часу є досить складне завдання і, як зазначено В. Жельніковим, «знаходження незвідних поліномів досі покрито мороком. Криптографічні служби високорозвинених країн працювали і працюють над пошуком многочленів якомога більш високого ступеня, але свої результати вони майже не висвітлюють у відкритій пресі». Відомі алгоритми синтезу незвідних поліномів мають суттєвий недолік, який полягає в тому, що їх обчислювальна складність є, як правило, квадратичною. Отже, побудова поліномів великих ступенів може бути реалізовано лише на обчислювальних комплексах високої продуктивності. Запропонований алгоритм спирається на так звані реперні сітки (сходи), число сходинок в яких збігається зі ступенем синтезованих поліномів. На кожній сходинці здійснюються найпростіші рекурентні однотипні модулярні обчислення, по завершенні яких поліном, що тестується, однозначно класифікується або як незвідний, або як складовий. Розроблений алгоритм відноситься до підкласу алгоритмів лінійної складності. Суть рекурентних операцій на множені двійкових поліномів зводиться до обчислення залишків за модулем тестуємого на незвідність поліному, представленого в векторній формі (набором бінарних коефіцієнтів поліному), від квадрата залишку, утвореного на попередній сходинці перетворення і доповненого справа нулем. Якщо верхня (порогова) ступінь синтезованих незвідних поліномів не велика, наприклад, не перевищує двох десятків, то формування множені поліномів, що тестуються, може здійснюватися за методом повного перебору. У тому випадку, коли ступінь поліному перевищує порогове значення, то генерацію поліномів зручніше реалізовувати статистичним моделюванням. В роботі коротко позначений алгоритм синтезу незвідних поліномів над простим полем Галуа характеристики

Біографії авторів

Анатолий Яковлевич Белецкий, Національний авіаційний університет

доктор технічних наук, професор, заслужений діяч науки і техніки України, лауреат Державної премії України в галузі науки і техніки, професор кафедри електроніки, робототехніки та технологій мониторингу и Інтернету речей Національного авіаційного університету

Арсен Віталійович Ковальчук, Національний авіаційний університет

студент кафедри електроніки, робототехніки та технологій мониторингу и Інтернету речей Національного авіаційного університету.

Костянтин Андрійович Новиков, Національний авіаційний університет

студент кафедри електроніки, робототехніки та технологій мониторингу и Інтернету речей Національного авіаційного університету.

Дмитро Анатолійович Полторацький, Національний авіаційний університет

студент кафедри електроніки, робототехніки та технологій мониторингу и Інтернету речей Національного авіаційного університету

Посилання

В. Прасолов, Многочлены, М.: МЦНМО, 2001, 336 с.

R. Lidl, H. Niederreiter, Finite Fields, Cambridge Uni-versity Press, 1996.

О. Василенко, Теоретико-числовые алгоритмы в крип-тографии, М.: МЦНМО, 2003, 328 с.

В. Фомичёв, Дискретная математика и криптография, M.: Диалог-MIFI, 2013, 397 с.

С. Титов, А. Торгашов, "Генерация неприводи-мых многочленов, связанных степенной зависи-мостью корней", Управление, вычислительная техни-ка и информатика, Томск: Труды Томского Гос. ун-та, № 2 (22), С. 310-317, 2010.

Б. Шнайер, Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке С+, Триумф, 2002, 816 с.

R. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley Publishing Company Reaging, 1984, 500 p.

W. Peterson, E. Weldon, Error Correcting Codes, MIT press, Cambridge, MA, 1972.

Ф. Мак- Вильямс, Н. Слоэн, Теория кодов, исправля-ющих ошибки, М: Связь, 1979, 744 с.

В. Жельников, Криптография от папируса до компью-тера, М: ABF, 1996, 355 с.

М. Мазурков, В. Дмитренко, Е. Конопака, "Эф-фективный алгоритм нахождения первообразных неприводимых полиномов", Праці УНДІРТ, Одесса, № 1, С. 32-35, 2005.

E. Berlekamp, Algebraic Coding Theory, 1968.

А. Леухин, С. Бахтин, "Новый алгоритм синтеза всех неприводимых многочленов над заданным конечным полем". [Electronic resource]. Available at: http://bio.marstu.net/data/materials/conf/mmro13/ mmro13pdf/LEUKHIN_SI_2.pdf.

А. Трахтман, В. Трахтман, Основы теории дискрет-ных сигналов на конечных интервалах, М: Сов. радио, 1975, 208 с.

Wilfrid Keller. "Factors of Fermat numbers and large primes of the form k · 2n + 1", Math. of Comp., 41, pp. 661-673, 1983.

##submission.downloads##

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

2020-07-01

Номер

Том 22 № 2 (2020)

Розділ

Статті

Ліцензія

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.

  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.

  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).