Решение нелинейных двучленных сравнений

Рассмотрим двучленные сравнения степени п, т. е. сравнения вида х" = = a (modm), где (а, т) = 1. Решения такого сравнения называются вычетами степени п по модулю т (квадратичными, кубическими и т. д.), остальные элементы называются невычетами степени п по модулю т.

В ряде задач требуется знать решения уравнения х^т — 1 в поле GF (pⁿ). Определим, сколько корней т-й степени из 1 содержится в поле GF (p").

Элемент поля GF (pⁿ) называется примитивным корнем т-й степени из 1, если циклическая группа (?) состоит из всех корней т-й степени из 1.

Утверждение 5.1.

• а) элемент gi, где g — образующий группы GF (p")*, есть корень т-й степени из 1 mj = 0(mod (p" - 1)), число корней равно (т, р^п — 1);
• б) GF (pⁿ)* содержит примитивный корень m-й степени из 1 т р^п — 1, при этом в GF (p") имеется ф(т) различных примитивных корней.

А Если GF (pⁿ)* - (g), то элементы группы имеют вид gJ, j = 1,…, р^п — 1. Отсюда gi = 1 «(р^п — 1)j, т. е. gj есть корень m-й степени из 1 ту = = 0(mod (p» — 1)).

Пусть d = (т, р^п — 1). Тогда сравнение mj = 0(mod (p^tt — 1)) относительно неизвестного у равносильно сравнению mj / d = 0(mod ((jO" - 1) / d)). Поскольку m / d и (pⁿ — 1) / d взаимно просты, то последнее сравнение выполнено j кратно (р" - 1) / d. Значит, {q, <;²,…, с,'¹} — множество корней m-й степени из 1, где? = / ^d при q = р^п

б) если GF (pⁿ) содержит ^ — примитивный корень m-й степени из 1, то содержит и подгруппу (<;) порядка т. Число корней вида ^²,…, равно m «d = т т | (р^п — 1). В группе (?) порядка m по следствию 2 теоремы 4.10 имеется ф (т) различных примитивных корней. ?

Следствие 1. Если (m, р" - 1) = 1, то 1 — единственный корень m-й степени из 1.

Следствие 2. В GF (p")* имеется элемент i = V-T р" = l (mod4).

Л Элемент i является примитивным корнем 4-й степени из 1. По утверждению 5.1б такой корень имеется в GF (pⁿ)* 4 | р^п — 1. ?

Рассмотрим двучленное сравнение х² = «(modp), р — простое. Если b — корень сравнения, то и (-Ь) тоже корень сравнения, тогда все квадратичные вычеты можно найти, вычисляя b² по модулю р для b — 1, …, (р — 1) / 2. Если F_;)* = (g), то любые элементы F_;)* имеют вид gi, j = 1, …, р- 1. Тогда квадраты — это половина элементов F_p*, а именно, gi с четной степенью j.

Для целого а и простого р > 2 определим символ Лежандра-. — равен Ы.

нулю, если/? | а, равен единице, если а — квадратичный вычет по mod/?, равен.

" _Л («) f «(mod/?)'.

— 1, если а — квадратичный невычет по mod/?. Отсюда — = - .

Р) I Р

Утверждение 5.2. Символ Лежандра задается формулой.

• •4 Если р | а, то обе части равенства сравнимы с 0 но mod/?. Пусть р не делит а. Если g — образующий в F_;)*, то а = gJ и левая часть сравнения равна 1 степень j четная. Вместе с тем, но малой теореме Ферма в F_p квадрат числа й (р-1)/2 есть 1, тогда а (р-1)/2= ±1. Отсюда a (p-i)/2 = gj (p-)/2 ₌
• — четное. Значит, левая и правая части сравнения

равны. ?

Утверждение 5.3 (свойства символа Лежандра).

•> (тНШ).

п 1 (^а)

б) если (о, р) — 1, то — = — ;

Р) Р)

• (1 ^ (-1)
• в) — = 1 и — = (-1)<�М)/2.

Кр) кр).

• •4 а) В силу утверждения 5.2 обе части сравнимы с (яб)О'^-1)/²;
• б) следует из а);
• в) первое равенство верно по определению символа Лежандра. Второе равенство вытекает из утверждения 5.2 при а = -1. ?

Замечание. По утверждению 5.3а вычисление символа Лежандра для а сводится к вычислению символов для делителей числа а, например для нечетного b при а = 2^кЬ. О Утверждение 5.4. В поле GF (p²) верна формула.

• 2
• 4 Покажем, что — = /(/?), где /(«) = (—1)<» ²⁻¹>/⁸ при нечетном п Р)

и f{n) = 0 при четном п. Поскольку р²= l (mod8) для нечетного простого р, то по утверждению 5.16 поле GF (p²) содержит примитивный корень Е,

• 7 ч-1
• 8-й степени из 1. Пусть 5(?) =? /0)^> суммы X ^а& ^с коэффициенте «/=о

тами ±1 при простом q называют гауссовыми суммами.

