Квадратичные вычеты и корни по простому модулю

В этой статье вы узнаете всё о квадратичных вычетах по простому модулю и разложении числа в сумму двух квадратов.

Будем обозначать множество остатков по модулю $p$ со сложением и умножением как ${\mathbb{F}}_p$.

Будем считать, что арифметические операции в ${\mathbb{F}}_p$ работают за константое время или что то же самое, мерять все в арифметических операциях(сложение, умножение, вычитание).

Вычеты, символ Лежандра

Здесь и далее $p$ – простое число.

Определение. $a\in {\mathbb{F}}_p$ называется квадратичным вычетом если существует такое $z$, что $z^2\equiv a(\mathrm{mod}p)$, а иначе невычетом.

Определение. Символом Лежандра числа $a$ называется величина $\left(\begin{array}{c}a\\ p\end{array}\right)$, равная единице, если $a$ является квадратичным вычетом по модулю $p$, нулю если $a\equiv 0$, и $-1$ иначе.

Лемма. В ${\mathbb{F}}_p$ поровну квадратичных вычетов и невычетов, а именно $\frac{p-1}{2}$.

Доказательство. Посмотрим на числа $1^2,2^2,\dots ,(p-1{)}^2$. Заметим, что $a^2\equiv b^2$ равносильно тому что $p\mid (a-b)(a+b)$, то есть либо $a\equiv b$, либо $a\equiv -b$. А это значит, что среди первых $\frac{p-1}{2}$ квадратов нет повторяющихся, а поскольку $a^2\equiv (p-a{)}^2$, то это все квадраты, что и требовалось.

Лемма. $\left(\begin{array}{c}ab\\ p\end{array}\right)=\left(\begin{array}{c}a\\ p\end{array}\right)\left(\begin{array}{c}b\\ p\end{array}\right)$.

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

Очевидно, что произведение двух вычетов является вычетом. $a\equiv x^2,b\equiv y^2$, значит $ab\equiv (xy{)}^2$.

Также понятно про произведение вычета и невычета. Если $a\equiv x^2,ab\equiv y^2$, то $b\equiv {\left(\frac{y}{x}\right)}^2$, где $\frac{y}{x}=y{x}^{-1}$, а $x^{-1}$ обратный остаток к $x$.

Осталось доказать, что произведение двух невычетов является вычетом. Предположим противное. Пусть $c\equiv ab$. Для каждого $x$ существует единственный $y$ такой, что $xy\equiv c$. Поскольку $c$ не является вычетом все числа можно так разбить на пары. Но в каждой паре есть хотя бы один невычет из первого пункта доказательства, но в одной из пар два невычета, значит их больше половины, противоречие.

Мы доказали очень важное свойство, которое называется мультипликативностью.

Лемма. $\left(\begin{array}{c}a\\ p\end{array}\right)=a^{\frac{p-1}{2}}$.

Доказательство. Заметим, что если $a\equiv x^2$, то $a^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1$ по малой теореме Ферма, то есть для вычетов утверждение верно.

Можно было бы сказать, что многочлен $x^{\frac{p-1}{2}}-1$ имеет не более $\frac{p-1}{2}$ корней, потому что ${\mathbb{F}}_p$ – поле, но у этого факта есть более элементарное доказательство.

Проделаем тот же трюк, что и в доказательстве мультипликативности для двух невычетов. Тогда произведение всех чисел в парах с одной стороны равно $(p-1)!$, так как каждое число встречается ровно один раз, а с другой стороны $a^{\frac{p-1}{2}}$, но по теореме Вильсона $(p-1)!\equiv -1(\mathrm{mod}p)$.

Это знание, например, позволит нам определить когда $-1$ является вычетом, и, даже, если очень постараться, понять то же самое про $2$.

Лемма. $-1$ является вычетом тогда и только тогда, когда $p=4k+1$.

Доказательство. Примените формулу для символа Лежандра.

Лемма. $\left(\begin{array}{c}2\\ p\end{array}\right)=(-1{)}^{\frac{p^2-1}{8}}$.

Доказательство. Пусть $P=2\cdot 4\cdot \dots \cdot (p-1)$. Тогда $P\equiv 2^{\frac{p-1}{2}}\left(\frac{p-1}{2}\right)!\equiv \left(\begin{array}{c}2\\ p\end{array}\right)\left(\frac{p-1}{2}\right)!$

