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

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

Анотація


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

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


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

Посилання


В. Прасолов, Многочлены, М.: МЦНМО, 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.


Повний текст: PDF

Посилання

  • Поки немає зовнішніх посилань.


ISSN 2410-7840 (Online), ISSN 2221-5212 (Print)

Ліцензія Creative Commons
Цей твір ліцензовано за ліцензією Creative Commons Із зазначенням авторства - Некомерційна - Без похідних творів 3.0 Неадаптована

РИНЦ SSM WorldCat BASE Національна бібліотека ім. Вернадського Науково-технічна бібліотека НАУ Ulrich's Periodicals Directory

Ulrich's Periodicals Directory