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

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

Каждое целое положительное число n может быть единственным образом разложено в виде произведения простых чисел [math]\displaystyle{ n = p^{e_1}_1 \cdots p^{e_k}_k }[/math], состоящего из простых чисел [math]\displaystyle{ p_i }[/math] и целых положительных показателей степени [math]\displaystyle{ e_i }[/math]. Вычисление разложения [math]\displaystyle{ p_1, e_1, ..., p_k, e_k }[/math] заданного числа n представляет собой задачу факторизации.

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

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

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

Теорема 2 [6]. Существует полиномиальный по времени квантовый алгоритм, выполняющий разложение целых чисел. Алгоритм факторизует число n за время [math]\displaystyle{ O((log \; n)^2 (log \; n \; log \; n)(log \; log\; log \; n)) }[/math] с добавлением времени постобработки (полиномиального относительно 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)