Сократим общие множители в сравнении и рассмотрим случаи.

Первый случай. $p=4k+1$. Получаем сравнение $$(2k+2)\cdot \dots \cdot 4k\equiv \left(\begin{array}{c}2\\ p\end{array}\right)\cdot 1\cdot 3\cdot \dots (2k-1)$$

Заметим, что $$(2k+2)\cdot \dots \cdot 4k\equiv (-1{)}^k\cdot 1\cdot 4\cdot \dots \cdot (2k-1)$$ Откуда $(-1{)}^k\equiv \left(\begin{array}{c}2\\ p\end{array}\right)$. Нетрудно проверить, что $k$ и $\frac{p^2-1}{8}$ имеют одинаковую четность, что и требовалось.

Второй случай. $p=4k+3$. Второй случай аналогичен и достается читателю в качестве простого и приятного упражнения.

Нахождение квадратного корня по модулю

Символ Лежандра числа $a$ можно найти за $O(\log p)$, возведя его в степень $\frac{p-1}{2}$. А можно ли найти квадратный корень числа по модулю?

Для начала попробуем найти квадратный корень $-1$, если $p=4k+1$. Пусть $a$ – невычет по модулю $p$, то $a^{\frac{p-1}{2}}\equiv -1$, а значит $a^{\frac{p-1}{4}}\equiv a^k$ это искомый корень. Перед нами встаёт задача о нахождении невычета по модулю $p$.

Лемма. Существует алгоритм, который находит невычет по модулю $p$ за ожидаемое время $O(\log p)$.

Доказательство. Будем брать случайное число от $1$ до $p-1$ включительно и проверять является ли оно невычетом, вычисляя символ Лежандра за $O(\log p)$. Поскольку невычетов ровно половина, вероятность того, что очередное число окажется невычетом равна $\frac{1}{2}$, а значит ожидаемое число шагов равно $2$.

Существование полиномиального, детерминированного и безусловного(не опирающегося на недоказанные факты) алгоритма является открытой проблемой. В предположении гипотезы Римана среди первых $O({\log }^{2}p)$ чисел есть невычет.

Лемма. Если $n$ является вычетом, то существует алгоритм, который за ожидаемое время $O(\log p)$ находит такое $a$, что $a^2-n$ является невычетом.

Доказательство. Если $n$ вычет, то $n=x^2$, а тогда $a^2-n=a^2-x^2=(a-x)(a+x)$. Воспользуемся мультипликативностью символа Лежандра, в предположении, что $a+x$ не равно нулю по модулю $p$.

$$\left(\begin{array}{c}{a}^2-n\\ p\end{array}\right)=\left(\begin{array}{c}(a-x)(a+x)\\ p\end{array}\right)=\left(\begin{array}{c}a-x\\ p\end{array}\right)\left(\begin{array}{c}a+x\\ p\end{array}\right)=\frac{\left(\begin{array}{c}a-x\\ p\end{array}\right)}{\left(\begin{array}{c}a+x\\ p\end{array}\right)}=\left(\begin{array}{c}{\displaystyle \frac{a-x}{a+x}}\\ p\end{array}\right)$$

Обозначим $f(a)={\displaystyle \frac{a-x}{a+x}}$. Пусть $f(a)\equiv f(b)$. Тогда $${\displaystyle \frac{a-x}{a+x}}\equiv {\displaystyle \frac{b-x}{b+x}}$$ $$(a-x)(b+x)\equiv (a+x)(b-x)$$ $$ab-bx+ax-x^2\equiv ab+bx-ax-x^2$$ $$(a-b)x\equiv (b-a)x$$

То есть $f(a)\equiv f(b)⟹a\equiv b$.

Поскольку $\left(\begin{array}{c}{a}^2-n\\ p\end{array}\right)=\left(\begin{array}{c}f(a)\\ p\end{array}\right)$, то вероятность того, что случайно выбранное $a$ окажется подходящим равна вероятности того, что $f(a)$ является невычетом. Но как было показано ранее, для разных аргументов $f$ возвращает разные значения, а значит $f$ равновероятно распределена между какими-то $p-1$ значениями.

Среди любых $p-1$ остатков хотя бы $\frac{p-1}{2}-1$ невычетов. Можно понять это так, мы берем все остатки, и исключаем из них один, а изначально невычетов $\frac{p-1}{2}$. Таким образом вероятность того, что $f(a)$ невычет не меньше $\frac{p-3}{2p-2}$.

