О порядках элементов квадратичного расширения конечного поля характеристики 2

Аннотация

Пусть F(2m) произвольное поле характеристики 2, его квадратичное расширение мы будем рассматривать как алгебру с базисом 1, e над полем F(2m). Здесь 1 рассматривается как единичный элемент алгебры, а элемент e удовлетворяет соотношению e= + α. Элемент α может быть произвольным из поля F(2m), но неудовлетворяющий условию α = + x2 при некотором x из F(2m).
Пусть n0 (α) обозначает порядок элемента e. Тогда основной результат работы можно сформулировать так: Неприводимый полином 1 + t + αt2 делит полином 1 + tn тогда и только тогда, когда n0 (α) делит натуральное n.
Аналогичные результаты для произвольных элементов поля F(2m) следуют из этого. Доказательство базируется на свойствах рекуррентных соотношений между полиномами P(α) и Qn (α), определяемые для всех n = 0, 1, 2, … из соотношений e= P(α) + Qn (αe. Формулы для производящих рядов этих полиномов содержат наиболее важные такие свойства. Эти формулы были получены. 

Сведения об авторах

Valery Mikhailovich Maximov, Российский государственный гуманитарный университет

заведующий кафедрой фундаментальной и прикладной математики, Институт информационных наук и технологий безопасности, доктор физико-математических наук, профессор

Victoria Ivanovna Remezova, Российский университет дружбы народов

магистрант факультета физико-математических и естественных наук

Литература

[1] Maksimov V.M., Primenko E.A. The Complication of Discrete Logarithms in Fields of Characteristic 2. International Journal of Open Information Technologies. 2018; 6(11):16-20. Available at: https://www.elibrary.ru/item.asp?id=36379613 (accessed 13.08.2020). (In Russ., abstract in Eng.)
[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.)
Опубликована
2020-09-30
Как цитировать
MAXIMOV, Valery Mikhailovich; REMEZOVA, Victoria Ivanovna. О порядках элементов квадратичного расширения конечного поля характеристики 2. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 16, n. 2, p. 314-320, sep. 2020. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/651>. Дата доступа: 06 mar. 2021 doi: https://doi.org/10.25559/SITITO.16.202002.314-320.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук