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

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

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

Эффективный алгоритм решения квадратичной проблемы невязкости немедленно влечет за собой эффективные алгоритмы для других задач теории чисел , таких как определение того, является ли составное $N$ неизвестной факторизации является произведением двух или трех простых чисел.

Точная формулировка

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

$a\equiv b^{2}{\pmod {T}}$.

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

$\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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

Трудноразрешимость квадратичной проблемы невязкости является основой безопасности генератора Блюма Блюма Шуба псевдослучайных чисел . Это также дает открытый ключ криптосистемы Гольдвассера – Микали . а также основанная на идентичности схема Cocks, .

См. также

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