Record Details

Algorithm for the synthesis of irreducible polynomials of linear complexity

Наукові журнали Національного Авіаційного Університету

View Archive Info
 
 
Field Value
 
Title Algorithm for the synthesis of irreducible polynomials of linear complexity
Алгоритм синтеза неприводимых полиномов линейной сложности
Алгоритм синтезу незвідних поліномів лінійної складності
 
Creator Белецкий, Анатолий Яковлевич; Національний авіаційний університет
Ковальчук, Арсен Віталійович; Національний авіаційний університет
Новиков, Костянтин Андрійович; Національний авіаційний університет
Полторацький, Дмитро Анатолійович; Національний авіаційний університет
 
Subject Information security
irreducible and compound polynomials; singular polynomials; defining steps; modular comparability
UDC 512.6, 519.165, 519.725
Информационная безопасность
неприводимые и составные полиномы; сингулярные полиномы; реперные сетки; сравнимость по модулю
УДК 512.6, 519.165, 519.725
Інформаційна безпека
незвідні та складові поліноми; сингулярні поліноми; реперні сітки; порівнянність за модулем
УДК 512.6, 519.165, 519.725
 
Description Irreducible polynomials are widely used in various fields of science and technology. Despite the great demand, the synthesis of irreducible polynomials is still a rather complicated task and, as V. Zhelnikov noted, "finding irreducible polynomials is still obscured. Cryptographic services of highly developed countries have worked and are working on the search for polynomials of the highest possible degree, but they hardly cover their results in the open press". Known algorithms for the synthesis of irreducible polynomials have a significant disadvantage, which is that their computational complexity is, as a rule, square. Consequently, the building of large polynomials can be implemented only at computational complexes of rather high performance. The proposed algorithm based on the so-called reference meshes (stairs) the number of steps in which coincides with the degree of the polynomials synthesized. On each rung of the ladder, the simplest recurrent single-type modular calculations carried out. The end of the polynomial tested is unambiguously classified either as non-accepted or compound. The developed algorithm belongs to the subclass of linear complexity algorithms. The essence of recurrence operations on a set of binary polynomials reduced to calculating the residues by the module of the polynomial irreducibility test represented in vector form from the deduction square formed at the previous transformation step and added to the right by zero. If the upper (threshold) degree of the synthesized non-acceptance polynomials is not large, e.g., does not exceed two tens. The formation of the set of polynomials under test can be carried out by the method of total elimination. When the degree of polynomial exceeds the threshold value, it is more convenient to generate the polynomials under test by statistical modeling. The paper briefly describes the synthesis algorithm for irreducible polynomials over a simple Galois field of characteristics .
Неприводимые полиномы находят широкое применение в различных областях науки и техники. Несмотря на большую востребованность синтез неприводимых полиномов до настоящего времени представляет собой достаточно сложную задачу и, как отмечено В. Жельниковым, «нахождение неприводимых полиномов до сих пор покрыто мраком. Криптографические службы высокоразвитых стран работали и работают над поиском многочленов как можно более высокой степени, но свои результаты они почти не освещают в открытой печати». Известные алгоритмы синтеза неприводимых полиномов обладают существенным недостатком, который состоит в том, что их вычислительная сложность является, как правило, квадратической. Следовательно, построение полиномов больших степеней может быть реализовано лишь на вычислительных комплексах весьма высокой производительности. Предлагаемый алгоритм опирается на так называемые реперные сетки (лестницы), число ступенек в которых совпадает со степенью синтезируемых полиномов. На каждой ступеньке лестницы осуществляются простейшие рекуррентные однотипные модулярные вычисления, по завершении которых тестируемый полином однозначно классифицируется или как неприводимый, или как составной. Разработанный алгоритм относится к подклассу алгоритмов линейной сложности. Суть рекуррентных операций на множестве двоичных полиномов сводится к вычислению остатков по модулю тестируемого на неприводимость полинома, представленного в векторной форме (набором бинарных коэффициентов полинома), от квадрата вычета, образованного на предыдущей ступеньке преобразования и дополненного справа нулем. Если верхняя (пороговая) степень синтезируемых полиномов не велика, например, не превышает двух десятков, то формирование множества тестируемых полиномов может осуществляться методом полного перебора. В том случае, когда степень полинома превышает пороговое значение, то их генерацию удобнее реализовывать статистическим моделированием. В работе кратко изложен алгоритм синтеза неприводимых полиномов над простым полем Галуа характеристики.
Незвідні поліноми знаходять широке застосування в різноманітних областях науки і техніки. Незважаючи на велику затребуваність синтез незвідних поліномів до теперішнього часу є досить складне завдання і, як зазначено В. Жельніковим, «знаходження незвідних поліномів досі покрито мороком. Криптографічні служби високорозвинених країн працювали і працюють над пошуком многочленів якомога більш високого ступеня, але свої результати вони майже не висвітлюють у відкритій пресі». Відомі алгоритми синтезу незвідних поліномів мають суттєвий недолік, який полягає в тому, що їх обчислювальна складність є, як правило, квадратичною. Отже, побудова поліномів великих ступенів може бути реалізовано лише на обчислювальних комплексах високої продуктивності. Запропонований алгоритм спирається на так звані реперні сітки (сходи), число сходинок в яких збігається зі ступенем синтезованих поліномів. На кожній сходинці здійснюються найпростіші рекурентні однотипні модулярні обчислення, по завершенні яких поліном, що тестується, однозначно класифікується або як незвідний, або як складовий. Розроблений алгоритм відноситься до підкласу алгоритмів лінійної складності. Суть рекурентних операцій на множені двійкових поліномів зводиться до обчислення залишків за модулем тестуємого на незвідність поліному, представленого в векторній формі (набором бінарних коефіцієнтів поліному), від квадрата залишку, утвореного на попередній сходинці перетворення і доповненого справа нулем. Якщо верхня (порогова) ступінь синтезованих незвідних поліномів не велика, наприклад, не перевищує двох десятків, то формування множені поліномів, що тестуються, може здійснюватися за методом повного перебору. У тому випадку, коли ступінь поліному перевищує порогове значення, то генерацію поліномів зручніше реалізовувати статистичним моделюванням. В роботі коротко позначений алгоритм синтезу незвідних поліномів над простим полем Галуа характеристики
 
Publisher National Aviation University
 
Contributor —
—
—
 
Date 2020-07-01
 
Type —
—
—
 
Format application/pdf
application/pdf
application/pdf
 
Identifier http://jrnl.nau.edu.ua/index.php/ZI/article/view/14868
10.18372/2410-7840.22.14868
 
Source Ukrainian Information Security Research Journal; Том 22, № 2 (2020); 74-87
Защита информации; Том 22, № 2 (2020); 74-87
Захист інформації; Том 22, № 2 (2020); 74-87
 
Language uk
 
Rights Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Авторы, публикующие в данном журнале, соглашаются со следующим: Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.Авторы сохраняют право заключать отдельные контрактные договоронности, касающиеся не-эксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге), со ссылкой на ее оригинальную публикацию в этом журнале.Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами: Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
 

Технічна підтримка: НДІІТТ НАУ