Проблема квадратичной остаточности

Проблема квадратичной остаточности ( QRP ^[1] ) в вычислительной теории чисел состоит в том, чтобы решить, учитывая целые числа и , является ли квадратичный вычет по модулю или нет. Здесь для двух неизвестных простых чисел и , и входит в число чисел, которые не являются явно квадратичными невычетами (см. Ниже).${\ displaystyle a}$${\ displaystyle N}$${\ displaystyle a}$${\ displaystyle N}$${\ displaystyle N = p_ {1} p_ {2}}$${\ displaystyle p_ {1}}$${\ displaystyle p_ {2}}$${\ displaystyle a}$

Проблема была впервые описана Гауссом в его Disquisitiones Arithmeticae в 1801 году. Считается, что эта проблема трудна в вычислительном отношении . Некоторые криптографические методы зависят от его надежности , см. Приложения .

Эффективный алгоритм для проблемы квадратичной остаточности немедленно подразумевает эффективные алгоритмы для других теоретико-числовых задач, таких как решение, является ли композиция неизвестной факторизации произведением 2 или 3 простых чисел. ^[2]${\ displaystyle N}$

Точная формулировка [ править ]

Для заданных целых чисел и , называется квадратичным вычетом по модулю, если существует такое целое число , что${\ displaystyle a}$${\ displaystyle T}$${\ displaystyle a}$${\ displaystyle T}$${\ displaystyle b}$

${\ Displaystyle а \ эквив б ^ {2} {\ pmod {T}}}$.

В противном случае мы говорим, что это квадратичный невычет. Когда стоит простое число, принято использовать символ Лежандра :${\ displaystyle T = p}$

${\ displaystyle \ left ({\ frac {a} {p}} \ right) = {\ begin {cases} 1 & {\ text {if}} a {\ text {квадратичный остаток по модулю}} p {\ text {and}} a \ not \ Equiv 0 {\ pmod {p}}, \\ - 1 & {\ text {if}} a {\ text {является квадратичным невычетом по модулю}} p, \\ 0 & {\ текст {if}} a \ Equiv 0 {\ pmod {p}}. \ end {case}}}$

Это мультипликативный символ, который означает ровно одно из значений , и это - остальные.${\ displaystyle {\ big (} {\ tfrac {a} {p}} {\ big)} = 1}$${\ Displaystyle (п-1) / 2}$${\ displaystyle 1, \ ldots, p-1}$${\displaystyle -1}$

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

Рассмотрим теперь некоторые данные, где и - два разных неизвестных простых числа. Данное является квадратичным вычетом по модулю тогда и только тогда, когда является квадратичным вычетом по модулю обоих и .${\displaystyle N=p_{1}p_{2}}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle a}$${\displaystyle N}$${\displaystyle a}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$

Поскольку мы не знаем или , мы не можем вычислить и . Однако их произведение легко вычислить. Это известно как символ Якоби :${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}}$${\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}$

${\displaystyle \left({\frac {a}{N}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)}$

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

Однако не во всех случаях может сказать нам, является ли квадратичный вычет по модулю или нет! Точнее, если then обязательно является квадратичным невычетом по модулю или , и в этом случае мы закончили. Но если тогда это либо случай, который является квадратичным вычетом по модулю обоих и , либо квадратичным невычетом по модулю обоих и . Мы не можем отличить эти случаи от знания этого .${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}}$${\displaystyle a}$${\displaystyle N}$${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=-1}$${\displaystyle a}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$${\displaystyle a}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$

Это приводит к точной формулировке проблемы квадратичного вычета:

Проблема: даны целые числа и , где и неизвестны, разные простые числа и где , определить, является ли квадратичный вычет по модулю или нет.${\displaystyle a}$${\displaystyle N=p_{1}p_{2}}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$${\displaystyle a}$${\displaystyle N}$

Распределение остатков [ править ]

Если обращаются равномерно случайным образом из целых чисел , так что , это чаще квадратичный вычет или квадратичный без вычетов по модулю ?${\displaystyle a}$${\displaystyle 0,\ldots ,N-1}$${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$${\displaystyle a}$${\displaystyle N}$

Как упоминалось ранее, тогда ровно для половины вариантов , а для остальных у нас есть . По большому счету, это также верно для половины вариантов . Аналогично для . Из основной алгебры следует, что это деление на 4 части равного размера, в зависимости от знака и .${\displaystyle a\in \{1,\ldots ,p_{1}-1\}}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=1}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=-1}$${\displaystyle a\in \{1,\ldots ,N-1\}\setminus p_{1}\mathbb {Z} }$${\displaystyle p_{2}}$${\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{\times }}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}}$${\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}$

Разрешенные в задаче о квадратичном вычете, приведенные выше, составляют именно те две части, которые соответствуют случаям и . Следовательно, ровно половина возможных является квадратичным вычетом, а оставшаяся - нет.${\displaystyle a}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=1}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=-1}$${\displaystyle a}$

Приложения [ править ]

Сложность проблемы квадратичной остаточности является основой безопасности генератора псевдослучайных чисел Блюма-Блюма-Шуба и криптосистемы Голдвассера – Микали . ^{[3] [4]}

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

• Проблема более высокой остаточности

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