Символ Лежандра

Символом Лежандра називається мультиплікативна функція, що використовується в теорії чисел. Названа на честь французького математика Адрієна-Марі Лежандра.

Визначення

Нехай a деяке ціле число і p просте число. Символ Лежандра ${\displaystyle \left({\frac {a}{p}}\right)}$ визначається таким чином:

• ${\displaystyle \left({\frac {a}{p}}\right)=0}$, якщо ${\displaystyle \ a}$ ділиться на ${\displaystyle \ p}$.
• ${\displaystyle \left({\frac {a}{p}}\right)=1}$, якщо ${\displaystyle \ a}$ є квадратичним лишком за модулем ${\displaystyle \ p}$, тобто існує таке ціле ${\displaystyle \ x}$, що ${\displaystyle \ x^{2}\equiv a{\pmod {p}}}$.
• ${\displaystyle \left({\frac {a}{p}}\right)=-1}$, якщо ${\displaystyle \ a}$ є квадратичним нелишком за модулем ${\displaystyle \ p}$.

Властивості

• Мультиплікативність: ${\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)}$
• Якщо ${\displaystyle \ a\equiv b{\pmod {p}}}$, то ${\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}$
• ${\displaystyle \left({\frac {1}{p}}\right)=1}$
• ${\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{(p-1)/2},}$ перший додатковий закон (англ. first supplementary law)
• ${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{(p^{2}-1)/8},}$ другий додатковий закон (англ. second supplementary law)

Доведення

Нехай ${\displaystyle s={\frac {p-1}{2}}}$, і розглянемо ${\displaystyle s}$ рівнянь

${\displaystyle {\begin{aligned}1&=(-1)(-1)\\2&=2(-1)^{2}\\3&=(-3)(-1)^{3}\\4&=4(-1)^{4}\\&\quad \quad \ldots \\s&=(\pm s)(-1)^{s}\end{aligned}}}$

Тут ми обираємо знак так, щоб мати правильний знак результату.

Зараз множимо ${\displaystyle s}$ рівнянь разом. Ліворуч отримуємо ${\displaystyle s!}$. Праворуч, маємо ${\displaystyle 2,4,6,\dots }$ і якісь від'ємні непарні числа. Але зауважимо, що ${\displaystyle 2(s)\equiv -1\mod p}$, ${\displaystyle 2(s-1)\equiv -3\mod p}$, і т.д., отже, ці від'ємні числа є іншими парними числами за модулем ${\displaystyle p}$, але прихованими. Отже права частина становить ${\displaystyle s!(2^{s})}$ (кожна двійка парна до одного з членів факторіалу, щоб представити парні числа за модулем ${\displaystyle p}$).

Залишилось лише зауважити, що ${\displaystyle (-1)^{1+2+\ldots +s}=(-1)^{s(s+1)/2}}$ і перенести в ліву частину.

Збираючи все до купи, ми отримуємо ${\displaystyle 2^{s}s!\equiv s!(-1)^{s(s+1)/2}\mod p}$, або по скороченні факторіалів ${\displaystyle 2^{s}\equiv (-1)^{s(s+1)/2}}$. І ${\displaystyle s(s+1)/2=(p^{2}-1)/8}$, отже ми насправді маємо ${\displaystyle 2^{(p-1)/2}\equiv (-1)^{(p^{2}-1)/8}}$.

• Якщо ${\displaystyle q}$ — просте число, не рівне ${\displaystyle p}$, то ${\displaystyle \left({\frac {q}{p}}\right)\left({\frac {p}{q}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}}$ — частковий випадок квадратичного закону взаємності.
• Серед чисел ${\displaystyle 1\leq a\leq p-1}$ рівно половина має символ Лежандра, рівний +1, а інша половина — –1.
• Символ Лежандра при ${\displaystyle p>2}$ можна обчислити за допомогою критерію Ейлера: ${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}{\pmod {p}}}$

Обчислення

Безпосереднє застосування критерію Ейлера для обчислення символу Лежандра потребує піднесення до степеня, що для великих значень ${\displaystyle a}$ і ${\displaystyle p}$ є доволі складним (зокрема, доводиться застосувати довгу арифметику) та вельми трудомістким. Набагато ефективніше обчислювати символи Лежандра через їх узагальнення — символи Якобі[1].

Приклад

${\displaystyle \left({\frac {12345}{331}}\right)}$

${\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right)}$

${\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right)}$

${\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right)}$

${\displaystyle =(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right)}$

${\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right)}$

${\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3}{23}}\right)^{2}}$

${\displaystyle =-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1.}$

Див. також

• Символ Кронекера — Якобі

Джерела

1. Нестеренко, 2012, с. 69.

Література

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — Москва : Мир, 1987. — 416 с.(рос.)
• Нестеренко А. Ю. Теоретико-числовые методы в криптографии : [рос.]. — Московский государственный институт электроники и математики. — М., 2012. — 224 с. — ISBN 978-5-94506-320-4.