Сначала я отвечу на ваш вопрос (у которого есть довольно простой ответ, который может вас разочаровать), прежде чем обсуждать небольшое расширение вашей проблемы, которую мы считаем квантовыми компьютерами. не можем решить, что может вас заинтересовать.
В качестве быстрого примечания к комментарию
По крайней мере, в случае факторинга, если $\log_2(p)=\log_2(q)=\log_2(k)$ тогда решение уравнения является информационно-теоретически невозможным, так как это в основном одноразовый блокнот.
Как правило, это делается так: противник побеждает, если восстанавливается. Любые решение $х^2+у^2\bmod k$, а не какое-то конкретное решение.
Это можно увидеть в таких вещах, как
- последовательная игра восстановления ключа (а не игра восстановления целевого ключа) и
- как односторонние функции должны восстанавливать любой прообраз $у$, например Любые $х$ такой, что $f(х) = у$, а не какое-то "точное" $х'$ который выбирается внутренне во время игры.
Я буду описывать вещи в этих терминах, так как это стандартно.
Если это не подходит для вашего приложения, вам, возможно, следует попытаться описать свое приложение подробнее.
Этот вопрос прост: может ли алгоритм Шора решить эти уравнения за полиномиальное время, если они выполняются с конечной арифметикой, а не над целыми числами?
Насколько я понимаю, алгоритм Шора описывается более $\mathbb{Z}$ скорее, чем $\mathbb{Z}_n$ не является серьезной проблемой с его реализацией в «реальном мире». В частности, хотя нужно быть осторожным, чтобы представления с конечной точностью, с которыми вы работаете, не были слишком «с потерями», я понимаю, что эти детали гораздо легче проработать, чем такие вещи, как создание квантового компьютера.
При условии, что это понимание правильное, ответ на оба эти вопроса примерно тривиален — решить различные уравнения по $\mathbb{Z}$, а затем сократить ответы $\bmod k$ получать решения по $\mathbb{Z}_k$. Как отмечает пончо в комментариях, проблема решения $n = xy\bmod k$ за $х, у$ даже классически легко, так что мораль этой истории в том, что наложение модульных ограничений может (возможно) значительно упростить задачи, но для этих задач они не усложняют задачи.
Существует мягкое расширение проблемы решения для $n = ху \bmod k$ который считается квантово-трудным.
Решение этой конгруэнтности можно рассматривать как решение линейного уравнения с одной переменной (точное).
Есть два естественных способа обобщить это
- более одной переменной и
- более одного уравнения.
Например, измените задачу на ту, где она указана $\vec b = A\vec s\bmod k$ куда $\vec b\in\mathbb{Z}_k^n, A\in\mathbb{Z}_k^{n\times n}, \vec s\in\mathbb{Z}_k^n$.
Это по-прежнему тривиально для «решения», хотя --- если вы выберете $А$ быть единичной матрицей, то $\vec s = \vec b$ работает.
В более общем случае, если вы выберете $А$ быть обратимым над $\mathbb{Z}_k$, тогда $\vec s = \vec A^{-1}\vec b$ работает.
Даже если $\vec А$ является необратимым (скажем, не квадратным), есть вещи, которые вы можете сделать, используя общие методы линейной алгебры.
Все это и действенно, и классически, т.е. Шор все равно перебор.
Как правило, останавливать вышеуказанные атаки можно двумя способами.
укажите некоторую матрицу $А$ необходимо использовать (поэтому нельзя установить $А$ быть тождеством или случайной обратимой матрицей), и
добавить немного шума в проблему.
Обратите внимание, что одного первого пункта достаточно (атака Пончо все еще работает), поэтому второй пункт следует рассматривать как фундаментальный.
Конкретно проблема в следующем
Обучение с ошибками: Позволять $A\in\mathbb{Z}_k^{n\times n}$ равномерно случайна, и пусть $\vec s\in\mathbb{Z}_k^n$ быть "секретным" вектором.
Для фиксированной раздачи $\чи$ поддерживается на $\mathbb{Z}_k$, мы говорим обучение поиску с ошибками проблема в том, чтобы восстановить $\vec с$, данный $(A, A\vec s + \vec e)$, куда $\vec e \gets\chi^n$.
В зависимости от параметризации проблема LWE является одним из главных кандидатов на допущение о жесткости, безопасное для квантовых компьютеров.
Это означает, что для подходящего обобщения решения $n \эквив xy\bmod k$, считается, что алгоритм Шора не можем решать проблему.
Однако, как видно выше, обобщение на много шагов удалено от вашей первоначальной проблемы.
Есть и другие подобные обобщения в этом направлении (задача Learning Parity with Noise или проблема Approximate GCD) --- принципиальное сходство со всеми из них состоит в том, что у вас есть какой-то "зашумленный" вариант линейной задачи.
Кроме того, существует обобщение $х^2+у^2\bmod k$ проблема, которая считается квантово-безопасной, но я не знаю столько подробностей, поэтому буду писать меньше.
Грубо говоря, можно заменить квадратичный многочлен $f(x, y) = x^2+y^2\bmod k$ с произвольный квадратичный многочлен (или набор многочленов) в $n$ переменные.
Тогда проблема восстановления $(x_1,\точки, x_n)$ которые являются (одновременными) нулями многомерных квадратных многочленов $p_0, \dots,p_m$ (примерно) связано со взломом «многовариантных криптосистем».
Обратите внимание, что настойчивое требование восстанавливать нули многочленов (а не $p(x_0,\dots,x_n) = N$, как вы просите) не теряет общности, так как это можно восстановить, взглянув на ноль $p(x_0,\dots,x_n) - N$.
Это все, чтобы сказать, что
- Считается, что Шор решит обе ваши проблемы, но
- есть обобщения обеих ваших проблем, которые считаются квантово-безопасными. На самом деле, многие из «ведущих» квантово-безопасных гипотез (все, что я знаю, кроме изогении и ранг-метрического кодирования) можно рассматривать как обобщение ваших проблем.
