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

Каждое целое положительное число n имеет единственное разложение в виде произведения простых чисел n = p1 e ■ ■ ■ pekk, состоящего из простых чисел pi и целых положительных показателей степени ei. Вычисление разложения p1; e1... ; pk; ek из n представляет собой задачу факторизации.

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

[[Труднорешаемая задача|Труднорешаемые задачи]] теории чисел нашли применение в криптографических системах с открытым ключом. Криптосистема RSA с открытым ключом, также как и другие, основывается на том, что факторизация не имеет эффективного алгоритма. Наиболее известные классические алгоритмы факторизации могут помочь определить, насколько безопасна криптосистема и какой размер ключа следует выбрать. Квантовый алгоритм Шора для факторизации может взломать эти системы за полиномиальное время с помощью квантового компьютера.

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