Квантовый алгоритм факторизации

Постановка задачи

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

Открытые вопросы

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

См. также

• Квантовый алгоритм для решения задачи дискретного логарифмирования
• Квантовые алгоритмы для группы классов числового поля
• Квантовый алгоритм для решения уравнения Пелля

Литература

1. Cohen, H.: A course in computational algebraic number theory. Graduate Texts in Mathematics, vol. 138. Springer (1993)

2. Lenstra, A., Lenstra, H. (eds.): The Development of the Number Field Sieve. Lecture Notes in Mathematics, vol. 1544. Springer (1993)

3. Lenstra, A.K., Lenstra, H.W. Jr., Manasse, M.S., Pollard, J.M.: The number field sieve. In: Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, Baltimore, Maryland, 14-16 May 1990, pp. 564-572

4. Morrison, M., Brillhart, J.: A method of factoring and the factorization of F7

5. Pomerance, C.: Factoring. In: Pomerance, C. (ed.) Cryptology and Computational Number Theory, Proceedings of Symposia in Applied Mathematics, vol. 42, p. 27. American Mathematical Society

6. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26,1484-1509 (1997)