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

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

Проблема квадратичной невязкости ( 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 a\equiv b^{2}{\pmod {T}}}$.

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

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{ if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{ if }}a{\text{ is a quadratic non-residue modulo }}p,\\0&{\text{ if }}a\equiv 0{\pmod {p}}.\end{cases}}}$

Это мультипликативный символ , который означает ровно для всех значений и для остальных. ${\displaystyle {\big (}{\tfrac {a}{p}}{\big )}=1}$ ${\displaystyle (p-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 \gcd(a,N)=1}$

Поскольку мы не знаем или , мы не можем вычислить и . Однако их произведение легко вычислить. Это известно как символ Якоби : ${\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)}$

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

Однако мы не можем во всех случаях сказать нам, является ли вычет квадратичным по модулю или нет! Точнее, if 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]} , а также схему Кокса , основанную на идентификации .

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

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

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

1. Калиски, Берт (2011). «Проблема квадратичной невязки». Энциклопедия криптографии и безопасности . п. 1003. дои : 10.1007/978-1-4419-5906-5_429 . ISBN 978-1-4419-5905-8.
2. Адлеман, Л. (1980). «Об отличии простых чисел от составных чисел». Материалы 21-го симпозиума IEEE по основам информатики (FOCS), Сиракьюс, штат Нью-Йорк . стр. 387–408. дои : 10.1109/SFCS.1980.28. ISSN  0272-5428.
3. С. Гольдвассер, С. Микали (1982). «Вероятностное шифрование и как играть в мысленный покер, сохраняя в секрете всю частичную информацию». Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '82 . стр. 365–377. дои : 10.1145/800070.802212. ISBN 0897910702. S2CID  10316867.
4. С. Гольдвассер, С. Микали (1984). «Вероятностное шифрование». Журнал компьютерных и системных наук . 28 (2): 270–299. дои : 10.1016/0022-0000(84)90070-9 .