Квадратичный остаток

В теории чисел целое число q называется квадратичным вычетом по модулю n, если оно конгруэнтно совершенному квадрату по модулю n ; т. е. если существует целое число x такое, что:

$x^{2}\equiv q{\pmod {n}}.$

В противном случае q называется квадратичным невычетом по модулю n .

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

История, условности и элементарные факты

Ферма , Эйлер , Лагранж , Лежандр и другие теоретики чисел 17 и 18 веков установили теоремы. и высказал предположения о квадратичных вычетах, но первое систематическое рассмотрение содержится в § IV ( Гаусса «Disquisitiones Arithmeticae» 1801). В статье 95 вводятся термины «квадратичный остаток» и «квадратичный невычет» и говорится, что, если из контекста становится ясно, прилагательное «квадратичный» может быть опущено.

Для данного n список квадратичных вычетов по модулю n можно получить, просто возведя в квадрат все числа 0, 1, ..., n − 1 . Поскольку a ≡ b (mod n ) влечет за собой a ² ≡ b ² (mod n ), любой другой квадратичный вычет конгруэнтен (mod n ) какому-либо из полученного списка. Но полученный список состоит не только из взаимно несовпадающих квадратичных вычетов (по модулю n). Поскольку ​ ² ≡( п - а ) ² (mod n ), список, полученный возведением в квадрат всех чисел в списке 1, 2, ..., n − 1 (или в списке 0, 1, ..., n ), симметричен (mod n ) вокруг своей средней точки. , следовательно, на самом деле нужно только возвести в квадрат все числа в списке 0, 1, ..., $\lfloor$ н /2 $\rfloor$. Полученный таким образом список может по-прежнему содержать взаимно конгруэнтные числа (по модулю n ). Таким образом, число несовпадающих друг с другом квадратичных вычетов по модулю n не может превышать n /2 + 1 ( n четное) или ( n + 1)/2 ( n нечетное).

Произведение двух остатков всегда является остатком.

Главный модуль

По модулю 2 каждое целое число является квадратичным вычетом.

По модулю нечетного простого числа p существует ( p + 1)/2 остатков (включая 0) и ( p − 1)/2 невычетов по критерию Эйлера . В этом случае принято рассматривать 0 как частный случай и работать внутри мультипликативной группы ненулевых поля элементов $(\mathbb {Z} /p\mathbb {Z} )$. (Другими словами, каждый класс конгруэнтности, кроме нуля по модулю p, имеет мультипликативный обратный. Это неверно для составных модулей.)

Следуя этому соглашению, мультипликативный обратный остаток является остатком, а обратный невычету является невычетом.

Следуя этому соглашению, по модулю нечетного простого числа имеется одинаковое количество остатков и невычетов.

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

Первое дополнение Согласно закону квадратичной взаимности , если p ≡ 1 (mod 4), то −1 является квадратичным вычетом по модулю p , а если p ≡ 3 (mod 4), то −1 является невычетом по модулю p . Это подразумевает следующее:

Если p ≡ 1 (mod 4), отрицательный результат остатка по модулю p является остатком, а отрицательный результат невычета является невычетом.

Если p ≡ 3 (mod 4), отрицательный остаток по модулю p является невычетом, а отрицательный результат невычета является остатком.

Основной модуль мощности

Все нечетные квадраты равны ≡ 1 (по модулю 8) и, следовательно, также ≡ 1 (по модулю 4). Если a — нечетное число и m = 8, 16 или некоторая высшая степень 2, то a — вычет по модулю m тогда и только тогда, когда a ≡ 1 (mod 8).

Например, по модулю (32) нечетные квадраты равны

1 ² ≡ 15 ² ≡ 1

3 ² ≡ 13 ² ≡ 9

5 ² ≡ 11 ² ≡ 25

7 ² ≡ 9 ² ≡ 49 ≡ 17

и четные

0 ² ≡ 8 ² ≡ 16 ² ≡ 0

2 ² ≡ 6 ² ≡ 10 ² ≡ 14 ² ≡ 4

4 ² ≡ 12 ² ≡ 16.

Таким образом, ненулевое число является остатком по модулю 8, 16 и т. д. тогда и только тогда, когда оно имеет вид 4. ^к ( 8н +1).

Число, относительно простое по отношению к нечетному простому числу p, является остатком по модулю любой степени p тогда и только тогда, когда оно является остатком по модулю p .

Если модуль равен p ^н ,

тогда п ^к а

является остатком по модулю p ^н если k ≥ n

является безвычетом по модулю p ^н если k < n нечетно

является остатком по модулю p ^н если k < n четно и a является остатком

является безвычетом по модулю p ^н если k < n четно и a не вычет.

Обратите внимание, что правила различаются для степеней двойки и степеней нечетных простых чисел.

По модулю нечетной степени простого числа n = p ^к , произведения остатков и невычетов, относительно простых с p, подчиняются тем же правилам, что и по модулю p ; p является невычетом, и, как правило, все остатки и невычеты подчиняются одним и тем же правилам, за исключением того, что произведения будут равны нулю, если степень p в произведении ≥ n .

По модулю 8 произведение невычетов 3 и 5 является невычетом 7, и аналогично для перестановок 3, 5 и 7. Фактически, мультипликативная группа невычетов и 1 образует четырехгруппу Клейна .

