Квантовый алгоритм факторизации: различия между версиями

Перейти к навигации Перейти к поиску
м
Строка 3: Строка 3:




Факторизация изучалась многие сотни лет, и для нее были найдены алгоритмы с экспоненциальным временем выполнения, включая перебор делителей, метод Лемана, <math>\rho</math>-алгоритм Полларда и метод группы классов Шенкса [1]. С изобретением криптографического алгоритма RSA с открытым ключом в конце семидесятых годов эта задача приобрела практическую значимость и стала привлекать гораздо больше внимания. Безопасность RSA тесно связана со сложностью факторизации; в частности, она безопасна только в том случае, если не имеется эффективного алгоритма факторизации. Первый алгоритм с субэкспоненциальным временем был предложен Моррисоном и Бриллхартом [4] и использует метод непрерывных дробей. За ним последовали метод квадратичного решета Померанца и метод эллиптических кривых Ленстры [5]. Метод решета числового поля [2, 3], представленный в 1989 году, является самым известным классическим алгоритмом факторизации и работает за время <math>exp(c(log \; n)^{1/3}(log \; log \; n)^{2/3})</math> для некоторой постоянной c. Шор предложил квантовый алгоритм факторизации с полиномиальным временем выполнения.
Факторизация изучалась многие сотни лет, и для нее были найдены алгоритмы с экспоненциальным временем выполнения, включая перебор делителей, метод Лемана, <math>\rho</math>-алгоритм Полларда и метод группы классов Шенкса [1]. С изобретением криптографического алгоритма RSA с открытым ключом в конце семидесятых годов эта задача приобрела практическую значимость и стала привлекать гораздо больше внимания. Безопасность RSA тесно связана со сложностью факторизации; точнее говоря, эта система криптографии безопасна только в том случае, если не имеется эффективного алгоритма факторизации. Первый алгоритм с субэкспоненциальным временем был предложен Моррисоном и Бриллхартом [4]; он использует метод непрерывных дробей. За ним последовали метод квадратичного решета Померанца и метод эллиптических кривых Ленстры [5]. Метод решета числового поля [2, 3], представленный в 1989 году, является самым известным классическим алгоритмом факторизации и работает за время <math>exp(c(log \; n)^{1/3}(log \; log \; n)^{2/3})</math> для некоторой постоянной c. Шор предложил квантовый алгоритм факторизации с полиномиальным временем выполнения.


== Основные результаты ==
== Основные результаты ==
4551

правка

Навигация