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

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

Будем обозначать множество остатков по модулю p со сложением и умножением как Fp.

Будем считать, что арифметические операции в Fp работают за константое время или что то же самое, мерять все в арифметических операциях(сложение, умножение, вычитание).

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

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

Определение. aFp называется квадратичным вычетом если существует такое z, что z2a(modp), а иначе невычетом.

Определение. Символом Лежандра числа a называется величина (ap), равная единице, если a является квадратичным вычетом по модулю p, нулю если a0, и 1 иначе.

Лемма. В Fp поровну квадратичных вычетов и невычетов, а именно p12.

Доказательство. Посмотрим на числа 12,22,,(p1)2. Заметим, что a2b2 равносильно тому что p(ab)(a+b), то есть либо ab, либо ab. А это значит, что среди первых p12 квадратов нет повторяющихся, а поскольку a2(pa)2, то это все квадраты, что и требовалось.

Лемма. (abp)=(ap)(bp).

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

Очевидно, что произведение двух вычетов является вычетом. ax2,by2, значит ab(xy)2.

Также понятно про произведение вычета и невычета. Если ax2,aby2, то b(yx)2, где yx=yx1, а x1 обратный остаток к x.

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

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

Лемма. (ap)=ap12.

Доказательство. Заметим, что если ax2, то ap12xp11 по малой теореме Ферма, то есть для вычетов утверждение верно.

Можно было бы сказать, что многочлен xp121 имеет не более p12 корней, потому что Fp – поле, но у этого факта есть более элементарное доказательство.

Проделаем тот же трюк, что и в доказательстве мультипликативности для двух невычетов. Тогда произведение всех чисел в парах с одной стороны равно (p1)!, так как каждое число встречается ровно один раз, а с другой стороны ap12, но по теореме Вильсона (p1)!1(modp).

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

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

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

Лемма. (2p)=(1)p218.

Доказательство. Пусть P=24(p1). Тогда P2p12(p12)!(2p)(p12)!

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

Первый случай. p=4k+1. Получаем сравнение (2k+2)4k(2p)13(2k1)

Заметим, что (2k+2)4k(1)k14(2k1) Откуда (1)k(2p). Нетрудно проверить, что k и p218 имеют одинаковую четность, что и требовалось.

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

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

Символ Лежандра числа a можно найти за O(logp), возведя его в степень p12. А можно ли найти квадратный корень числа по модулю?

Для начала попробуем найти квадратный корень 1, если p=4k+1. Пусть a – невычет по модулю p, то ap121, а значит ap14ak это искомый корень. Перед нами встаёт задача о нахождении невычета по модулю p.

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

Доказательство. Будем брать случайное число от 1 до p1 включительно и проверять является ли оно невычетом, вычисляя символ Лежандра за O(logp). Поскольку невычетов ровно половина, вероятность того, что очередное число окажется невычетом равна 12, а значит ожидаемое число шагов равно 2.

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

Лемма. Если n является вычетом, то существует алгоритм, который за ожидаемое время O(logp) находит такое a, что a2n является невычетом.

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

(a2np)=((ax)(a+x)p)=(axp)(a+xp)=(axp)(a+xp)=(axa+xp)

Обозначим f(a)=axa+x. Пусть f(a)f(b). Тогда axa+xbxb+x (ax)(b+x)(a+x)(bx) abbx+axx2ab+bxaxx2 (ab)x(ba)x

То есть f(a)f(b)ab.

Поскольку (a2np)=(f(a)p), то вероятность того, что случайно выбранное a окажется подходящим равна вероятности того, что f(a) является невычетом. Но как было показано ранее, для разных аргументов f возвращает разные значения, а значит f равновероятно распределена между какими-то p1 значениями.

Среди любых p1 остатков хотя бы p121 невычетов. Можно понять это так, мы берем все остатки, и исключаем из них один, а изначально невычетов p12. Таким образом вероятность того, что f(a) невычет не меньше p32p2.

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

Лемма. Существует алгоритм, который для вычета n ищет такой z, что z2n(modp) за ожидаемое время O(logp).

Доказательство. Найдём такое a, что a2n является невычетом за ожидаемое время O(logp). Обозначим за ω=a2n. Строго говоря, посмотрим на все многочлены в Fp от ω. и посмотрим на них по модулю ω2(a2n). Получившееся множество {a+bwa,bFp} будем обозначать T=Fp[w]/(w2(a2n)).

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

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

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

Лемма. (a+w)p+12 является искомым z, что в частности значит, что оно не имеет компоненту с w.

Доказательство. Посмотрим на (a+w)p+1. Заметим, что (a+w)p=ap+wp. Действительно, если раскрыть скобки по биному Ньютона, то все остальные члены будут делиться на p. Также wp=w, поскольку wp1=(a2n)p12=1, в силу того, что a2n невычет. Тогда

(a+w)p+1=(ap+wp)(a+w)=(aw)(a+w)=a2w2=a2(a2n)=n

Поскольку читатель проверил, что T является полем, многочлен x2n имеет в нем не более двух корней. Но мы знаем, что z и z являются его корнями. В то же время ((a+w)p+12)2n=0, значит оно и есть искомое z.

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

  1. Найти такое a, что a2n является невычетом методом проб и ошибок
  2. Возвести (a+w) в степень p+12 быстрым возведением в степень, где w=a2n, это и будет результатом.

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

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

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

Лемма Жирара. Если a2+b20(modp), где p простое число вида 4k+3, то pa,b.

Доказательство. a2b2(modp). Возьмём символ лежандра от обоих частей и воспользуемся мультипликативностью.

(a2p)=[(a2p)=(b2p)]=(1p)(b2p)=1(b2p)

Последнее равенство в силу того, что p=4k+3. Но тогда (a2p)=(b2p)=0, что и требовалось.

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

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

Пусть a2+b2=x,c2+d2=y. Тогда a2c2+a2d2+b2c2+b2d2=xy (ac)2+(ad)2+(bc)2+(bd)2=xy (ac)2+(bd)2+2abcd+(ad)2+(bc)22abcd=xy (ac+bd)2+(adbc)2=xy

То же самое можно увидеть, если рассмотреть z=a+bi,w=c+di, тогда \conjzw=(ac+bd)+(adbc)i, а xy=|z|2|w|2=|\conjz|2|w|2=|\conjzw|2|.

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

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

Определение. Абсолютно наименьшим вычетом числа a по модулю m называется наименьшее по абсолютному значению b такое, что ab(modm).

Пусть c,d абсолютно наименьшие вычеты чисел a,b по модулю m. Тогда c2+d2=mk и km2.

Тогда мы можем представить m2pk=(ac+bd)2+(adbc)2. Остается только заметить, что adbc и ac+bd делятся на m. Действительно, adbcabab0(modm) и ac+bda2+b20(modm). pk=(adbcm)2+(ac+bdm)2

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

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

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

В качестве начального разбиения можно взять a=1,b=z, где z21(modp). Найти z можно за O(logp). Далее мы делаем O(logp) шагов, так как начальное m не превосходит p, на каждом шаге делаем константное число операций.

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

Составное n

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

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

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

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

Доказательство. Если a2+b2 не делится на p, то утверждение очевидно. Иначе воспользуемся леммой Жирара, получим что pa,b. Тода p2a2+b2 и (ap)2+(bp)2=a2+b2p2. Применяя то же самое рассуждение получаем требуемое.

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