Квадратичный вычет

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

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

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

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

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

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

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

Для заданного n список квадратичных вычетов по модулю n может быть получен простым возведением в квадрат всех чисел 0, 1, ..., n − 1. Поскольку a ≡ b (mod n ) влечет a ² ≡ b ² (mod n ), любой другой квадратичный вычет будет конгруэнтным (mod n ) некоторым числам в полученном списке. Но полученный список состоит не только из взаимно неконгруэнтных квадратичных вычетов (mod n). Поскольку a ² ≡( n − a ) ² (mod n ), список, полученный возведением в квадрат всех чисел в списке 1, 2, ..., n − 1 (или в списке 0, 1, ..., n ), симметричен (mod n ) относительно своей средней точки, поэтому на самом деле нужно возвести в квадрат только все числа в списке 0, 1, ..., n /2 . Полученный таким образом список может по-прежнему содержать взаимно конгруэнтные числа (mod 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 (mod 8) и, таким образом, также ≡ 1 (mod 4). Если a — нечетное число и m = 8, 16 или некоторая большая степень 2, то a является остатком по модулю m тогда и только тогда, когда a ≡ 1 (mod 8). ^[7]

Например, mod (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 и т. д. тогда и только тогда, когда оно имеет вид 4k ⁽ 8n + 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, подчиняются тем же правилам, что и по модулю p ; p является невычетом, и в общем случае все остатки и невычеты подчиняются тем же правилам, за исключением того, что произведения будут равны нулю, если степень p в произведении ≥ n .

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

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

Основной факт в этом случае заключается в том, что

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

если a является невычетом по модулю n , то a является невычетом по модулю p ^k по крайней мере для одной простой степени, делящей 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, все равно нулю, следует из работы в полном кольце , которое имеет делители нуля для составного n . ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )}$

По этой причине некоторые авторы ^[10] добавляют к определению, что квадратичный вычет ^a должен быть не только квадратом, но и должен быть взаимно простым с модулем n . ( a взаимно просто с n тогда и только тогда, когда a2 взаимно просто с 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 , то но если мы не знаем, является ли a R m или a 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 будут. CRT утверждает, что это то же самое, что 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 (mod 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 mod 4, избыток равен нулю, поскольку −1 — квадратичный вычет, а вычеты симметричны относительно r ↔ p − r . Для p, сравнимого с 3 mod 4, избыток E всегда положителен. ^[29]

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

То есть, если задано число a и модуль n , насколько сложно

1. определить, существует ли x , решающее 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 .

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

Например:

Решите x ² ≡ 6 (mod 15).

x ² ≡ 6 (mod 3) имеет одно решение, 0; x ² ≡ 6 (mod 5) имеет два решения, 1 и 4.

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

Решите x ² ≡ 4 (mod 15).

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

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

Решите x ² ≡ 7 (mod 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 (обозначается a R n или a N n ), может быть эффективно выполнено для простого n путем вычисления символа Лежандра. Однако для составного n это образует задачу квадратичного вычета , которая, как известно, не так сложна , как факторизация, но предполагается, что она довольно сложна.

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

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

Пусть n > 1 и gcd( 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, является ли заданное число n простым или составным, выбирает случайное a и вычисляет ( a | n ), используя модификацию алгоритма Евклида ^[40] , а также используя критерий Эйлера. ^[41] Если результаты не совпадают, n является составным; если они совпадают, n может быть составным или простым. Для составного n по крайней мере 1/2 значения a в диапазоне 2, 3, ..., n − 1 вернут « n является составным»; для простого n ни одно не вернет. Если после использования многих различных значений a составность n не была доказана , оно называется « вероятным простым ».

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

Факторизация целых чисел

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

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

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

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

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

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

Примечания

1. Леммемайер, Гл. 1
2. Леммермейер, стр. 6–8, стр. 16 и далее.
3. Гаусс, DA, ст. 94
4. Gauss, DA, ст. 96
5. Gauss, DA, ст. 98
6. Гаусс, DA, ст. 111
7. Гаусс, DA, статья 103
8. Gauss, DA, статья 101
9. Гаусс, DA, статья 102
10. например, Айрленд и Розен 1990, стр. 50
11. Гаусс, DA, статья 131
12. например, Харди и Райт используют его
13. Гаусс, DA, ст. 230 и далее.
14. Это расширение области необходимо для определения L- функций.
15. См . Символ Лежандра#Свойства символа Лежандра для примеров.
16. Леммермейер, стр. 111–конец
17. Davenport 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, pp 106–108 обсуждают сходства и различия. Например, подбрасывая n монет, возможно (хотя и маловероятно) получить n /2 орлов, за которыми последует столько же решек. Неравенство VP исключает это для остатков.
24. Davenport 2000, стр. 135–137, (доказательство P–V, (на самом деле big-O можно заменить на 2); ссылки на журналы Paley, Montgomery и Schur)
25. Planet Math: Доказательство неравенства Полиа–Виноградова во внешних ссылках. Доказательство занимает страницу и требует только элементарных фактов о суммах Гаусса
26. Pomerance & Crandall, ex 2.38 pp.106–108. результат из T. Cochrane, "О тригонометрическом неравенстве Виноградова", J. Number Theory , 27:9–16, 1987
27. Фридлендер, Джон Б.; Иванец , Генрик (2010). Opera De Cribro . Американское математическое общество . стр. 156. ISBN 978-0-8218-4970-5. Збл  1226.11099.
28. Монтгомери, Хью Л. (1994). Десять лекций о взаимодействии аналитической теории чисел и гармонического анализа . Американское математическое общество . стр. 176. ISBN 0-8218-0737-4. Збл  0814.11001.
29. Бейтман, Пол Т .; Даймонд, Гарольд Г. (2004). Аналитическая теория чисел . World Scientific. стр. 250. ISBN 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. Crandall & Pomerance, пр. 6.5 и 6.6, стр. 273
36. Мандерс и Адлеман 1978
37. Бертон, Дэвид (2007). Элементарная теория чисел . Нью-Йорк: McGraw HIll. стр. 195.
38. Stangl, Walter D. (октябрь 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. Гаусс, DA, искусства 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), Эффективные алгоритмы , Алгоритмическая теория чисел, т. I, Кембридж: Издательство MIT , 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-5A7.1: AN1, стр.249.
• Харди, Г. Х.; Райт , Э. М. (1980), Введение в теорию чисел (пятое изд.), Оксфорд: Oxford University Press , ISBN 978-0-19-853171-5
• Айрленд, Кеннет; Розен, Майкл (1990), Классическое введение в современную теорию чисел (второе изд.), Нью-Йорк: Springer, ISBN 0-387-97329-X
• Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer, ISBN 3-540-66957-4
• Мандерс, Кеннет Л.; Адлеман, Леонард (1978), « NP -полные задачи принятия решений для двоичных квадратичных уравнений», Журнал компьютерных и системных наук , 16 (2): 168–184, doi : 10.1016/0022-0000(78)90044-2 .

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

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