Составной модуль не является простой степенью

Основным фактом в данном случае является

если a — вычет по модулю n , то a — вычет по модулю p ^к для каждой простой степени, делящей n .

если a — невычет по модулю n , то a — невычет по модулю p ^к для хотя бы одной простой степени, делящей n .

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

Например, из таблицы для модуля 6  1 , 2, 3 , 4 , 5 (остатки выделены жирным шрифтом ).

Продуктом остатка 3 и неостатка 5 является остаток 3, тогда как продуктом остатка 4 и неостатка 2 является неостаток 2.

Кроме того, произведение двух невычетов может быть остатком, неостатком или нулем.

Например, из таблицы для модуля 15  1 , 2, 3, 4 , 5, 6 , 7, 8, 9 , 10 , 11, 12, 13, 14 (остатки выделены жирным шрифтом ).

Произведением неостатков 2 и 8 является остаток 1, тогда как произведением неостатков 2 и 7 является неостаток 14.

Это явление лучше всего можно описать, используя словарь абстрактной алгебры. Классы сравнения, относительно простые по модулю, представляют собой группу при умножении, называемую группой единиц кольца . $(\mathbb {Z} /n\mathbb {Z} )$, а квадраты являются подгруппой его . Разные невычеты могут принадлежать разным смежным классам , и не существует простого правила, предсказывающего, в каком из них будет находиться их произведение. По модулю простого числа существует только подгруппа квадратов и один смежный класс.

Тот факт, что, например, по модулю 15 произведение неостатков 3 и 5, или неостатка 5 и остатка 9, или двух остатков 9 и 10 равно нулю, является результатом работы в полном кольце. $(\mathbb {Z} /n\mathbb {Z} )$, который имеет делители нуля для составного n .

По этой причине некоторые авторы добавьте к определению, что квадратичный вычет a должен быть не только квадратом, но также должен быть взаимно простым с модулем n . ( a взаимно просто с n тогда и только тогда, когда a ² взаимно просто с n .)

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

Обозначения

Гаусс использовали R и N для обозначения невязкости и неостаточности соответственно;

например, 2 R 7 и 5 N 7 или 1 R 8 и 3 N 8 .

Хотя это обозначение компактно и удобно для некоторых целей, более полезным обозначением является символ Лежандра , также называемый квадратичным символом , который определяется для всех целых чисел a и положительных нечетных простых чисел p как

$\left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{ if }}p{\text{ divides }}a\\+1&{\text{ if }}a\operatorname {R} p{\text{ and }}p{\text{ does not divide }}a\\-1&{\text{ if }}a\operatorname {N} p{\text{ and }}p{\text{ does not divide }}a\end{cases}}$

Есть две причины, по которым числа ≡ 0 (mod p ) рассматриваются особым образом. Как мы видели, это облегчает формулировку многих формул и теорем. Другая (связанная с этим) причина заключается в том, что квадратичный характер является гомоморфизмом мультипликативной группы ненулевых классов конгруэнтности по модулю p в комплексные числа при умножении. Параметр $({\tfrac {np}{p}})=0$ позволяет свою область определения расширить до мультипликативной полугруппы всех целых чисел.

Одним из преимуществ этого обозначения перед обозначением Гаусса является то, что символ Лежандра представляет собой функцию, которую можно использовать в формулах. Его также можно легко обобщить на вычеты кубической , четвертой и более высокой степени.

Существует обобщение символа Лежандра для составных значений p — символ Якоби , но его свойства не так просты: если m составное и символ Якоби $({\tfrac {a}{m}})=-1,$ тогда a N m , а если a R m , то $({\tfrac {a}{m}})=1,$ но если $({\tfrac {a}{m}})=1$ мы не знаем это Rm , или Nm является ли . Например: $({\tfrac {2}{15}})=1$ и $({\tfrac {4}{15}})=1$, но 2 N 15 и 4 R 15 . Если m простое число, символы Якоби и Лежандра совпадают.

Распределение квадратичных вычетов

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

Используя теорему Дирихле о простых числах в арифметических прогрессиях , закон квадратичной взаимности и китайскую теорему об остатках (КТО), легко увидеть, что для любого M > 0 существуют простые числа p такие, что числа 1, 2, ..., M — все остатки по модулю p .

Например, если p ≡ 1 (mod 8), (mod 12), (mod 5) и (mod 28), то по закону квадратичной взаимности 2, 3, 5 и 7 все будут остатками по модулю p , и таким образом, будут все цифры 1–10. ЭЛТ утверждает, что это то же самое, что p ≡ 1 (mod 840), а теорема Дирихле утверждает, что существует бесконечное количество простых чисел этой формы. 2521 самый маленький, да и вообще 1 ² ≡ 1, 1046 ² ≡ 2, 123 ² ≡ 3, 2 ² ≡ 4, 643 ² ≡ 5, 87 ² ≡ 6, 668 ² ≡ 7, 429 ² ≡ 8, 3 ² ≡ 9 и 529 ² ≡ 10 (против 2521).

Формулы Дирихле

Первая из этих закономерностей вытекает из Питера Густава Лежена Дирихле работы (1830-е годы) над аналитической формулой для числа классов бинарных квадратичных форм . Пусть q — простое число, s — комплексная переменная, и определим L-функцию Дирихле как

