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

Автор(и)

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

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

Як цитувати

Белецкий, А. Я., Ковальчук, А. В., Новиков, К. А., & Полторацький, Д. А. (2020). Алгоритм синтезу незвідних поліномів лінійної складності. Захист інформації, 22(2), 74–87. https://doi.org/10.18372/2410-7840.22.14868

Номер

Том 22 № 2 (2020)

Розділ

Статті

Ліцензія

Науковий журнал дотримується принципів відкритого доступу (Open Access) та забезпечує вільний, негайний і постійний доступ до всіх опублікованих матеріалів без фінансових, технічних або юридичних обмежень для читачів.

Усі статті публікуються у відкритому доступі відповідно до ліцензії Creative Commons Attribution 4.0 International (CC BY 4.0).

Авторські права

Автори, які публікують свої роботи в журналі:

  • зберігають за собою авторські права на свої публікації;

  • надають журналу право на перше опублікування статті;

  • погоджуються на поширення матеріалів за ліцензією CC BY 4.0;

  • мають право повторно використовувати, архівувати та поширювати свої роботи (у тому числі в інституційних та тематичних репозитаріях) за умови посилання на первинну публікацію в журналі.