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

Конечные поля более целенаправленно стали изучаться в начале XIX века. Но еще до этого с разными подходами (см. [1, 2]) основы теории конечных полей были заложены в работах Гаусса и Галуа. (см. [1–3]).

Вслед за этим введением изложены вспомогательные результаты: леммы 1–5. Из них в лемме 1 дается явная формула для n-кругового многочлена Q n (x) над полем K ненулевой характеристики, при этом такой многочлен задается формулой

n

Q n (x)= П (x - ^ s ) ,

S=1,

(s,n) = 1

(О 2025 Пачев У. М., Токбаева А. А.

где £ — первообразный корень n-й степени из единицы над полем K , причем deg Q _n (x) = ^(n), где ^(n) — функция Эйлера.

В лемме 2 дается формула для произведения J(q, n; х) всех нормированных неприводимых многочленов F _q [х].

Леммы 3–5 непосредственно используются в доказательствах теорем 1 и 2, являющихся основными результатами нашей работы.

Из них в теореме 1 дается новая формула для числа N _q (n) нормированных неприводимых многочленов степени n над конечным полем F _q .

Возникает вопрос: существует ли какой-нибудь аналог известного соотношения Гаусса для функции Эйлера из теории чисел, но с меньшим числом слагаемых?

Положительный ответ на такой вопрос дает теорема 2, в ходе доказательства которой получен также новый вывод формулы для N q (n) (другой способ см. в [4, 5]).

• 1.    Вспомогательные результаты о многочленах над конечным полем

Основные понятия, относящиеся к многочленам над конечным полем даны во введении. Поэтому сразу переходим к изложению вспомогательных средств, используемых в доказательствах основных результатов.

Лемма 1 (о явной формуле n -кругового многочлена) . Для поля K характеристики p >  0 и натурального n, не делящегося на р, n-круговой многочлен задается формулой

Qn(х) = П (х“ - >)'(5’ = II (xd - О*’ ■ где µ — функция Мебиуса.

⊳ Доказательство см. в [6], где оно основано на разложении xn - 1 = nQd(x) d|n с последующим применением к этому равенству мультипликативного варианта формулы обращения Мебиуса. ⊲

Лемма 2. Произведение J(q,n; х) всех нормированных неприводимых многочленов степени n из кольца многочленов F q [х] задается формулой

J(q, n; х) = П (x q d — х) ^^ = П (^х^ d d | n                           d | n

-

x,

где µ — функция Мебиуса.

⊳ Доказательство см. в [6]. ⊲

Полезно и следующее представление для J(q,n; х) в разложенном виде через круговые многочлены.

Лемма 3. Для натурального числа n >  1 имеет место формула

J(q,n; x) = Ц Qm(x), m\qn-1

где Q m (x ) — m-круговой многочлен над полем F _q и произведение берется по всем натуральным делителям m числа q n — 1, для которых n является показателем, которому принадлежит число q по модулю m.

• < 1 Доказательство см. в [6]. >

Лемма 4. Для произведения J(q,n; x) всех нормированных неприводимых многочленов степени n из кольца многочленов F q [x] справедливо соотношение

J(q,n; x) П (x q d — x) = П (x q d - x) , d | n,                                  d | n,

^(d) = - 1                      ^(d) = 1

где µ — функция Мебиуса.

• <    В силу леммы 2 имеем

J(q,n; x) = П (xq d — x)    П (xq d - x) • d|n,                                  d|n,

^(d) = - 1                        p,(d) = 1

Умножая теперь обе части этого равенства на произведение

n

П (xq ^d

—

x,

получаем

J(q,n; x) • П (xq d — x)   = П (xq d - x) • > d|n,                                       d|n,

^(d) = - 1                            ^(d) = 1

Лемма 5. Число нормированных неприводимых многочленов из F q [x] степени m и порядка e равно ^(e- , если e ^ 2, а m — показатель, которому принадлежит число q по модулю е, равно 2, если m = e = 1, и равно нулю во всех остальных случаях.

• <    Доказательство см. в [6]. >

• 2.    Доказательства основных результатов

Отметим, что к данной части нашей работы имеют некоторое отношение публикации [7-13], в частности, в [7] доказано асимптотическое разложение для числа N _q (n) нормированных неприводимых многочленов степени n над полем F _q .

В этой части нашей работы решается вопрос, поставленный в конце введения, относительно существования аналога соотношению Гаусса для функции Эйлера.

Теорема 1. Число N q (n) неприводимых нормированных многочленов степени n в кольце F _q [x] определяется формулой

N q ⁽ n)

y^{( e )}

n

= e\qn-1, qm^1 (mod e), 1^m

<1 Так как все нормированные неприводимые многочлены степени n над полем Fq можно разбить на группы многочленов с заданным порядком e, то, применяя к каждой такой группе лемму 3 и затем суммируя по всем возможным значениям e, получим

f(e) n

Nq⁽ⁿ⁾

= Е e|qn-1, qm^1 (mod e), l^m^n где qm ^ 1 (mod e) при 1 C m C n. >

Теорема 2. Пусть q — степень простого числа; n — показатель, которому число q принадлежит по модулю e. Тогда имеет место соотношение

£    v(e) = £^(d)qn, e|qn—1,                  d|n qm^1 (mod e), ICmCn где ϕ — функция Эйлера; µ — функция Мебиуса; суммирование в левой части проводится по тем числам e, по которым число q принадлежит показателю n по модулю e.

< Воспользуемся леммой 3, согласно которой J(q,n; x) = П m|qn-1, Qm(x), где qs^l (mod e), lCsCn

Qm(x) — m-круговой многочлен над полем Fq, при этом произведение берется по всем натуральным делителям m числа qn — 1. Применяя к обеим частям этого соотношения deg, будем иметь deg J(q,n; x) = deg Ц Qm(x).

mlqn — 1

Воспользуемся еще леммой 4, согласно которой

J(q,n; x) ^  (x^qd — x) = ^ (xq d — x) .

d|n,                                  d|n,

^(d) = -1                      ^(d) = 1

Переходя в этом равенстве к степеням, будем иметь

n

n

= £ deg (xq ^d d|n,

M(d) = 1

—x .

deg J (q,n; x) +       deg (xq d d|n,

M(d) = -1

Отсюда непосредственно следует deg J(q, n; x) =

^ deg (xq^d— x) — ^ deg (xq^d— x) d|n,                                          d|n,

^(d) = -1                              ^(d) = 1

= E q d d|n, M(d) = 1

— Eqd = E ^(d)q d + E ^(d)q d = E^)q d • d|n.                     d|n.                              d|n.                            d|n

^(d) = -1          ^(d) = 1                ^(d) = -1

Теперь вычисляем также deg I(q,n; x) по лемме 3. Имеем deg I(q,n; x) = deg   Ц   Qm(x) =    ^   deg Qm(x)

m|qn-1,                    m|qn-1, qs^1(mod e),            qs^1(mod e),

1<s<n                  1<s<n

E

m|qⁿ-1, q^s^1 (mod e), 1<s<n

^(m).

Теперь из (1) и (2) следует утверждение теоремы 2. >

Приведем пример к результату теоремы 2 в случае q = 3, n = 4. Сначала находим Ed|4 ^(d) • 3d = ^(1) • 34 + ^(2) • 32 + ^(4) • 3 = 72. Теперь вычисляем

£    ^(e), e|34-11 qm^1 (mod e), 1^m

Определяем числа е, для которых jej и 3m ^ 1 (mod е) при 1 С m С 4.

Из всех делителей 80 нашим условиям будут удовлетворять только следующие числа: е1 =5, е₂= 10, ез = 16, е₄= 20, е5 = 40, еб = 80. Тогда

£    ^(е) = ^(5) + ^(10) + ^(16) + ^(20) + ^(40) + ^(80) = 72.

e|34 - 1, qm^1 (mod e), ICmCn

Значит, для обеих сумм получаем равные значения.

Сравним полученное значение с соотношением Гаусса для функции Эйлера. Имеем

£ ^^(d) = 80.

d|80

Значит,

£ ^(d) -   £   

Завершая изложение нашей работы, отметим еще, что имеются также некоторые приложения теории конечных полей к криптографии (см. [4, 15, 13]).