ФАКТОРИЗАЦІЯ СТУПЕНЯ СФЕНІЧНИХ ПОЛІНОМІВ

Автор(и)

  • Білецький Анатолій Якович кафедра електроніки, робототехніки та технологій мониторингу и Інтернету речей Національного авіа-ційного університету https://orcid.org/0000-0002-3798-8150
  • Ковальчук Арсен Віталійович кафедра електроніки, робототехніки та технологій мониторингу и Інтернету речей Національного авіа-ційного університету https://orcid.org/0000-0001-5085-3173

DOI:

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

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

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

Анотація

До сфенічних будемо відносити поліноми, що утворені добутком трьох (не обов'язково різних) простих поліномів з апріорі невідомими ступенями. Основне завдання дослідження полягає у розробці ефективного алгоритму факторизації ступеня сфенічних поліномів, що забезпечує мінімум обчислювальної складності. Розглянуто різні варіанти вирішення проблеми факторизації залежно від співвідношень ступеня та періоду циклу цих поліномів. Період циклу сфенічного полінома визначений як параметр, якій дорівнює числу відрахувань, що не повторюються, та обчислений на лінійно-логарифмічній шкалі групи відрахувань за модулем сфенічного поліному. Пропонований алгоритм інваріантний до характеристик полів Галуа, що породжуються співмножниками сфенічних поліномів. Коректність результатів дослідження підтверджується численними прикладами.

Посилання

Сфеническое число. Wikipedia [online], Available at: https://dic.academic.ru/dic.nsf/ ruwiki/1644009.

Сфеническое число. Wikipedia [online], Available at: https://wikisko.ru/wiki/Sphenic_number.

Шпаринский И.Е. О некоторых вопросах теории конечных полей, УМН, 46:1(277) (1991). — С. 165-200. Wikipedia [online], Available at: www.mathnet.ru/links/c42de5a12c7ae9608284aece3963a1fa/rm4570.pdf.

Gerald Tenenbaum. Introduction to Analytic and Probabilistic Number Theory. Cambridge University Press, (2004). ISBN 978-0-521-41261-2

Полупростое число. Wikipedia [online], Available at: https://wiki5.ru/wiki/Semiprime.

Anatoly Beletsky. Factorization of the Degree of Semisimple Polynomials of one Variable over the Galois Fields of Arbitrary Characteristics. WSEAS Transactions on Mathematics. Vol. 21, 2022, Art. 23, p.p. 160-172. DOI: 10.37394/23206.2022.21.23.

Ишмухаметов Ш.Т. Методы факторизации натуральных чисел. – Казань: Казанский ун-т. 2011. – 190 с.

Bach E., Shallit J. Factoring with cyclotomic polynomials. – Math. Comp. 1989. v.52(185), p. 201–219.

Schneier B., Applied cryptography, Second Edition: Protocols, Algorithms, and Source Code in C+. John Wiley & Sons, New York (1996).

Chervyakov N.I., Kolyada A.A., Lyakhov P.A. Modular arithmetic and its applications in Infocommunication technologies. – M.: Fizmatlit, 2017. – 400 p.

Henri Cohen. A course in computational algebraic number theory. Berlin, Springer, 1996. – 545 p.

Anatoly Beletsky. An Effective Algorithm for the Synthesis of Irreducible Polynomials over a Galois Fields of Arbitrary Characteristics. WSEAS Transactions on Mathematics. VOL 20, 2021. – pp. 508-519. DOI: 10.37394/23206.2021.20.54.

Lidl R., Niederreiter H. Finite Fields. Cambridge University Press (1996).

Круглые числа. Wikipedia [online], Available at: https://dic.academic.ru/dic.nsf/ruwiki/ 180635.

##submission.downloads##

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

2022-10-11

Номер

Том 24 № 1 (2022): Захист інформації

Розділ

Статті

Ліцензія

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

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

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

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