То есть если мы будем выбирать $a$ случайно от 0 до $p$ невключительно, то ожидаемое количество шагов при $p>3$ ограничено константой. Можно убедиться, что при $p=3$ мы сможем найти такое $a$. Действительно, единственный вычет это $1$, то есть $n=1$. Тогда подходящее $a=0$.

Лемма. Существует алгоритм, который для вычета $n$ ищет такой $z$, что $z^2\equiv n(\mathrm{mod}p)$ за ожидаемое время $O(\log p)$.

Доказательство. Найдём такое $a$, что $a^2-n$ является невычетом за ожидаемое время $O(\log p)$. Обозначим за $\omega =\sqrt{a^2-n}$. Строго говоря, посмотрим на все многочлены в ${\mathbb{F}}_p$ от $\omega$. и посмотрим на них по модулю ${\omega }^2-(a^2-n)$. Получившееся множество $\{a+bw\mid a,b\leftarrow {\mathbb{F}}_p\}$ будем обозначать $T={\mathbb{F}}_p[w]/(w^2-(a^2-n))$.

Заметим, что числа из $T$ можно складывать и умножать: $$(a+bw)+(c+dw)=(a+c)+(b+d)w,(a+bw)(c+dw)=(ac+bd(a^2-n))+(ad+bc)w$$

Понятно, что сложение и умножение обладает всеми необходимыми свойствами(коммутативность, дистрибутивность, ассоциативность)

В качестве упражнения читателю остается проверить, что $T$ – поле. Из содержательных свойств надо проверить обратимость умножения.

Лемма. $(a+w{)}^{\frac{p+1}{2}}$ является искомым $z$, что в частности значит, что оно не имеет компоненту с $w$.

Доказательство. Посмотрим на $(a+w{)}^{p+1}$. Заметим, что $(a+w{)}^p=a^p+w^p$. Действительно, если раскрыть скобки по биному Ньютона, то все остальные члены будут делиться на $p$. Также $w^p=-w$, поскольку $w^{p-1}=(a^2-n{)}^{\frac{p-1}{2}}=-1$, в силу того, что $a^2-n$ невычет. Тогда

$$(a+w{)}^{p+1}=(a^p+w^p)(a+w)=(a-w)(a+w)=a^2-w^2=a^2-(a^2-n)=n$$

Поскольку читатель проверил, что $T$ является полем, многочлен $x^2-n$ имеет в нем не более двух корней. Но мы знаем, что $z$ и $-z$ являются его корнями. В то же время ${((a+w{)}^{\frac{p+1}{2}})}^2-n=0$, значит оно и есть искомое $z$.

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

1. Найти такое $a$, что $a^2-n$ является невычетом методом проб и ошибок
2. Возвести $(a+w)$ в степень $\frac{p+1}{2}$ быстрым возведением в степень, где $w=\sqrt{a^2-n}$, это и будет результатом.

Разложение в сумму двух квадратов

Наша цель, понять, для каких $n$ существуют $a,b$, такие, что $a^2+b^2=n$, и как их оптимально искать.

Для начала попробуем решить задачу для простого $p$. Сразу понятно, что если $p=4k+3$, то разложить в сумму двух квадратов не удастся, можно даже доказать более сильное утверждение.

Лемма Жирара. Если $a^2+b^2\equiv 0(\mathrm{mod}p)$, где $p$ простое число вида $4k+3$, то $p\mid a,b$.

Доказательство. $a^2\equiv -b^2(\mathrm{mod}p)$. Возьмём символ лежандра от обоих частей и воспользуемся мультипликативностью.

$$\left(\begin{array}{c}{a}^2\\ p\end{array}\right)=[\left(\begin{array}{c}{a}^2\\ p\end{array}\right)=\left(\begin{array}{c}-b^2\\ p\end{array}\right)]=\left(\begin{array}{c}-1\\ p\end{array}\right)\left(\begin{array}{c}{b}^2\\ p\end{array}\right)=-1\left(\begin{array}{c}{b}^2\\ p\end{array}\right)$$

Последнее равенство в силу того, что $p=4k+3$. Но тогда $\left(\begin{array}{c}{a}^2\\ p\end{array}\right)=\left(\begin{array}{c}{b}^2\\ p\end{array}\right)=0$, что и требовалось.

