Algorithm for the synthesis of irreducible polynomials of linear complexity

Authors

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

DOI:

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

Keywords:

irreducible and compound polynomials, singular polynomials, defining steps, modular comparability

Abstract

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 .

Author Biographies

Анатолий Яковлевич Белецкий, National Aviation University

Doctor of Science, Professor, Honored Scientist of Ukraine, Laureate of the State Prize of Ukraine in Science and Technology, Department of Electronics, Robotics, Monitoring and IoT Technologies, Professor, National Aviation University

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

Department of Electronics, Robotics, Monitoring and IoT Technologies, Student, National Aviation University

Костянтин Андрійович Новиков, National Aviation University

Department of Electronics, Robotics, Monitoring and IoT Technologies, Student, National Aviation University

Дмитро Анатолійович Полторацький, National Aviation University

Department of Electronics, Robotics, Monitoring and IoT Technologies, Student, National Aviation University

References

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

Published

2020-07-01

Issue

Section

Articles