Я наткнулся на алгоритм Шора (который решает следующую задачу: «Дано целое число N, найти его простые множители»).
Фактически алгоритм Шора решает задачу «дана периодическая функция $ф$, то есть если $\underbrace{f(f(... f(a))...)}_{k\text{times}} = a$, что такое $к$?"
Указав $ф$ разумно, мы можем использовать это, чтобы решить проблему факторизации. Я отмечаю это, потому что его можно использовать и для решения других интересных задач.
В любом случае, что вы на самом деле спрашиваете, так это «если мы можем факторизовать ключ, как это поможет нам взломать RSA»? Обратите внимание, что, полагаясь на сложность факторизации, от чего зависит RSA; другие методы (например, Диффи-Хеллмана) в равной степени уязвимы для алгоритма Шора, но они используют другой $ф$ функция.
Ну, с RSA, публичным экспонентом $е$ и частный показатель $д$ связаны $e \cdot d \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$. Оказывается, если мы знаем простые множители $р, д$ и мы знаем общественный показатель $е$ (который дан в открытом ключе), легко вычислить закрытый показатель степени $д$; что немедленно дает нам способ расшифровать через $P = C^d \bmod n$.