Лемма. Любое простое $p$ вида $4k+1$ представляется в виде суммы двух квадратов.

Попробуем конструктивно научиться искать разложение для $p=4k+1$. Для начала поймем как “перемножать” такие разложения, это также поможет нам далее, когда мы перейдем в составному $n$.

Пусть $a^2+b^2=x,c^2+d^2=y$. Тогда $$a^2{c}^2+a^2{d}^2+b^2{c}^2+b^2{d}^2=xy$$ $$(ac{)}^2+(ad{)}^2+(bc{)}^2+(bd{)}^2=xy$$ $$(ac{)}^2+(bd{)}^2+2abcd+(ad{)}^2+(bc{)}^2-2abcd=xy$$ $$(ac+bd{)}^2+(ad-bc{)}^2=xy$$

То же самое можно увидеть, если рассмотреть $z=a+bi,w=c+di$, тогда $\text{conj}zw=(ac+bd)+(ad-bc)i$, а $xy=|z{|}^2|w{|}^2=|\text{conj}z{|}^2|w{|}^2=|\text{conj}zw{|}^2|$.

То есть мы доказали, что если $x,y$ представимы в виде суммы двух квадратов, то $xy$ тоже представимо в виде суммы двух квадратов.

Попробуем представить число $p$, пользуясь предыдущим знанием. Пусть для начала у нас есть разбиение числа $mp$ для какого-то $m$, то есть $a^2+b^2=mp$.

Определение. Абсолютно наименьшим вычетом числа $a$ по модулю $m$ называется наименьшее по абсолютному значению $b$ такое, что $a\equiv b(\mathrm{mod}m)$.

Пусть $c,d$ абсолютно наименьшие вычеты чисел $a,b$ по модулю $m$. Тогда $c^2+d^2=mk$ и $k⩽\frac{m}{2}$.

Тогда мы можем представить $m^{2}pk=(ac+bd{)}^2+(ad-bc{)}^2$. Остается только заметить, что $ad-bc$ и $ac+bd$ делятся на $m$. Действительно, $ad-bc\equiv ab-ab\equiv 0(\mathrm{mod}m)$ и $ac+bd\equiv a^2+b^2\equiv 0(\mathrm{mod}m)$. $$pk={\left({\displaystyle \frac{ad-bc}{m}}\right)}^2+{\left({\displaystyle \frac{ac+bd}{m}}\right)}^2$$

Если мы будем повторять эту процедуру, то на каждом шаге $m$ будет уменьшаться хотя бы в два раза, а значит когда-то станет единицей, и мы получим требуемое разбиение.

Тем самым мы не только доказали лемму, но и нашли эффективный алгоритм нахождения такого разложения.

Анализ алгоритма

В качестве начального разбиения можно взять $a=1,b=z$, где $z^2\equiv -1(\mathrm{mod}p)$. Найти $z$ можно за $O(\log p)$. Далее мы делаем $O(\log p)$ шагов, так как начальное $m$ не превосходит $p$, на каждом шаге делаем константное число операций.

Итого за $O(\log p)$ времени и $O(1)$ дополнительной памяти мы умеем искать разложение $p$ в сумму двух квадратов.

Составное $n$

Самое интересное происходит в случае составного $n$. Оказывается верно следующее.

Рождественская теорема Ферма. Число $n$ можно представить в виде суммы двух квадратов тогда и только тогда, когда каждое простое $p$ вида $4k+3$ входит в разложение $n$ в четной степени.

В одну сторону мы уже умеем доказывать и находить разбиение. Действительно $2=1^2+1^2,p^2=0^2+p^2$. Для простых вида $4k+1$ мы умеем находить разбиение, а ещё мы умеем перемножать два существующих.

Лемма. Для любого простого $p$ вида $4k+3$ его степень вхождения в $a^2+b^2$ чётна.

Доказательство. Если $a^2+b^2$ не делится на $p$, то утверждение очевидно. Иначе воспользуемся леммой Жирара, получим что $p\mid a,b$. Тода $p^2\mid a^2+b^2$ и ${\left(\frac{a}{p}\right)}^2+{\left(\frac{b}{p}\right)}^2=\frac{a^2+b^2}{p^2}$. Применяя то же самое рассуждение получаем требуемое.

Тем самым мы доказали рождественскую теорему Ферма и научились раскладывать числа в суммы двух квадратов.