Упростим 5(?), заметив, что = -1, ?⁵ = q⁷ = -q-E 5(?) = E_S- q³ — q^r> + + E² = 2(2, — ^³). Тогда (б'(?))² = 4(^² — 2^⁴ + ^⁶) = 8, и в соответствии с утверждениями 5.2 и 5.36.

Используя в GF (p²) соотношения (а + Ь) р=ор+Ьр и (/(«))/' = /(и), имеем.

• 7
• (S (c,))/^J = X f (J%^pj- Сделав замену переменных k-pj (подстановку множено

ства {0, 1,7}) и используя очевидное равенство f (j) = f (p)f (pj), получаем (2

Следовательно, — 5'(?) = f (p)S (L). Поскольку (5(?))² = 8 в GF (p²), то Р)

5(?) Ф 0. Тогда, сократив последнее равенство, получаем нужную формулу. ?

Свяжем — и — для простого нечетного (/, не равного/;. Если q <�р, то.

KPJ Ч)

• (р) (p (modq))
• — = -, что позволяет определять символ Лежандра для меньших

Ч) I Ч

чисел.

Теорема 5.10 (квадратичный закон взаимности). Для нечетных простых р и q

где с = -1, если p = q = 3(mod4), и с — 1 в остальных случаях.

Л Пусть п — огф в группе GF (q)*, т.е.р^п= l (mod<7). По утверждению 5.16 GF (pⁿ) содержит примитивный корень с, q-й степени из 1. Определим гауссову сумму L (%) =

;=о Ч)

Лемма 5.1 (промежуточная).

Г-Л В соответствии с утверждением 5.3 В заменим — на (-1)^/-0/² и сде;

V Ч

лаем замену переменных k —>jk, при любом j Ф 0 это подстановка множества.

{1, …, q- 1}. ТогдаL (4)E (^) = (-l)(?^_1)/2^? -— Используяутверж;

j=ii=iy q J

дение 5.36, изменяя порядок суммирования и вынося — за пределы вну;

Ч)

q-(Uq-

тренней суммы по j, получаем = (-1)(?-1)/2? — ??./(1-*). Сумма.

k=q)j=

q-Uk

Yj — =0, так как числа вычетов и невычетов равны. Добавив ее к пре- к=Я) _tq-{ k^q~^{

дыдущему равенству, имеем L (?)I (?) = (-l)^-¹)/²^ — ??./(1-*). Сумма.

k= V Я)j=o

?, + +…+ есть сумма всех ненулевых элементов поля GF (q), равная 0.

по modк Ф 1 внутренние суммы равны 0. Отсюда.

Вернемся к теореме. Используя лемму 5.1, имеем.

(4 У.

Вместе с тем, используя в GF (pⁿ) соотношения (а + Ь) р = а1^}+ Ьр и — =.

Я)

/ Л J

= —, имеем Я)

/

Вынося — за знак суммы и меняя затем порядок суммирования с помо- Я)

" (п

щыо замены j —"pj, приходим к соотношению (L (^))p= — L (^). Следова;

(аЛ (р

тельно, (— 1)0-¹)(^-¹)/⁴ УЦ?)= 2- Ц?).

р) U г

По лемме 5.1 /.(?) Ф 0, тогда, сократив равенство, получаем нужную формулу. ?

Пример 5.4.

Найти, есть ли 7411 квадратичный вычет по простому модулю 9283. Числа 7411 и 9283 — простые и сравнимые с 3 по модулю 4, тогда имеем.

Используя каноническое разложение: 1872 = 2⁴ • З² • 13, получаем.

Применяем теорему 5.10, учитывая, что 13 = 1(тос14):

т.е. 7411 — невычет по модулю 9283. О Пример показывает, что при больших числах неудобство вычислений состоит в необходимости определять канонические разложения чисел. Однако это неудобство преодолимо.

Для целого а и нечетного п определим символ Якоби — через символы.

п)

Лежандра с учетом канонического разложения (2.1) числа п:

Утверждение 5.5. Для нечетного натурального п верно следующее:

— ] = (_1)(«²-1)/8.

У^п)

4 Пусть f (n) = (—1)^" ^2₁>/⁸, тогда f{n_xn₂) = f{n_x)J ₂) для любых нечетных п_х и п₂, что можно проверить, опробовав в качестве п_х и п₂ все нечетные неотрицательные вычеты по модулю 8. Используя это свойство и утверждение 5.4, получаем, что правая часть равна.

Теорема 5.11 (квадратичный закон взаимности для символов Якоби).

/ /.

771 71

Для нечетных натуральных тг и m верно — = (-1)(от-1)(и-1)/4 —.

• п) ут)
• 4 Если (n, т)> 1, то по определению символов Лежандра и Якоби обе части равны 0.

Пусть (тг, тп) = 1, т=р_х…р_п тг = q_x…q_s — произведения простых чисел, где.

/ (

П ^т Т1 Pi

повторения возможны. Для перехода от символа — = [ [ —- к символу.

w ‘Ля.,)

• (_п (q
• — = П — необходимо rs раз применить квадратичный закон взаим- ^т) ujPi)

ности для символов Лежандра. При этом по теореме 5.10 перемена знака произойдет и раз, где и — число пар (i, j) таких, что i е {1,…, /-}, j е {1,…, s} и p,(modm) = g,(modn) = 3(mod4). Значит, и = и_хи₂, где и_{ и и₂ — число простых сомножителей в разложении тип соответственно, сравнимых.

(т (п

с 3(mod4). Значит, — =- —, если нечетными являются числа простых,.

™)

сравнимых с 3(mod4) сомножителей в разложениях чисел тип. В про;

(тЛ (п 'j.

тивном случае — = —. Однако произведение нечетных простых чисел п) т)

• (п и т таковы) сравнимо с 3(mod4) о оно содержит нечетное число сомно-
• (т

жителей, сравнимых с 3(mod4). Значит, коэффициент, связывающий —.

^ V^п

и —, равен -1 т = п = 3(mod4). ?

т)

Вычислим символ Лежандра (см. пример 5.4), не разлагая 1872 на множители полностью, выделяя в нем лишь максимальную степень 2. По квадратичному закону взаимности для символов Якоби имеем.

Итак, квадратичный закон взаимности позволяет определить, является ли а квадратичным вычетом. С алгоритмом вычисления квадратного корня из а по модулю простого нечетного р можно ознакомиться в [26].