В теории чисел целое число q называется квадратичным вычетом по модулю n, если оно конгруэнтно совершенному квадрату по модулю n ; т. е. если существует целое число x такое, что:
В противном случае q называется квадратичным невычетом по модулю n .
Первоначально это абстрактное математическое понятие из раздела теории чисел, известного как модульная арифметика , квадратичные вычеты теперь используются в различных приложениях, от акустической техники до криптографии и факторизации больших чисел .
Ферма , Эйлер , Лагранж , Лежандр и другие теоретики чисел 17 и 18 веков установили теоремы [1] и сформировали гипотезы [2] о квадратичных вычетах, но первое систематическое рассмотрение - это § IV « Disquisitiones Arithmeticae » Гаусса (1801). . В статье 95 вводятся термины «квадратичный остаток» и «квадратичный невычет» и говорится, что, если из контекста становится ясно, прилагательное «квадратичный» может быть опущено.
Для данного n список квадратичных вычетов по модулю n можно получить, просто возведя в квадрат числа 0, 1, ..., n − 1 . Поскольку a 2 ≡ ( n − a ) 2 (mod n ), список квадратов по модулю n симметричен относительно n /2, и список должен подняться только до этой высоты. Это можно увидеть в таблице ниже.
Таким образом, число квадратичных вычетов по модулю n не может превышать n /2 + 1 ( n четное) или ( n + 1)/2 ( n нечетное). [3]
Произведение двух остатков всегда является остатком.
По модулю 2 каждое целое число является квадратичным вычетом.
По модулю нечетного простого числа p существует ( p + 1)/2 остатков (включая 0) и ( p − 1)/2 невычетов по критерию Эйлера . В этом случае принято рассматривать 0 как частный случай и работать внутри мультипликативной группы ненулевых элементов поля . (Другими словами, каждый класс конгруэнтности, кроме нуля по модулю p, имеет мультипликативный обратный. Это неверно для составных модулей.) [4]
Следуя этому соглашению, мультипликативный обратный остаток является остатком, а обратный невычету является невычетом. [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 2 ≡ 15 2 ≡ 1
- 3 2 ≡ 13 2 ≡ 9
- 5 2 ≡ 11 2 ≡ 25
- 7 2 ≡ 9 2 ≡ 49 ≡ 17
и четные
- 0 2 ≡ 8 2 ≡ 16 2 ≡ 0
- 2 2 ≡ 6 2 ≡ 10 2 ≡ 14 2 ≡ 4
- 4 2 ≡ 12 2 ≡ 16.
Таким образом, ненулевое число является остатком по модулю 8, 16 и т. д. тогда и только тогда, когда оно имеет вид 4 k (8 n + 1).
Число , относительно простое по отношению к нечетному простому числу p, является остатком по модулю любой степени p тогда и только тогда, когда оно является остатком по модулю p . [8]
Если модуль равен p n ,
Обратите внимание, что правила различаются для степеней двойки и степеней нечетных простых чисел.
По модулю нечетной степени простого числа n = p k произведения остатков и невычетов, относительно простых с p, подчиняются тем же правилам, что и по mod p ; p является невычетом, и, как правило, все остатки и невычеты подчиняются одним и тем же правилам, за исключением того, что произведения будут равны нулю, если степень p в произведении ≥ n .
По модулю 8 произведение невычетов 3 и 5 является невычетом 7, и аналогично для перестановок 3, 5 и 7. Фактически, мультипликативная группа невычетов и 1 образует четырехгруппу Клейна .
Основным фактом в данном случае является
По модулю составного числа произведение двух остатков является остатком. Произведение остатка и неостатка может быть остатком, неостатком или нулем.
Например, из таблицы для модуля 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.
Это явление лучше всего можно описать, используя словарь абстрактной алгебры. Классы сравнения , относительно простые по модулю, представляют собой группу при умножении, называемую группой единиц кольца , а квадраты являются ее подгруппой . Разные невычеты могут принадлежать разным смежным классам , и не существует простого правила, предсказывающего, в каком из них будет находиться их произведение. По модулю простого числа существует только подгруппа квадратов и один смежный класс.
Тот факт, что, например, по модулю 15 произведение невычетов 3 и 5, или невычета 5 и остатка 9, или двух остатков 9 и 10 равно нулю, является результатом работы в полном кольце , которое имеет делители нуля для составной н .
По этой причине некоторые авторы [10] добавляют к определению, что квадратичный вычет a должен быть не только квадратом, но и быть относительно простым с модулем n . ( a взаимно просто с n тогда и только тогда, когда a 2 взаимно просто с n .)
Хотя это упрощает задачу, эта статья не настаивает на том, что остатки должны быть взаимно простыми по модулю.
Гаусс [11] использовал R и N для обозначения невязкости и невязкости соответственно;
Хотя это обозначение компактно и удобно для некоторых целей, [12] [13] более полезным обозначением является символ Лежандра , также называемый квадратичным характером , который определяется для всех целых чисел a и положительных нечетных простых чисел p как
Есть две причины, по которым числа ≡ 0 (mod p ) рассматриваются особым образом. Как мы видели, это облегчает формулировку многих формул и теорем. Другая (связанная с этим) причина заключается в том, что квадратичный характер является гомоморфизмом мультипликативной группы ненулевых классов конгруэнтности по модулю p в комплексные числа при умножении. Установка позволяет расширить область определения до мультипликативной полугруппы всех целых чисел. [14]
Одним из преимуществ этого обозначения перед обозначением Гаусса является то, что символ Лежандра представляет собой функцию, которую можно использовать в формулах. [15] Его также можно легко обобщить на вычеты кубической , четвертой и более высокой степени. [16]
Существует обобщение символа Лежандра для составных значений p — символ Якоби , но его свойства не так просты: если m составное и символ Якоби, то a N m , а если a R m , то , но если мы не узнать, является ли R m или N m . Например: и , но 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 2 ≡ 1, 1046 2 ≡ 2, 123 2 ≡ 3, 2 2 ≡ 4, 643 2 ≡ 5, 87 2 ≡ 6, 668 2 ≡ 7, 429 2 ≡ 8, 3 2 ≡ 9 и 529 2 ≡ 10 (по модулю 2521).
Первая из этих закономерностей вытекает из работы Питера Густава Лежена Дирихле (1830-е годы) над аналитической формулой для числа классов бинарных квадратичных форм . [17] Пусть q — простое число, s — комплексная переменная, и определим L-функцию Дирихле как
Дирихле показал, что если q ≡ 3 (mod 4), то
Следовательно, в этом случае (простое 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 равно нулю, а это означает, что обе суммы равны . [ нужна цитата ]
Дирихле также доказал, что для простого числа q ≡ 3 (mod 4)
Это означает, что среди чисел 1, 2, ..., ( q - 1)/2 квадратичных вычетов больше, чем невычетов .
Например, по модулю 11 имеется четыре остатка меньше 6 (а именно 1, 3, 4 и 5), но только один неостаток (2).
Интригующий факт об этих двух теоремах заключается в том, что все известные доказательства основаны на анализе; никто никогда не публиковал простого или прямого доказательства того или иного утверждения. [19]
Если p и q — нечетные простые числа, то:
(( p — квадратичный вычет по модулю q ) тогда и только тогда, когда ( q — квадратичный вычет по модулю p )) тогда и только тогда, когда (хотя бы один из p и q конгруэнтен 1 по модулю 4).
То есть:
где находится символ Лежандра .
Таким образом, для чисел 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 определим множества
и разреши
То есть,
Тогда если p ≡ 1 (mod 4)
и если p ≡ 3 (mod 4)
Например: (остатки выделены жирным шрифтом )
по модулю 17
- 1 , 2 , 3, 4 , 5, 6, 7, 8 , 9 , 10, 11, 12, 13 , 14, 15 , 16
- А 00 = {1,8,15},
- А 01 = {2,4,9,13},
- А 10 = {3,7,12,14},
- А 11 = {5,6,10,11}.
по модулю 19
- 1 , 2, 3, 4 , 5 , 6 , 7 , 8, 9 , 10, 11 , 12, 13, 14, 15, 16 , 17 , 18
- А 00 = {4,5,6,16},
- А 01 = {1,7,9,11,17},
- А 10 = {3,8,10,15},
- А 11 = {2,12,13,14}.
Гаусс (1828) [22] ввел этот вид счета, когда доказал, что если p ≡ 1 (mod 4), то x 4 ≡ 2 (mod p ) можно решить тогда и только тогда, когда p = a 2 + 64 b 2 .
Значения последовательных значений a имитируют случайную величину, например подбрасывание монеты . [23] В частности, Полиа и Виноградов доказали [24] (независимо) в 1918 году, что для любого неглавного характера Дирихле χ( n ) по модулю q и любых целых чисел M и N ,
в большой записи О. Параметр
это показывает, что количество квадратичных вычетов по модулю q в любом интервале длины N равно
Легко [25] доказать, что
Фактически [26]
Монтгомери и Воган улучшили это утверждение в 1977 году, показав, что если обобщенная гипотеза Римана верна, то
Этот результат невозможно существенно улучшить, поскольку в 1918 г. Шур доказал, что
и Пейли доказали в 1932 году, что
для бесконечного числа d > 0.
Наименьший квадратичный вычет по модулю p, очевидно, равен 1. Вопрос о величине наименьшего квадратичного невычета n ( p ) более тонкий, но он всегда простой, причем 7 впервые появляется в 71.
Неравенство Полиа – Виноградова, приведенное выше, дает O( √ p log p ).
Наилучшая безусловная оценка — это n ( p ) ≪ pθ для любого θ>1/4 √e , полученная с помощью оценок Бёрджесса на суммах характеров . [27]
Приняв обобщенную гипотезу Римана , Анкени получил n ( p ) ≪ (log p ) 2 . [28]
Линник показал, что число p меньше X таких, что n ( p ) > X ε, ограничено константой, зависящей от ε. [27]
Наименьшие квадратичные невычеты по модулю p для нечетных простых чисел p :
Пусть 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 , насколько это сложно
Здесь проявляется важная разница между простыми и составными модулями. По модулю простого числа p квадратичный вычет a имеет 1 + ( a | p ) корней (т.е. ноль, если a N p , один, если a ≡ 0 (mod p ), или два, если a R p и gcd( a,p ) = 1.)
В общем случае, если составной модуль n записан как произведение степеней различных простых чисел и имеется n 1 корней по модулю первого, n 2 по модулю второго, ..., будет n 1 n 2 ... корней. по модулю н .
Теоретический способ объединения решений по модулю простых чисел для получения решений по модулю n называется китайской теоремой об остатках ; это может быть реализовано с помощью эффективного алгоритма. [30]
Например:
- Решите х 2 ≡ 6 (по модулю 15).
- x 2 ≡ 6 (mod 3) имеет одно решение, 0; x 2 ≡ 6 (по модулю 5) имеет двойку, 1 и 4.
- и есть два решения по модулю 15, а именно 6 и 9.
- Решите х 2 ≡ 4 (по модулю 15).
- x 2 ≡ 4 (mod 3) имеет два решения: 1 и 2; x 2 ≡ 4 (по модулю 5) имеет двойку, 2 и 3.
- и существует четыре решения по модулю 15, а именно 2, 7, 8 и 13.
- Решите х 2 ≡ 7 (по модулю 15).
- x 2 ≡ 7 (mod 3) имеет два решения: 1 и 2; x 2 ≡ 7 (mod 5) не имеет решений.
- и решений по модулю 15 нет.
Во-первых, если модуль n является простым, символ Лежандра можно быстро вычислить, используя вариант алгоритма Евклида [31] или критерий Эйлера . Если это -1, то решения нет. Во-вторых, предполагая, что , если n ≡ 3 (mod 4), Лагранж нашел, что решения имеют вид
и Лежандр нашли аналогичное решение [32] при n ≡ 5 (mod 8):
Однако для простого числа n ≡ 1 (mod 8) известной формулы не существует. Тонелли [33] (в 1891 г.) и Чиполла [34] нашли эффективные алгоритмы, работающие для всех простых модулей. Оба алгоритма требуют нахождения квадратичного невычета по модулю n , и для этого не существует эффективного детерминированного алгоритма. Но поскольку половина чисел между 1 и n не являются вычетами, случайный выбор чисел x и вычисление символа Лежандра до тех пор, пока не будет найден невычет, быстро приведет к его получению. Небольшим вариантом этого алгоритма является алгоритм Тонелли-Шенкса .
Если модуль n является простой степенью n = p e , решение можно найти по модулю p и «поднять» до решения по модулю n , используя лемму Гензеля или алгоритм Гаусса. [8]
Если модуль n был разложен на простые степени, решение обсуждалось выше.
Если n не соответствует 2 по модулю 4 и символу Кронекера , то решения нет; если n соответствует 2 по модулю 4 и , то решения также нет. Если n не соответствует 2 по модулю 4 и , или n соответствует 2 по модулю 4 и , то один может быть, а может и не быть.
Если полная факторизация n неизвестна, и n не конгруэнтно 2 по модулю 4, или n конгруэнтно 2 по модулю 4 и , известно , что проблема эквивалентна целочисленной факторизации n (т.е. эффективное решение либо проблема может быть использована для эффективного решения другой).
Приведенное выше обсуждение показывает, как знание факторов n позволяет нам эффективно находить корни. Допустим, существует эффективный алгоритм поиска квадратных корней по модулю составного числа. В статье «Сравнение квадратов» обсуждается, как найти два числа x и y, где x 2 ≡ y 2 (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 2 ≡ a (mod n ) разрешима тогда и только тогда, когда:
Примечание. Эта теорема по существу требует, чтобы факторизация n была известна. Также обратите внимание, что если gcd( a , n ) = m , то сравнение можно свести к a / m ≡ x 2 / m (mod n / m ) , но тогда это снимает проблему с квадратичными вычетами (если только m не является квадрат).
Список количества квадратичных вычетов по модулю n для n = 1, 2, 3... выглядит так:
Формула для подсчета количества квадратов по модулю 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 .)
« Disquisitiones Arithmeticae» переведена с цицероновской латыни Гаусса на английский и немецкий языки . Немецкое издание включает все его статьи по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса , исследования биквадратичной взаимности и неопубликованные заметки.