$L(s)=\sum _{n=1}^{\infty }\left({\frac {n}{q}}\right)n^{-s}.$

Дирихле показал, что если q ≡ 3 (mod 4), то

$L(1)=-{\frac {\pi }{\sqrt {q}}}\sum _{n=1}^{q-1}{\frac {n}{q}}\left({\frac {n}{q}}\right)>0.$

Следовательно, в этом случае (простое q ≡ 3 (mod 4)) сумма квадратичных вычетов за вычетом суммы невычетов в диапазоне 1, 2, ..., q - 1 является отрицательным числом.

Например, по модулю 11,

1 , 2, 3 , 4 , 5 , 6, 7, 8, 9 , 10 (остатки выделены жирным шрифтом )

1 + 4 + 9 + 5 + 3 = 22, 2 + 6 + 7 + 8 + 10 = 33, а разница равна −11.

Фактически разница всегда будет нечетным кратным q, если q > 3. Напротив, для простого числа q ≡ 1 (mod 4) сумма квадратичных вычетов за вычетом суммы невычетов в диапазоне 1, 2, ..., q - 1 равна нулю, а это означает, что обе суммы равны ${\frac {q(q-1)}{4}}$.

Дирихле также доказал, что для простого числа q ≡ 3 (mod 4)

$L(1)={\frac {\pi }{\left(2-\left({\frac {2}{q}}\right)\right)\!{\sqrt {q}}}}\sum _{n=1}^{\frac {q-1}{2}}\left({\frac {n}{q}}\right)>0.$

квадратичных вычетов больше, чем невычетов Это означает, что среди чисел 1, 2, ..., ( q − 1)/2 .

Например, по модулю 11 имеется четыре остатка меньше 6 (а именно 1, 3, 4 и 5), но только один неостаток (2).

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

Закон квадратичной взаимности

Основная статья: квадратичная взаимность

Если p и q — нечетные простые числа, то:

(( p — квадратичный вычет по модулю q ) тогда и только тогда, когда ( q — квадратичный вычет по модулю p )) тогда и только тогда, когда (хотя бы один из p и q конгруэнтен 1 по модулю 4).

То есть:

$\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}$

где $\left({\frac {p}{q}}\right)$ — это символ Лежандра .

Таким образом, для чисел a и нечетных простых чисел p , которые не делят a :

а	a является квадратичным вычетом по модулю p тогда и только тогда, когда	а	a является квадратичным вычетом по модулю p тогда и только тогда, когда
1	(каждое простое число p )	−1	р ≡ 1 (по модулю 4)
2	р ≡ 1, 7 (против 8)	−2	р ≡ 1, 3 (против 8)
3	р ≡ 1, 11 (против 12)	−3	р ≡ 1 (по модулю 3)
4	(каждое простое число p )	−4	р ≡ 1 (по модулю 4)
5	р ≡ 1, 4 (против 5)	−5	р ≡ 1, 3, 7, 9 (по модулю 20)
6	р ≡ 1, 5, 19, 23 (против 24)	−6	р ≡ 1, 5, 7, 11 (по модулю 24)
7	р ≡ 1, 3, 9, 19, 25, 27 (против 28)	−7	р ≡ 1, 2, 4 (по модулю 7)
8	р ≡ 1, 7 (против 8)	−8	р ≡ 1, 3 (против 8)
9	(каждое простое число p )	−9	р ≡ 1 (по модулю 4)
10	р ≡ 1, 3, 9, 13, 27, 31, 37, 39 (против 40)	−10	р ≡ 1, 7, 9, 11, 13, 19, 23, 37 (против 40)
11	р ≡ 1, 5, 7, 9, 19, 25, 35, 37, 39, 43 (против 44)	−11	р ≡ 1, 3, 4, 5, 9 (против 11)
12	р ≡ 1, 11 (против 12)	−12	р ≡ 1 (по модулю 3)

Пары остатков и неостатков

По модулю простого числа p количество пар n , n + 1, где n R p и n + 1 R p или n N p и n + 1 R p и т. д., почти одинаково. Точнее, пусть p — нечетное простое число. Для i , j = 0, 1 определим множества

$A_{ij}=\left\{k\in \{1,2,\dots ,p-2\}:\left({\frac {k}{p}}\right)=(-1)^{i}\land \left({\frac {k+1}{p}}\right)=(-1)^{j}\right\},$

и пусть

$\alpha _{ij}=|A_{ij}|.$

То есть,

α ₀₀ — количество остатков, за которыми следует остаток,

α ₀₁ — количество остатков, за которыми следует неостаток,

α ₁₀ представляет собой количество неостатков, за которыми следует остаток, и

α ₁₁ представляет собой количество невычетов, за которыми следует невычет.

Тогда если p ≡ 1 (mod 4)

$\alpha _{00}={\frac {p-5}{4}},\;\alpha _{01}=\alpha _{10}=\alpha _{11}={\frac {p-1}{4}}$

и если p ≡ 3 (mod 4)

$\alpha _{01}={\frac {p+1}{4}},\;\alpha _{00}=\alpha _{10}=\alpha _{11}={\frac {p-3}{4}}.$

Например: (остатки выделены жирным шрифтом )

Модуль 17

1 , 2 , 3, 4 , 5, 6, 7, 8 , 9 , 10, 11, 12, 13 , 14, 15 , 16

