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

В теории чисел , целое число д называется квадратичным вычетом по модулю п , если оно конгруэнтно к идеальному квадратному по модулю п ; то есть, если существует целое число 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 ² ≡ ( n - a ) ² (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 , как частный случай и работой в рамках мультипликативной группы ненулевых элементов в поле Z / р Z . (Другими словами, каждый класс сравнения, кроме нулевого по модулю 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 (mod 8) и, следовательно, также 1 (mod 4). Если a - нечетное число и m = 8, 16 или некоторая более высокая степень двойки, то 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 и т. Д. Тогда и только тогда, когда оно имеет вид 4 ^k (8 n + 1).

Ряд взаимно простой с нечетным простым р представляет собой остаток по модулю любой степени р , если и только если оно представляет собой остаток по модулю р . ^[8]

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

тогда p ^k a

является вычетом по модулю 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.

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

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

По этой причине некоторые авторы ^[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 {не делит}} a \\ - 1 & {\ text {if}} a \ operatorname { N} p {\ text {and}} p {\ text {не делит}} a \ end {case}}}$

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

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

Существует обобщение символа Лежандра для составных значений р , с символом Якоби , но его свойства не так просто: если т составное и символ Якоби , то N м , а если в R м , то но если мы не знаете ли в R м или в N м . Например: а , но 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 , и это использовалось в таких приложениях, как акустика и криптография , их распределение также демонстрирует некоторые поразительные закономерности.

Используя теорему Дирихле о простых числах в арифметических прогрессиях , закон квадратичной взаимности и китайскую теорему об остатках (CRT), легко увидеть, что для любого 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 (мод. 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

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

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

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

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

По модулю 19

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

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

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

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

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

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

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

Значения для последовательных значений в мимической случайной величины , как флип монеты . ^{[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),}$

в большой нотации O . Параметр

${\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 ) более тонкий, но он всегда прост. Приведенное выше неравенство Полиа – Виноградова дает 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, 3, 2, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 2, 5, 2, 2, 2, 7, 5, 2, 3, 2, 3, 2, 2, 3, 7, 7, 2, 3, 5, 2, 3, 2, 3, 2, 2, 2, 11, 5, 2, 2, 5, 2, 2, 3, 7, 3, 2, 2, .. . (последовательность A053760 в OEIS )

Квадратичный эксцесс [ править ]

Пусть p нечетное простое число. Квадратичная избыток Е ( р ) число квадратичных вычетов на интервале (0, р / 2) минус число в диапазоне ( р / 2, р ) (последовательность 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 _{2 по} модулю второго, ..., будет 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}$

Если полное разложение по п не известна, а и п не сравнимо с 2 по модулю 4, или п сравнимо с 2 по модулю 4 и , проблема , как известно, эквивалентна целочисленной факторизации из п (т.е. эффективное решение либо проблема может быть использована для эффективного решения другой проблемы).${\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]

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

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

В общем, чтобы определить , является ли квадратичный вычет по модулю композит п , можно использовать следующую теорему: ^[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, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, ... (последовательность A000224 в OEIS )

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

Приложения квадратичных вычетов [ править ]

Акустика [ править ]

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

Теория графов [ править ]

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

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

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

Криптография [ править ]

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

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

Проверка на первичность [ править ]

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

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

Целочисленная факторизация [ править ]

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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

• Гаусс, Карл Фридрих; Кларк, Артур А. (переводчик на английский язык) (1986), Disquisitiones Arithemeticae (второе исправленное издание), Нью-Йорк: Springer , ISBN 0-387-96254-9
• Гаусс, Карл Фридрих; Мазер, Х. (перевод на немецкий) (1965), Untersuchungen über hohere Arithmetik [ Disquisitiones Arithemeticae & другие статьи по теории чисел ] (второе изд.), Нью-Йорк: Chelsea, ISBN 0-8284-0191-8
• Бах, Эрик; Шаллит, Джеффри (1996), Эффективные алгоритмы , теория алгоритмических чисел, I , Кембридж: 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, стр. 249.
• Харди, GH ; Райт, EM (1980), Введение в теорию чисел (пятое изд.), Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Ирландия, Кеннет; Розен, Майкл (1990), Классическое введение в современную теорию чисел (второе изд.), Нью-Йорк: Springer, ISBN 0-387-97329-X
• Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer, ISBN 3-540-66957-4
• Manders, Kenneth L .; Адлеман, Леонард (1978), " NP Проблемы принятия решений -полных для Binary квадратичных", журнал компьютерных и системных наук , 16 (2): 168-184, DOI : 10,1016 / 0022-0000 (78) 90044-2 .

Внешние ссылки [ править ]

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