О порядках элементов квадратичного расширения конечного поля характеристики 2
Аннотация
Пусть F(2m) произвольное поле характеристики 2, его квадратичное расширение мы будем рассматривать как алгебру с базисом 1, e над полем F(2m). Здесь 1 рассматривается как единичный элемент алгебры, а элемент e удовлетворяет соотношению e2 = e + α. Элемент α может быть произвольным из поля F(2m), но неудовлетворяющий условию α = x + x2 при некотором x из F(2m).
Пусть n0 (α) обозначает порядок элемента e. Тогда основной результат работы можно сформулировать так: Неприводимый полином 1 + t + αt2 делит полином 1 + tn тогда и только тогда, когда n0 (α) делит натуральное n.
Аналогичные результаты для произвольных элементов поля F(2m) следуют из этого. Доказательство базируется на свойствах рекуррентных соотношений между полиномами Pn (α) и Qn (α), определяемые для всех n = 0, 1, 2, … из соотношений en = Pn (α) + Qn (α) e. Формулы для производящих рядов этих полиномов содержат наиболее важные такие свойства. Эти формулы были получены.
Литература
[2] Koblitz N. A Course in Number Theory and Cryptography. Graduate Texts in Mathematics. 1987; 114. Springer, New York, NY. (In Eng.) DOI: https://doi.org/10.1007/978-1-4684-0310-7
[3] Maksimov V.M., Primenko E.A., Borisov A.V. Statisticheskij podhod k zadache diskretnogo logarifmirovanija [Statistical approach to the discrete logarithm problem]. In: Proceeding of the Humanitarian Readings of RSUH. Moscow, Yanus-K; 2019. p. 38-42. Available at: https://www.elibrary.ru/item.asp?id=39235884 (accessed 13.08.2020). (In Russ.)
[4] Kuzmin A.S., Markov V.T., Mikhalev A.A., Mikhalev A.V., Nechaev A.A. Cryptographic Algorithms on Groups and Algebras. Fundamentalnaya i Prikladnaya Matematika = Fundamental and Applied Mathematics. 2015; 20(1):205-222. Available at: https://www.elibrary.ru/item.asp?id=25686556 (accessed 13.08.2020). (In Russ., abstract in Eng.)
[5] Moldovyan N., Moldovyan A. Vector Finite Groups as Primitives for Fast Digital Signature Algorithms. In: Popovich V.V., Claramunt C., Schrenk M., Korolenko K.V. (ed.) Information Fusion and Geographic Information Systems. Lecture Notes in Geoinformation and Cartography. Springer, Berlin, Heidelberg; 2009. p. 317-330. (In Eng.) DOI: https://doi.org/10.1007/978-3-642-00304-2_22
[6] Adleman L.M., DeMarrais J. A Subexponential Algorithm for Discrete Logarithms over All Finite Fields. In: Stinson D.R. (ed.) Advances in Cryptology – CRYPTO'93. CRYPTO 1993. Lecture Notes in Computer Science. 1994; 773:147-158. Springer, Berlin, Heidelberg. (In Eng.) DOI: https://doi.org/10.1007/3-540-48329-2_13
[7] Herlestam T., Johannesson R. On computing logarithms over GF(2p). BIT Numerical Mathematics. 1981; 21(3):326-334. (In Eng.) DOI: https://doi.org/10.1007/BF01941467
[8] ElGamal T. On Computing Logarithms Over Finite Fields. In: Williams H.C. (ed.) Advances in Cryptology – CRYPTO'85 Proceedings. CRYPTO 1985. Lecture Notes in Computer Science. 1986; 218: 396-402. Springer, Berlin, Heidelberg. (In Eng.) DOI: https://doi.org/10.1007/3-540-39799-X_28
[9] Coppersmith D. Fast evaluation of logarithms in fields of characteristic two. IEEE Transactions on Information Theory. 1984; 30(4):587-594. (In Eng.) DOI: https://doi.org/10.1109/TIT.1984.1056941
[10] Thomé E. Computation of Discrete Logarithms in "F" ┬"2" "607". In: Boyd C. (ed.) Advances in Cryptology – ASIACRYPT 2001. ASIACRYPT 2001. Lecture Notes in Computer Science. 2001; 2248:107-124. (In Eng.) DOI: https://doi.org/10.1007/3-540-45682-1_7
[11] Thomé E. Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm. In: Proceedings of the 2001 international symposium on Symbolic and algebraic computation (ISSAC'01). Association for Computing Machinery, New York, NY, USA; 2001. p. 323-331. (In Eng.) DOI: https://doi.org/10.1145/384101.384145
[12] Semaev I. New algorithm for the discrete logarithm problem on elliptic curves. arXiv: 1504.01175. 2015. Available at: https://arxiv.org/abs/1504.01175 (accessed 13.08.2020). (In Eng.)
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