А ₀₀ = {1,8,15},

А ₀₁ = {2,4,9,13},

A ₁₀ = {3,7,12,14},

И ₁₁ = {5,6,10,11}.

Модуль 19

1 , 2, 3, 4 , 5 , 6 , 7 , 8, 9 , 10, 11 , 12, 13, 14, 15, 16 , 17 , 18

А ₀₀ = {4,5,6,16},

А ₀₁ = {1,7,9,11,17},

A ₁₀ = {3,8,10,15},

И ₁₁ = {2,12,13,14}.

Гаусс (1828) ввел этот вид счета, когда доказал, что если p ≡ 1 (mod 4), то x ⁴ ≡ 2 (mod p ) можно решить тогда и только тогда, когда p = a ² + 64 б ² .

Неравенство Полиа–Виноградова

Значения $({\tfrac {a}{p}})$ для последовательных значений подбрасывание имитировать случайную величину, например, монеты . В частности, Поля и Виноградов провели (независимо) в 1918 году, что для любого неглавного характера Дирихле χ( n ) по модулю q и любых целых чисел M и N ,

$\left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log q\right),$

в большой записи О. Параметр

$\chi (n)=\left({\frac {n}{q}}\right),$

это показывает, что количество квадратичных вычетов по модулю q в любом интервале длины N равно

${\frac {1}{2}}N+O({\sqrt {q}}\log q).$

Это легко чтобы доказать это

$\left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\sqrt {q}}\log q.$

Фактически,

$\left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\frac {4}{\pi ^{2}}}{\sqrt {q}}\log q+0.41{\sqrt {q}}+0.61.$

Монтгомери и Воган улучшили это утверждение в 1977 году, показав, что если обобщенная гипотеза Римана верна, то

$\left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log \log q\right).$

Этот результат невозможно существенно улучшить, поскольку в 1918 г. Шур доказал, что

$\max _{N}\left|\sum _{n=1}^{N}\left({\frac {n}{q}}\right)\right|>{\frac {1}{2\pi }}{\sqrt {q}}$

и Пейли доказали в 1932 году, что

$\max _{N}\left|\sum _{n=1}^{N}\left({\frac {d}{n}}\right)\right|>{\frac {1}{7}}{\sqrt {d}}\log \log d$

для бесконечного числа d > 0.

Наименьший квадратичный невычет

Наименьший квадратичный вычет по модулю p, очевидно, равен 1. Вопрос о величине наименьшего квадратичного невычета n ( p ) более тонкий, но он всегда простой, причем 7 впервые появляется в 71.

Неравенство Полиа – Виноградова, приведенное выше, дает O( √ p log p ).

Наилучшая безусловная оценка — это n ( p ) ≪ p ^я для любого θ>1/4 √ e , полученного с помощью оценок Бёрджесса на суммах характеров .

Приняв обобщенную гипотезу Римана , Анкени получил n ( p ) ≪ (log p ) ² .

Линник показал, что число p меньше X таких, что n ( p ) > X ^е ограничено константой, зависящей от ε.

Наименьшие квадратичные невычеты по модулю p для нечетных простых чисел p :

2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ... (последовательность A053760 в OEIS )

Квадратичный избыток

Пусть p — нечетное простое число. Квадратичный избыток E ( p ) — это количество квадратичных остатков в диапазоне (0, p /2) минус число в диапазоне ( p /2, p ) (последовательность A178153 в OEIS ). Для p, конгруэнтного 1 по модулю 4, избыток равен нулю, поскольку −1 является квадратичным вычетом, а вычеты симметричны относительно r ↔ p − r . Для p, соответствующего 3 mod 4, избыток E всегда положителен.

Сложность поиска квадратных корней

То есть, учитывая число a и модуль n , насколько это сложно

1. чтобы сказать, x ли решает ² ≡ a (mod n ) существует
2. предполагая, что он существует, чтобы вычислить его?

Здесь проявляется важная разница между простыми и составными модулями. По модулю простого числа p квадратичный вычет a имеет 1 + ( a | p ) корней (т.е. ноль, если a N p , один, если a ≡ 0 (mod p ), или два, если a R p и gcd( a,p ) = 1.)

В общем случае, если составной модуль n записан как произведение степеней различных простых чисел и имеется n ₁ корней по модулю первого, n ₂ по модулю второго, ..., будет n ₁ n ₂ ... корней. по модулю н .

Теоретический способ объединения решений по модулю простых чисел для получения решений по модулю n называется китайской теоремой об остатках ; это может быть реализовано с помощью эффективного алгоритма.

Например:

Решите х ² ≡ 6 (против 15).

х ² ≡ 6 (по модулю 3) имеет одно решение, 0; х ² ≡ 6 (по модулю 5) имеет два, 1 и 4.

и есть два решения по модулю 15, а именно 6 и 9.

Решите х ² ≡ 4 (против 15).

х ² ≡ 4 (mod 3) имеет два решения: 1 и 2; х ² ≡ 4 (по модулю 5) имеет два, 2 и 3.

и существует четыре решения по модулю 15, а именно 2, 7, 8 и 13.

Решите х ² ≡ 7 (против 15).

х ² ≡ 7 (по модулю 3) имеет два решения: 1 и 2; х ² ≡ 7 (по модулю 5) не имеет решений.

и решений по модулю 15 нет.

