Не буду вдаваться в подробности шифрования данных в интернете, так как не шарю. Для сегодняшнего поста нам достаточно знать, что используемые обычно алгоритмы в своей основе используют простой механизм: если взять два очень больших простых числа и умножить друг на друга, то по результату невозможно узнать исходные числа. Или возможно?
В попытке распутать клубок первым откровением стал следующий факт: не доказано, что разложение числа на простые множители не является P-задачей. Обезьяны всего лишь не додумались до классического алгоритма, умеющего делать это за логарифм. Зато господин Шор придумал, как её можно решить за логарифм на квантовом компьютере.
Допустим, мы ищем множители у N. Возьмём случайное число k. Оно, конечно, не является тем самым искомым числом, а значит, взаимно простое с N. Начнём возводить k во всё большую и большую степень и брать остаток от деления на N. К примеру, если N=15, k=2, то будет 2,4,8,1,2,….
Так вот, этот ряд обязательно рано или поздно зациклится, но, прежде чем вернуться в k, он должен за шаг до этого дойти до 1.
Значит, для какого-то p будет верно
k^p = m*N+1. Следовательно (переносим 1 и раскладываем как разность квадратов):(k^p/2 - 1)(k^p/2 + 1) = m * NС вероятностью 37.5% (trust me bro) p будет чётным, а ещё одна скобка будет делиться на одно из исходных чисел, а другая на другое.
Таким образом, задача сводится к нахождению периода у последовательности остатков от деления на N степеней k. На обычных компах мы не умеем понять, когда этот ряд зациклится, и только в этот момент в игру вступает квантовый компьютер.
К сожалению, между сверхупрощением и 6-часовой лекцией я не смог найти золотой середины на просторах интернета. Сейчас я установлю рекорд по отуплению этого алгоритма.
В своём прошлом квантовом посте я рассказывал, что квантовый компьютер оперирует векторами в пространстве 2^N, где N - количество кубитов. Если задать вектор, «соответствующий» последовательности этих остатков и применить так называемый Quantum Fourier Transform, то вжух 💨 - и мы узнаем период этого ряда.
Как же меня совесть не мучает за такое объяснение? Всё просто.
Нахождение периода функции - это не задача перебора, которую квантовый компьютер решает магическим образом, «параллельно проверяя все варианты». Это очень сложная, но всего лишь последовательность операций над векторами.
Лично у меня возникло весьма жирное подозрение, что и классический алгоритм существует. Может, в P != NP я ещё готов поверить, но тут есть red flag, любезно найденный господином Шором.
Ссылки на материалы для интересующихся:
1) 20минутка
2) первая из 6 лекций, которые я не стал смотреть
3) пост от квантового чувачка, у него там еще свои ссылки
Надеюсь, ASI выложит в интернет алгоритм разложения для обычных компов. Чисто по ржать. Переход на постквантовую криптографию не спасёт, так как застрянет в бэклоге.
@knowledge_accumulator