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

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

Теорема 1 [2, 3]. Существует классический субэкспоненциальный алгоритм, который факторизует целое число n за время exp(c(logn)1/3(loglogn)2/3).

Теорема 2 [6]. Существует полиномиальный по времени квантовый алгоритм, выполняющий разложение целых чисел. Алгоритм факторизует число n за время O((log n)2 (log nlog n)(logloglog n)) с добавлением полиномиальной относительно log n постобработки, которая может быть выполнена классическим образом.