Простой или простой модуль мощности

Во-первых, если модуль n является простым, то символ Лежандра $\left({\frac {a}{n}}\right)$ можно быстро вычислить, используя вариант алгоритма Евклида. или критерий Эйлера . Если это -1, то решения нет.Во-вторых, если предположить, что $\left({\frac {a}{n}}\right)=1$, если n ≡ 3 (mod 4), Лагранж обнаружил, что решения имеют вид

$x\equiv \pm \;a^{(n+1)/4}{\pmod {n}},$

и Лежандр нашли похожее решение если n ≡ 5 (по модулю 8):

$x\equiv {\begin{cases}\pm \;a^{(n+3)/8}{\pmod {n}}&{\text{ if }}a{\text{ is a quartic residue modulo }}n\\\pm \;a^{(n+3)/8}2^{(n-1)/4}{\pmod {n}}&{\text{ if }}a{\text{ is a quartic non-residue modulo }}n\end{cases}}$

Однако для простого числа n ≡ 1 (mod 8) известной формулы не существует. Тонелли (в 1891 г.) и Чиполла нашел эффективные алгоритмы, работающие для всех простых модулей. Оба алгоритма требуют нахождения квадратичного невычета по модулю n , и для этого не существует эффективного детерминированного алгоритма. Но поскольку половина чисел от 1 до n не являются вычетами, выбор чисел x и вычисление символа Лежандра случайный $\left({\frac {x}{n}}\right)$ до тех пор, пока не будет найден неостаток, он быстро образуется. Небольшим вариантом этого алгоритма является алгоритм Тонелли-Шенкса .

Если модуль n является простой степенью n = p ^и , решение можно найти по модулю p и «поднять» до решения по модулю n, используя лемму Гензеля или алгоритм Гаусса.

Композитный модуль

Если модуль n был разложен на простые степени, решение обсуждалось выше.

Если n не соответствует 2 по модулю 4 и символу Кронекера $\left({\tfrac {a}{n}}\right)=-1$ тогда решения нет; если n конгруэнтно 2 по модулю 4 и $\left({\tfrac {a}{n/2}}\right)=-1$, то решения также нет. Если n не соответствует 2 по модулю 4 и $\left({\tfrac {a}{n}}\right)=1$, или n конгруэнтно 2 по модулю 4 и $\left({\tfrac {a}{n/2}}\right)=1$, может быть, а может и не быть.

Если полная факторизация n неизвестна и $\left({\tfrac {a}{n}}\right)=1$ и n не конгруэнтно 2 по модулю 4, или n конгруэнтно 2 по модулю 4 и $\left({\tfrac {a}{n/2}}\right)=1$ как известно, эквивалентна целочисленной факторизации n , проблема , (т.е. эффективное решение любой проблемы может быть использовано для эффективного решения другой).

Приведенное выше обсуждение показывает, как знание факторов n позволяет нам эффективно находить корни. Допустим, существует эффективный алгоритм поиска квадратных корней по модулю составного числа. В статье « Сопоставление квадратов» обсуждается, как найти два числа x и y, где x ² ≡ и ² (mod n ) и x ≠ ± y достаточно для эффективной факторизации n . Сгенерируйте случайное число, возведите его в квадрат по модулю n и используйте эффективный алгоритм квадратного корня, чтобы найти корень. Повторяйте, пока он не вернет число, не равное тому, которое мы первоначально возвели в квадрат (или его отрицательное значение по модулю n ), затем следуйте алгоритму, описанному в разделе «Конгруэнтность квадратов». Эффективность алгоритма факторизации зависит от точных характеристик средства поиска корней (например, возвращает ли он все корни? только самый маленький? случайный?), но он будет эффективным.

