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

Целое число, являющееся точным квадратом по модулю некоторого целого числа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первое дополнение ^[6] к закону квадратичной взаимности состоит в том, что если 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). ^[7]

Например, по модулю (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 ^k (8 n + 1).

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

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

тогда п ^к а

является вычетом по модулю p ^n, если k ≥ n

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

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

является невычетом по модулю p ^n, если k < n четно и a является невычетом. ^[9]

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

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

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

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

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

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

если a — невычет по модулю n , то a — невычет по модулю pk хотя бы для одной простой степени, ^{делящей} 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.

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

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

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

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

Обозначения

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

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

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

${\displaystyle \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 в комплексные числа при умножении. Установка позволяет расширить область определения до мультипликативной полугруппы всех целых чисел. ^[14] ${\displaystyle ({\tfrac {np}{p}})=0}$

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

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

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

Хотя квадратичные вычеты, по-видимому, возникают по довольно случайному образцу по модулю 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-е годы) над аналитической формулой для числа классов бинарных квадратичных форм . ^[17] Пусть q — простое число, s — комплексная переменная, и определим L-функцию Дирихле как

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

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

${\displaystyle 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. ^[18] Напротив, для простого числа q ≡ 1 (mod 4), сумма квадратичных вычетов минус сумма невычетов в диапазоне 1, 2, ..., q - 1 равно нулю, а это означает, что обе суммы равны . ^{[ нужна цитата ]} ${\displaystyle {\frac {q(q-1)}{4}}}$

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

${\displaystyle 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).

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

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

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

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

То есть:

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

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

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

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

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

${\displaystyle 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\},}$

и разреши

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

То есть,

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

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

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

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

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

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

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

${\displaystyle \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},

А ₁₀ = {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},

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

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

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

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

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

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

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

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

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

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

Легко ^[25] доказать, что

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

Фактически ^[26]

${\displaystyle \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 году, показав, что если обобщенная гипотеза Римана верна, то

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

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

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

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

${\displaystyle \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 , полученная с помощью оценок Бёрджесса на суммах характеров . ^[27]

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

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

Наименьшие квадратичные невычеты по модулю 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 всегда положителен. ^[29]

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

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

1. определить, существует ли решение x 2 ^≡ 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 называется китайской теоремой об остатках ; это может быть реализовано с помощью эффективного алгоритма. ^[30]

Например:

Решите х ² ≡ 6 (по модулю 15).

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

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

Решите х ² ≡ 4 (по модулю 15).

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

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

Решите х ² ≡ 7 (по модулю 15).

x ² ≡ 7 (mod 3) имеет два решения: 1 и 2; x ² ≡ 7 (mod 5) не имеет решений.

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

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

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

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

и Лежандр нашли аналогичное решение ^[32] при n ≡ 5 (mod 8):

${\displaystyle 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) известной формулы не существует. Тонелли ^[33] (в 1891 г.) и Чиполла ^[34] нашли эффективные алгоритмы, работающие для всех простых модулей. Оба алгоритма требуют нахождения квадратичного невычета по модулю n , и для этого не существует эффективного детерминированного алгоритма. Но поскольку половина чисел между 1 и n не являются вычетами, случайный выбор чисел x и вычисление символа Лежандра до тех пор, пока не будет найден невычет, быстро приведет к его получению. Небольшим вариантом этого алгоритма является алгоритм Тонелли-Шенкса . ${\displaystyle \left({\frac {x}{n}}\right)}$

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

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

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

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

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

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

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

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

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

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

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

Примечание. Эта теорема по существу требует, чтобы факторизация n была известна. Также обратите внимание, что если gcd( 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 дана Штанглем. ^[38]

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

Акустика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Примечания

1. Леммемейер, Ч. 1
2. Леммермейер, стр. 6–8, стр. 16 и далее
3. Гаусс Д.А., ст. 94
4. Гаусс Д.А., ст. 96
5. Гаусс Д.А., ст. 98
6. Гаусс, Д.А., арт 111.
7. Гаусс Д.А., ст. 103
8. Гаусс Д.А., ст. 101
9. Гаусс Д.А., ст. 102
10. например, Ирландия и Розен 1990, с. 50
11. Гаусс Д.А., ст. 131
12. например, Харди и Райт используют его.
13. Гаусс, Д.А., арт 230 и далее.
14. Это расширение области определения необходимо для определения функций L.
15. Примеры см. в разделе Символ Лежандра # Свойства символа Лежандра.
16. Леммермейер, стр. 111 – конец.
17. Давенпорт 2000, стр. 8–9, 43–51. Это классические результаты.
18. Davenport 2000, стр. 49–51 (предположение Якоби , доказанное Дирихле)
19. Давенпорт 2000, стр. 9
20. Леммермейер, с. 29 упр. 1,22; ср. стр. 26–27, гл. 10
21. Crandall & Pomerance, ex 2.38, стр. 106–108.
22. Гаусс, Theorie der biquadratischen Reste, Erste Abhandlung (стр. 511–533 из Untersuchungen über hohere Arithmetik)
23. Crandall & Pomerance, ex 2.38, стр. 106–108 обсуждают сходства и различия. Например, подбрасывая n монет, можно (хотя и маловероятно) получить n /2 орлов, за которыми последует такое же количество решок. Неравенство ВП исключает это для остатков.
24. Davenport 2000, стр. 135–137, (доказательство P – V (фактически большое О можно заменить на 2); ссылки в журналах на Пейли, Монтгомери и Шура)
25. Planet Math: Доказательство неравенства Полиа – Виноградова во внешних ссылках. Доказательство занимает целую страницу и требует только элементарных фактов о гауссовских суммах.
26. Pomerance & Crandall, ex 2.38, стр. 106–108. результат Т. Кокрейна, «О тригонометрическом неравенстве Виноградова», J. Number Theory , 27: 9–16, 1987.
27. Фридлендер, Джон Б .; Иванец, Хенрик (2010). Опера Де Крибро . Американское математическое общество . п. 156. ИСБН 978-0-8218-4970-5. Збл  1226.11099.
28. Монтгомери, Хью Л. (1994). Десять лекций о взаимодействии аналитической теории чисел и гармонического анализа . Американское математическое общество . п. 176. ИСБН 0-8218-0737-4. Збл  0814.11001.
29. Бейтман, Пол Т .; Даймонд, Гарольд Г. (2004). Аналитическая теория чисел . Всемирная научная. п. 250. ИСБН 981-256-080-7. Збл  1074.11001.
30. Бах и Шалит 1996, с. 104 и далее; для этого требуется O(log ² m ) шагов, где m — количество простых чисел, делящих n .
31. Бах и Шалит 1996, с. 113; для вычислений требуется O(log a log n ) шагов ${\displaystyle \left({\frac {a}{n}}\right)}$
32. Леммермейер, с. 29
33. Бах и Шалит 1996, с. 156 и далее; алгоритм требует O(log ⁴ n ) шагов.
34. Бах и Шалит 1996, с. 156 и далее; алгоритм требует O(log ³ n ) шагов и также является недетерминированным.
35. Крэндалл и Померанс, бывш. 6.5 и 6.6, стр.273
36. Мандерс и Адлеман, 1978 г.
37. Бертон, Дэвид (2007). Элементарная теория чисел . Нью-Йорк: МакГроу Хилл. п. 195.
38. Штангл, Уолтер Д. (октябрь 1996 г.), «Счет квадратов в ℤn» (PDF) , Mathematics Magazine , 69 (4): 285–289, doi : 10.2307/2690536, JSTOR  2690536
39. Уокер, Р. «Проектирование и применение модульных акустических рассеивающих элементов» (PDF) . Исследовательский отдел BBC . Проверено 25 октября 2016 г.
40. Бах и Шалит 1996, с. 113
41. Бах и Шалит 1996, стр. 109–110; Критерий Эйлера требует O(log ³ n ) шагов.
42. Гаусс, Д.А., искусство 329–334.

Рекомендации

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

• Гаусс, Карл Фридрих (1986), Disquisitiones Arithemeticae , перевод Кларка, Артура А. (второе исправленное издание), Нью-Йорк: Springer , ISBN 0-387-96254-9
• Гаусс, Карл Фридрих (1965), Untersuchungen über hohere Arithmetik [ 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А7.1: AN1, стр.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 .