Новости криптовалют
Что такое алгоритм Шора? Квантовый алгоритм, способный за секунды раскладывать большие числа на простые множители и решать задачу дискретного логарифма. На сложности этих двух задач основана значительная часть современной асимметричной криптографии (с открытым ключом): RSA, протокол Диффи — Хеллмана, ECDSA и подписи Шнорра. Для классического компьютера эти задачи практически нерешаемы при достаточной длине ключа.
Лучший традиционный метод — метод решета числового поля — требует субэкспоненциального времени. Например, взлом ключа RSA-2048 занял бы миллиарды лет, а алгоритм Шора решает эту же задачу за полиномиальное время. Алгоритм стал одним из ключевых результатов ранней истории квантовых вычислений.
Он показал, что достаточно мощная квантовая машина сможет эффективно решать задачи, на сложности которых основаны широко используемые криптографические системы. Кто и когда его придумал? Математик Питер Шор из Bell Labs в 1994 году. До этого квантовые вычисления уже существовали как теоретическое направление, но у них не было столь убедительного применения для решения практически значимой задачи.
Работа Шора показала, что достаточно мощный квантовый компьютер сможет взламывать целый ряд криптографических систем с открытым ключом, включая RSA и криптографию на эллиптических кривых. Это стало одним из главных стимулов для развития квантовых вычислений и впоследствии — для создания постквантовой криптографии, устойчивой к таким атакам. Как работает алгоритм Шора?
Задача факторизации (разложения числа на множители) сводится к поиску периода специальной функции. Классический компьютер тратит на этот поиск слишком много времени. Квантовый компьютер создает суперпозицию множества возможных состояний, а затем с помощью интерференции и квантового преобразования Фурье выделяет периодическую структуру функции.
После измерения и классической обработки из нее можно получить множители числа или решить задачу дискретного логарифма.