Определить, является ли n или n ) , a квадратичным остатком или невычетом по модулю n (обозначается R можно эффективно для N простого числа n путем вычисления символа Лежандра. Однако для составного n это образует квадратичную проблему невязкости , которая, как известно, не так сложна , как факторизация, но предполагается, что она довольно сложна.

С другой стороны, если мы хотим знать, существует ли решение для x меньше некоторого заданного предела c , эта проблема является NP-полной ; однако это решаемая проблема с фиксированным параметром , где c — параметр.

В общем, чтобы определить, является ли a квадратичным вычетом по модулю составного n , можно использовать следующую теорему:

Пусть n > 1 и НОД( a , n ) = 1 . Тогда х ² ≡ a (mod n ) разрешима тогда и только тогда, когда:

• Символ Лежандра $\left({\tfrac {a}{p}}\right)=1$ для всех нечетных простых делителей p числа n .
• a ≡ 1 (mod 4) , если n делится на 4, но не делится на 8; или a ≡ 1 (mod 8), если n делится на 8.

Примечание. Эта теорема по существу требует, чтобы факторизация n была известна. Также обратите внимание, что если НОД( a , n ) = m , то сравнение можно свести к a / m ≡ x ² / m (mod n / m ) , но тогда это убирает проблему с квадратичными вычетами (если m не является квадратом).

Количество квадратичных остатков

Список количества квадратичных вычетов по модулю n для n = 1, 2, 3... выглядит так:

1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, ... (последовательность A000224 в OEIS )

Формула для подсчета количества квадратов по модулю n дана Штанглем.

Применение квадратичных вычетов

Акустика

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

Теория графов

Графы Пэли — это плотные неориентированные графы, по одному для каждого простого числа p ≡ 1 (mod 4), которые образуют бесконечное семейство графов конференций , которые дают бесконечное семейство симметричных матриц конференций .

Орграфы Пэли представляют собой направленные аналоги графов Пэли, по одному для каждого p ≡ 3 (mod 4), которые дают антисимметричные матрицы конференций.

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

Криптография

Тот факт, что извлечение квадратного корня из числа по модулю большого составного n эквивалентно факторингу (что, как широко распространено мнение, является сложной задачей ), использовался для построения криптографических схем, таких как криптосистема Рабина и не обращающий внимания перенос . Проблема квадратичной невязки лежит в основе криптосистемы Гольдвассера-Микали .

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

Тестирование на примитивность

Критерий Эйлера — это формула для символа Лежандра ( a | p ), где p — простое число. Если p является составным, формула может или не может вычислить ( a | p ) правильно. Тест на простоту Соловея -Штрассена для определения того, является ли данное число n простым или составным, выбирает случайное значение a и вычисляет ( a | n ), используя модификацию алгоритма Евклида: а также используя критерий Эйлера. Если результаты не совпадают, n является составным; если они согласны, n может быть составным или простым. Для составного n по крайней мере 1/2 значений a в диапазоне 2, 3,..., n - 1 вернут « n является составным»; для Prime n никто не будет. Если после использования множества различных значений a не было доказано , что n составное, оно называется « вероятным простым числом ».

Критерий простоты Миллера-Рабина основан на тех же принципах. Существует детерминистская версия этого метода, но доказательство того, что он работает, зависит от обобщенной гипотезы Римана ; Результатом этого теста будет: « n определенно составное» или «либо n простое, либо GRH ложно». Если второй результат когда-либо произойдет для составного n , то GRH будет ложным, что будет иметь последствия для многих разделов математики.

Целочисленная факторизация

В § VI Disquisitiones Arithmeticae Гаусс обсуждает два алгоритма факторизации, которые используют квадратичные вычеты и закон квадратичной взаимности .

Некоторые современные алгоритмы факторизации (включая алгоритм Диксона , метод непрерывной дроби , квадратичное решето и решето числового поля ) генерируют небольшие квадратичные остатки (по модулю факторизуемого числа) в попытке найти сравнение квадратов , которое приведет к факторизации. Решето числового поля — это самый быстрый из известных алгоритмов факторизации общего назначения.

Таблица квадратичных вычетов

В следующей таблице (последовательность A096008 в OEIS ) перечислены квадратичные остатки по модулю от 1 до 75 (a красное число означает, что оно не взаимно просто с n ). (Информацию о квадратичных остатках, взаимно простых с n , см. в OEIS : A096103 , а о ненулевых квадратичных остатках см. в OEIS : A046071 .)

н	квадратичные вычеты по модулю n	н	квадратичные вычеты по модулю n	н	квадратичные вычеты по модулю n
1	0	26	0 , 1, 3, 4 , 9, 10 , 12 , 13 , 14 , 16 , 17, 22 , 23, 25	51	0 , 1, 4, 9 , 13, 15 , 16, 18 , 19, 21 , 25, 30 , 33 , 34 , 36 , 42 , 43, 49
2	0 , 1	27	0 , 1, 4, 7, 9 , 10, 13, 16, 19, 22, 25	52	0 , 1, 4 , 9, 12 , 13 , 16 , 17, 25, 29, 36 , 40 , 48 , 49
3	0 , 1	28	0 , 1, 4 , 8 , 9, 16 , 21 , 25	53	0 , 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52
4	0 , 1	29	0 , 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28	54	0 , 1, 4 , 7, 9 , 10 , 13, 16 , 19, 22 , 25, 27 , 28 , 31, 34 , 36 , 37, 40 , 43, 46 , 49, 52
5	0 , 1, 4	30	0 , 1, 4 , 6 , 9 , 10 , 15 , 16 , 19, 21 , 24 , 25	55	0 , 1, 4, 5 , 9, 11 , 14, 15 , 16, 20 , 25 , 26, 31, 34, 36, 44 , 45 , 49
6	0 , 1, 3 , 4	31	0 , 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28	56	0 , 1, 4 , 8 , 9, 16 , 25, 28 , 32 , 36 , 44 , 49
7	0 , 1, 2, 4	32	0 , 1, 4 , 9, 16 , 17, 25	57	0 , 1, 4, 6 , 7, 9 , 16, 19 , 24 , 25, 28, 30 , 36 , 39 , 42 , 43, 45 , 49, 54 , 55
8	0 , 1, 4	33	0 , 1, 3 , 4, 9 , 12 , 15 , 16, 22 , 25, 27 , 31	58	0 , 1, 4 , 5, 6 , 7, 9, 13, 16 , 20 , 22 , 23, 24 , 25, 28 , 29 , 30 , 33, 34 , 35, 36 , 38 , 42 , 45, 49, 51, 52 , 53, 54 , 57
9	0 , 1, 4, 7	34	0 , 1, 2 , 4 , 8 , 9, 13, 15, 16 , 17 , 18 , 19, 21, 25, 26 , 30 , 32 , 33	59	0 , 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27, 28, 29, 35, 36, 41, 45, 46, 48, 49, 51, 53, 57
10	0 , 1, 4 , 5 , 6 , 9	35	0 , 1, 4, 9, 11, 14 , 15 , 16, 21 , 25 , 29, 30	60	0 , 1, 4 , 9 , 16 , 21 , 24 , 25 , 36 , 40 , 45 , 49
11	0 , 1, 3, 4, 5, 9	36	0 , 1, 4 , 9 , 13, 16 , 25, 28	61	0 , 1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 52, 56, 57, 58, 60
12	0 , 1, 4 , 9	37	0 , 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36	62	0 , 1, 2 , 4 , 5, 7, 8 , 9, 10 , 14 , 16 , 18 , 19, 20 , 25, 28 , 31 , 32 , 33, 35, 36 , 38 , 39, 40 , 41, 45, 47, 49, 50 , 51, 56 , 59
13	0 , 1, 3, 4, 9, 10, 12	38	0 , 1, 4 , 5, 6 , 7, 9, 11, 16 , 17, 19 , 20 , 23, 24 , 25, 26 , 28 , 30 , 35, 36	63	0 , 1, 4, 7 , 9 , 16, 18 , 22, 25, 28 , 36 , 37, 43, 46, 49 , 58
14	0 , 1, 2 , 4 , 7 , 8 , 9, 11	39	0 , 1, 3 , 4, 9 , 10, 12 , 13 , 16, 22, 25, 27 , 30 , 36	64	0 , 1, 4 , 9, 16 , 17, 25, 33, 36 , 41, 49, 57
15	0 , 1, 4, 6 , 9 , 10	40	0 , 1, 4 , 9, 16 , 20 , 24 , 25 , 36	65	0 , 1, 4, 9, 10 , 14, 16, 25 , 26 , 29, 30 , 35 , 36, 39 , 40 , 49, 51, 55 , 56, 61, 64
16	0 , 1, 4 , 9	41	0 , 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40	66	0 , 1, 3 , 4 , 9 , 12 , 15 , 16 , 22 , 25, 27 , 31, 33 , 34 , 36 , 37, 42 , 45 , 48 , 49, 55 , 58 , 60 , 64
17	0 , 1, 2, 4, 8, 9, 13, 15, 16	42	0 , 1, 4 , 7 , 9 , 15 , 16 , 18 , 21 , 22 , 25, 28 , 30 , 36 , 37, 39	67	0 , 1, 4, 6, 9, 10, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 29, 33, 35, 36, 37, 39, 40, 47, 49, 54, 55, 56, 59, 60, 62, 64, 65
18	0 , 1, 4 , 7, 9 , 10 , 13, 16	43	0 , 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41	68	0 , 1, 4 , 8 , 9, 13, 16 , 17 , 21, 25, 32 , 33, 36 , 49, 52 , 53, 60 , 64
19	0 , 1, 4, 5, 6, 7, 9, 11, 16, 17	44	0 , 1, 4 , 5, 9, 12 , 16 , 20 , 25, 33 , 36 , 37	69	0 , 1, 3 , 4, 6 , 9 , 12 , 13, 16, 18 , 24 , 25, 27 , 31, 36 , 39 , 46 , 48 , 49, 52, 54 , 55, 58, 64
20	0 , 1, 4 , 5 , 9, 16	45	0 , 1, 4, 9 , 10 , 16, 19, 25 , 31, 34, 36 , 40	70	0 , 1, 4 , 9, 11, 14 , 15 , 16 , 21 , 25 , 29, 30 , 35 , 36 , 39, 44 , 46 , 49 , 50 , 51, 56 , 60 , 64 , 65
21	0 , 1, 4, 7 , 9 , 15 , 16, 18	46	0 , 1, 2 , 3, 4 , 6 , 8 , 9, 12 , 13, 16 , 18 , 23 , 24 , 25, 26 , 27, 29, 31, 32 , 35, 36 , 39, 41	71	0 , 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 24, 25, 27, 29, 30, 32, 36, 37, 38, 40, 43, 45, 48, 49, 50, 54, 57, 58, 60, 64
22	0 , 1, 3, 4 , 5, 9, 11 , 12 , 14 , 15, 16 , 20	47	0 , 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 42	72	0 , 1, 4 , 9 , 16 , 25, 28 , 36 , 40 , 49, 52 , 64
23	0 , 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18	48	0 , 1, 4 , 9 , 16 , 25, 33 , 36	73	0 , 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 19, 23, 24, 25, 27, 32, 35, 36, 37, 38, 41, 46, 48, 49, 50, 54, 55, 57, 61, 64, 65, 67, 69, 70, 71, 72
24	0 , 1, 4 , 9 , 12 , 16	49	0 , 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46	74	0 , 1, 3, 4 , 7, 9, 10 , 11, 12 , 16 , 21, 25, 26 , 27, 28 , 30 , 33, 34 , 36 , 37 , 38 , 40 , 41, 44 , 46 , 47, 48 , 49, 53, 58 , 62 , 63, 64 , 65, 67, 70 , 71, 73
25	0 , 1, 4, 6, 9, 11, 14, 16, 19, 21, 24	50	0 , 1, 4 , 6 , 9, 11, 14 , 16 , 19, 21, 24 , 25 , 26 , 29, 31, 34 , 36 , 39, 41, 44 , 46 , 49	75	0 , 1, 4, 6 , 9 , 16, 19, 21 , 24 , 25 , 31, 34, 36 , 39 , 46, 49, 51 , 54 , 61, 64, 66 , 69

Квадратичные вычеты (см. также A048152 , A343720 )

х	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
х 2	1	4	9	16	25	36	49	64	81	100	121	144	169	196	225	256	289	324	361	400	441	484	529	576	625
против 1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
против 2	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
против 3	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1
против 4	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
против 5	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0
против 6	1	4	3	4	1	0	1	4	3	4	1	0	1	4	3	4	1	0	1	4	3	4	1	0	1
против 7	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2
к 8	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1
к 9	1	4	0	7	7	0	4	1	0	1	4	0	7	7	0	4	1	0	1	4	0	7	7	0	4
около 10	1	4	9	6	5	6	9	4	1	0	1	4	9	6	5	6	9	4	1	0	1	4	9	6	5
около 11	1	4	9	5	3	3	5	9	4	1	0	1	4	9	5	3	3	5	9	4	1	0	1	4	9
около 12	1	4	9	4	1	0	1	4	9	4	1	0	1	4	9	4	1	0	1	4	9	4	1	0	1
около 13	1	4	9	3	12	10	10	12	3	9	4	1	0	1	4	9	3	12	10	10	12	3	9	4	1
около 14	1	4	9	2	11	8	7	8	11	2	9	4	1	0	1	4	9	2	11	8	7	8	11	2	9
около 15	1	4	9	1	10	6	4	4	6	10	1	9	4	1	0	1	4	9	1	10	6	4	4	6	10
около 16	1	4	9	0	9	4	1	0	1	4	9	0	9	4	1	0	1	4	9	0	9	4	1	0	1
около 17	1	4	9	16	8	2	15	13	13	15	2	8	16	9	4	1	0	1	4	9	16	8	2	15	13
около 18	1	4	9	16	7	0	13	10	9	10	13	0	7	16	9	4	1	0	1	4	9	16	7	0	13
около 19	1	4	9	16	6	17	11	7	5	5	7	11	17	6	16	9	4	1	0	1	4	9	16	6	17
около 20	1	4	9	16	5	16	9	4	1	0	1	4	9	16	5	16	9	4	1	0	1	4	9	16	5
к 21	1	4	9	16	4	15	7	1	18	16	16	18	1	7	15	4	16	9	4	1	0	1	4	9	16
к 22	1	4	9	16	3	14	5	20	15	12	11	12	15	20	5	14	3	16	9	4	1	0	1	4	9
к 23	1	4	9	16	2	13	3	18	12	8	6	6	8	12	18	3	13	2	16	9	4	1	0	1	4
около 24	1	4	9	16	1	12	1	16	9	4	1	0	1	4	9	16	1	12	1	16	9	4	1	0	1
к 25	1	4	9	16	0	11	24	14	6	0	21	19	19	21	0	6	14	24	11	0	16	9	4	1	0

См. также

• критерий Эйлера
• Лемма Гаусса
• Zolotarev's lemma
• Сумма символов
• Закон квадратичной взаимности
• Код квадратичного остатка

Ссылки

« Disquisitiones Arithmeticae» переведена с цицероновской латыни Гаусса на английский и немецкий языки . Немецкое издание включает все его статьи по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса , исследования биквадратичной взаимности и неопубликованные заметки.

• Гаусс, Карл Фридрих (1986), Disquisitiones Arithemeticae , перевод Кларка, Артура А. (второе исправленное издание), Нью-Йорк: Springer , ISBN  0-387-96254-9
• Гаусс, Карл Фридрих (1965), Исследования по высшей арифметике [ Disquisitiones Arithemeticae и другие статьи по теории чисел ], перевод Мазера Х. (второе изд.), Нью-Йорк: Челси, ISBN  0-8284-0191-8
• Бах, Эрик; Шалит, Джеффри (1996), Эффективные алгоритмы , Алгоритмическая теория чисел, том. Я, Кембридж: MIT Press , ISBN  0-262-02405-5
• Крэндалл, Ричард; Померанс, Карл (2001), Простые числа: вычислительная перспектива , Нью-Йорк: Springer, ISBN  0-387-94777-9
• Давенпорт, Гарольд (2000), Мультипликативная теория чисел (третье изд.), Нью-Йорк: Springer, ISBN  0-387-95097-4
• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN  0-7167-1045-5 A7.1: AN1, pg.249.
• Харди, штат Джорджия ; Райт, Э.М. (1980), Введение в теорию чисел (пятое изд.), Оксфорд: Oxford University Press , ISBN  978-0-19-853171-5
• Ирландия, Кеннет; Розен, Майкл (1990), Классическое введение в современную теорию чисел (второе изд.), Нью-Йорк: Springer, ISBN  0-387-97329-Х
• Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer, ISBN  3-540-66957-4
• Мандерс, Кеннет Л.; Адлеман, Леонард (1978), « NP -полные задачи решения для бинарных квадратиков», Журнал компьютерных и системных наук , 16 (2): 168–184, doi : 10.1016/0022-0000(78)90044-2 .

Внешние ссылки

• Вайсштейн, Эрик В. «Квадратичный остаток» . Математический мир .
• Доказательство неравенства Полиа – Виноградова на PlanetMath .