1683-3414 1814-0807

Владикавказский математический журнал

Vladikavkaz Mathematical Journal

Южный математический институт - филиал Федерального государственного бюджетного учреждения науки Федерального научного центра «Владикавказский научный центр Российской академии наук» (ЮМИ ВНЦ РАН)

О применениях конечных полей к функции Эйлера

On Applications of Finite Fields to the Euler Function

10.46698/m2155-1449-8044-d

17198

09 2025

27 3 120 126

https://vmj.ru/archive/detail.php?ELEMENT_ID=17198&SECTION_ID=635

Пачев

У. М.

Pachev

U. M.

urusbi@rambler.ru

Токбаева

А. А.

Tokbaeva

A. A.

tok2506@mail.ru

Кабардино-Балкарский государственный университет, 360004, Нальчик, ул.Чернышевского, 173 Kabardino-Balkarian State University, 173 Chernyshevsky St., Nalchik 360004, Russia

Работа относится к применениям конечных полей к функции Эйлера из теории чисел. С помощью понятия нормированного неприводимого многочлена заданной степени над конечным полем $F_{q}$ получен некоторый аналог известного соотношения Гаусса $\sum\nolimits_{d|n}\varphi(d)=n$. Здесь $\varphi(k)$ - арифметическая функция Эйлера, значение которой равно количеству чисел ряда $1,2,\ldots,k$, взаимно простых с числом $k$. Для формулировки и доказательства аналога этого соотношения используется ряд понятий и предварительных результатов из теории многочленов над конечным полем $F_{q}$ из $q$ элементов. Именно к ним относятся понятия нормированного неприводимого многочлена от одной переменной над полем $F_{q}$ и $n$-кругового многочлена $Q_{n}(x)$ над любым полем ненулевой характеристики. Кроме того, существенно используется также понятие порядка многочлена $f(x) \in F_{q}[x]$, согласно которому наименьшее натуральное число $e$, для которого многочлен $f(x)$ делит $x^{e}-1$ в кольце $F_{q}[x]$ есть порядок многочлена $f(x)$. При этом на явной формуле $n$-кругового многочлена $Q_{n}(x)$, а также на вспомогательном результате для числа нормированных неприводимых многочленов $f(x) \in F_{q}[ x]$ степени $m$ и заданного порядка $e$ основаны доказательства основных новых результатов. Основными из них являются формула для числа $N_{q}(n)$ нормированных неприводимых многочленов степени $n$, а также аналог соотношения Гаусса для функции Эйлера.

The manuscript is devoted to applications of finite fields to the Euler function from number theory. Using the concept of a normalized irreducible polynomial of a given degree over a finite field $F_q$, we obtain an analogue of the well known Gauss relation $\sum_{d|n}{\varphi(d) =}n$. Here $\varphi(k)$ is the Euler arithmetic function such that its value is equal to the number of integers $1,2,\ldots,k$ relatively prime to $k$. In order to formulate and prove an analogue of this relation we use concepts and preliminary results from the polynomial theory over a finite field $F_{q}$ of $q$ elements. In particular, we apply the concepts of a normalized irreducible polynomial of one variable over the field $F_{q}$ and $n$-circle polynomial $Q_{n}(x)$ over any field of nonzero characteristic. In addition, we use the concept of the order of a polynomial $f(x) \in F_{q}[x]$ such that if the polynomial $f(x)$ divides $x^{e} - 1$ in the ring $F_{q}[x]$, then the minimal natural number $e$ is the order of the polynomial $f(x)$. The proof of the main new results is based on the explicit formula for the $n$-circle polynomial $Q_n(x)$ and on the auxiliary result for the number of normalized irreducible polynomials $f(x)\in F_{q}[x]$ degree $m$ and given order $e$. We obtain the formula for $N_{q}(n)$ of normalized irreducible polynomials degree $n$ and an analogue of the Gauss relation for the Euler function.

конечное поле нормированный неприводимый многочлен порядок многочлена $n$-круговой многочлен функция Эйлера

finite field normed irreducible polynomial polynomial order $n$-cyclotomic polynomial Euler function

Гаусс К. Ф. Труды по теории чисел. М.: Изд-во АН СССР, 1959. 987 с.

Gauss, K. F. Works on Number Theory, Moscow, Publishing House the USSR Academy of Sciences, 1959, 987 p. (in Russian).

Галуа Э. Из теории чисел. Сочинения. М.-Л.: ОНТИ, 1936. 342 с.

Galois, E. From the Theory of Numbers. Works, Moscow, Leningrad, ONTI, 1936, pp. 35-47 (in Russian).

Пачев У. М. Избранные главы теории чисел. Нальчик: Изд-во М. и В. Котляровых, 2016. 186 с.

Pachev, U. M. Selected Chapters of Number Theory, Nalchik, "M. and V. Kotlyarov", 2016, 186 p. (in Russian).

