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

В теории чисел целое число 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 и НОД( 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 n ) a квадратичным остатком или невычетом по модулю n (обозначается R , может быть эффективно выполнено для простого числа 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 .