# Алгоритм Шора: как квантовые компьютеры взломают шифрование?

Источник: https://www.youtube.com/watch?v=k_kyepATqB8
Канал: Computerphile
Опубликовано: 09.07.2026

---

## Взлом RSA: как алгоритм Шора меняет правила игры
[[JUMP:0:00]]

Алгоритм Шора представляет собой теоретически мощный квантовый метод факторизации целых чисел, способный подорвать основы современных систем шифрования. В этом выпуске Computerphile эксперты разбирают, как классическая математика и квантовая физика объединяются для решения задачи, которая заняла бы у обычных компьютеров миллионы лет. Ведущий Майк объясняет классическую часть алгоритма, а физик Фил показывает, как квантовые состояния и интерференция волн позволяют находить периоды функций с невероятной эффективностью.

### Классический фундамент: задача RSA и поиск периода
[[JUMP:1:03]]

Алгоритм RSA является одним из самых известных методов асимметричного шифрования, используемым для цифровых подписей и сертификатов в интернете. Его надежность базируется на вычислительной сложности задачи факторизации целых чисел: если у вас есть открытый ключ, содержащий огромное число $N$, состоящее из произведения двух секретных простых чисел $P$ и $Q$, получить эти $P$ и $Q$ практически невозможно.

Майк отмечает, что вместо прямого подбора $P$ и $Q$, алгоритм Шора переформулирует задачу:

* Создается функция, которая периодически возвращает значение 1 (модульная экспоненция).
* Задача сводится к поиску периода $R$ этой функции.
* Зная $R$, можно использовать разность квадратов, чтобы вычислить наибольший общий делитель и «извлечь» $P$ и $Q$.

Хотя для числа 15 (где $N=15$, $A=2$) период $R=4$ легко найти вручную, для реальных ключей RSA размером 2000 бит классический компьютер вынужден перебирать колоссальное пространство вариантов.

### Квантовая магия: преобразование Фурье и интерференция
[[JUMP:11:40]]

По словам Фила, квантовая часть алгоритма Шора — это элегантное использование принципа периодичности. Физика, от кристаллографии до изучения космического микроволнового фона, строится на разложении сложных паттернов в сумму простых волн — это и есть суть преобразования Фурье.

* **Преобразование Фурье:** процесс, при котором сложный сигнал разбивается на сумму синусоид и косинусоид.
* **Интерференция:** ключ к работе квантового компьютера заключается в управлении фазой волн, чтобы добиваться конструктивной (усиление) или деструктивной (подавление) интерференции.
* **Кубиты:** в ловушках ионов квантовые состояния (0 и 1) представляются в виде суперпозиции. Используя микроволновые импульсы, ученые могут контролировать вероятность нахождения системы в конкретном состоянии.

Фил подчеркивает, что квантовые вычисления — это не «магия параллельных вселенных», а строгая работа с интерференцией волн в рамках нашей одной вселенной.

### Практическая реализация и вызовы будущего
[[JUMP:36:47]]

На текущий момент квантовые компьютеры остаются шумными и хрупкими системами, требующими героических инженерных усилий для изоляции от внешней среды (ультравысокий вакуум, экстремально низкие температуры).

* **Главная проблема:** взаимодействие с окружающей средой приводит к потере квантовости («размытию» фазы).
* **Прогнозы:** хотя сегодня удается факторизовать лишь очень малые числа, развитие технологий может сделать взлом RSA возможным в течение 20–30 лет, хотя эксперты не исключают и гораздо более долгие сроки.

Оба спикера сходятся во мнении, что, несмотря на сложность, квантовая механика предлагает путь, где решение задачи не требует перебора всех вариантов, а «выскакивает» само в процессе анализа спектра частот.