Минеев М. П., Чубариков В. Н. Лекции по арифметическим вопросам криптографии. М.: Изд-во "Луч", 2014. 224 с.

Mineev, M. P. and Chubarikov, V. N. Lectures on Arithmetic Issues of Cryptography, Moscow, 2014, 224 p. (in Russian).

Степанов С. А. Сравнения. М.: Изд-во "Знание", 1975.

Stepanov, S. A. Congruences, Publishing house "Knowledge", Moscow, 1975 (in Russian).

Лидл Р., Нидеррайтер Г. Конечные поля. Т. 1. М.: "Мир", 1988. 486 с.

Lidl, R. and Niederreiter, H. {Finite Fields. Vol. 1, Cambridge University Press, 1983.

Ленской Д. Н. К арифметике многочленов над конечным полем // Волжский матем. сб. Тр. матем. кафедр пед. ин-тов Поволжья. 1966. Вып. 4. C. 155-159.

Lenskoy, D. N. On the Arithmetic of Polynomials Over a Finite Field, Volzhsky Mat. Sb., Kuibishev. Works of Mathematical Departaments of Pedagogical Institutes of the Volga Region, issue 4, 1966, pp. 155-159 (in Russian).

Fredman M. L. Congruence formulas obtained by counting irreducible // Pacific J. Math. 1970. Vol. 35, № 3. P. 613-624. DOI: 10.2140/pjm.1970.35.613.

Fredman, M. L. Congruence Formulas Obtained by Counting Irreducible, Pacific Journal of Mathematics, 1970, vol. 35, no. 3, pp. 613-624. DOI: 10.2140/pjm.1970.35.613.

Степанов С. А. О числе неприводимых в $F_{q[x]}$ многочленов специального вида // Успехи мат. наук. 1985. Т. 40, вып. 4(244). С. 199-200.

Stepanov, S. A. On the Number of Irreducible Polynomials in $F_{q[x]$ of Special Form, Russian Mathematical Surveys, 1985, vol. 40, no. 4, pp. 219-220. DOI: 10.1070/RM1985v040n04ABEH003656.

Carlitz L. The arithmetic of polynomials in a Galois field // Proc. Nat. Acad. Sci. 1931. Vol. 17, № 2. P. 120-122. DOI: 10.1073/pnas.17.2.120.

Carlitz, L. The Arithmetic of Polynomials in a Galois Field, Proceedings of the National Academy of Sciences, 1931, vol. 17, no. 2, pp. 120-122. DOI: 10.1073/pnas.17.2.120.

Willams K. S. Polynomials with irreducible factors of specified degree // Canada. Math. Bull. 1969. Vol. 12, № 2. P. 221-223. DOI: 10.4153/CMB-1969-026-2.

Willams, K. S. Polynomials with Irreducible Factors of Specified Degree, Canadian Mathematical Bulletin, 1969, vol. 12 , no. 2, pp. 221-223. DOI: 10.4153/CMB-1969-026-2.

Пачев У. М., Кодзоков А. Х., Машезова А. М. Об оценках числа нормированных неприводимых многочленов заданной степени над конечным полем // Алгебра и динамические системы. Тез. докл. Междунар. конф., посвящ. 110-летию со дня рождения С. Н. Черникова. Нальчик, 2022. С. 100-101.

Pachev, U. M., Kodzokov, A. Kh. and Mashezova, A. M. On Estimates on the Number of Normalized Irreducible Polynomials of a Given Degree Over a Finite Field, Algebra and Dynamical System. Abstracts of Reports of the International Conference Dedicated to the 110-th Anniversary of the Birth of S. N. Chernikov, Nalchik, 2022, pp. 100-101.

Carlitz L. Some theorems on irreducible polynomials over a finite field // J. Reine Angen. Math. 1967. Vol. 227. P. 212-220.

Carlitz, L. Some Theorems on Irreducible Polynomials Over a Finite Field, Journal fur die reine und angewandte Mathematik, 1967, vol. 227, pp. 212-220.

Levine J., Brawley J. V. Involutory commutants with some applications to algebraic cryptographic // J. Reine Angew. Math. 1966. Vol. 224. P. 20-43.

Levine, J. and Brawley, J. V. Involutory Commutants with Some Applications to Algebraic Cryptography, Journal fur die Reine und Angewandte Mathematik, 1966, vol. 224, pp. 20-43.

Levine J., Brawley J. V. Some cryptographic applications of permutation polynomials // Cryptologia. 1977. Vol. 1. P. 76-92. DOI:10.1080/0161-117791832814.

Levine, J. and Brawley, J. V. Some Cryptographic Applications of Permutation Polynomials, Cryptologia, 1977, vol. 1, pp. 76-92. DOI:10.1080/0161-117791832814.