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

Факторизация изучалась многие сотни лет, и для нее были найдены алгоритмы с экспоненциальным временем выполнения, включая перебор делителей, метод Лемана, <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. Шор предложил квантовый алгоритм факторизации с полиномиальным временем выполнения.