Квантовый алгоритм факторизации: различия между версиями
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Каждое целое положительное число n имеет единственное разложение…») |
KVN (обсуждение | вклад) |
||
| (не показано 6 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Каждое целое положительное число n | Каждое целое положительное число n может быть единственным образом разложено в виде произведения простых чисел <math>n = p^{e_1}_1 \cdots p^{e_k}_k</math>, состоящего из простых чисел <math>p_i</math> и целых положительных показателей степени <math>e_i</math>. Вычисление разложения <math>p_1, e_1, ..., p_k, e_k</math> заданного числа n представляет собой задачу факторизации. | ||
Факторизация изучалась многие сотни лет, и для нее были найдены алгоритмы с экспоненциальным временем выполнения, включая перебор делителей, метод Лемана, | Факторизация изучалась многие сотни лет, и для нее были найдены алгоритмы с экспоненциальным временем выполнения, включая перебор делителей, метод Лемана, <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. Шор предложил квантовый алгоритм факторизации с полиномиальным временем выполнения. | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1 [2, 3]. Существует классический субэкспоненциальный алгоритм, который факторизует целое число n за время exp(c( | '''Теорема 1 [2, 3]. Существует классический субэкспоненциальный алгоритм, который факторизует целое число n за время <math>exp(c(log \; n)^{1/3}(log \; log \; n)^{2/3})</math>.''' | ||
Теорема 2 [6]. Существует полиномиальный по времени квантовый алгоритм, выполняющий разложение целых чисел. Алгоритм факторизует число n за время O((log n)2 (log | '''Теорема 2 [6]. Существует полиномиальный по времени квантовый алгоритм, выполняющий разложение целых чисел. Алгоритм факторизует число n за время <math>O((log \; n)^2 (log \; n \; log \; n)(log \; log\; log \; n))</math> с добавлением времени постобработки (полиномиального относительно log n), которая может быть выполнена классическим образом.''' | ||
== Применение == | == Применение == | ||
[[Труднорешаемая задача|Труднорешаемые задачи]] теории чисел нашли применение в криптографических системах с открытым ключом. Криптосистема RSA с открытым ключом, также как и другие, основывается на том, что факторизация не имеет эффективного алгоритма. Наиболее известные классические алгоритмы факторизации | [[Труднорешаемая задача|Труднорешаемые задачи]] теории чисел нашли применение в криптографических системах с открытым ключом. Криптосистема RSA с открытым ключом, также как и другие, основывается на том, что факторизация не имеет эффективного алгоритма. Наиболее известные классические алгоритмы факторизации способны помочь определить, насколько безопасна криптосистема и какой размер ключа следует выбрать. Квантовый алгоритм Шора для факторизации может взломать эти системы за полиномиальное время с помощью квантового компьютера. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Вопрос о том, существует ли классический алгоритм факторизации с полиномиальным временем выполнения, остается открытым. Существуют задачи сложнее факторизации, такие как нахождение единичной группы числового поля произвольной степени, для которых пока не | Вопрос о том, существует ли классический алгоритм факторизации с полиномиальным временем выполнения, остается открытым. Существуют задачи сложнее факторизации, такие как нахождение единичной группы числового поля произвольной степени, для которых пока не обнаружено эффективных квантовых алгоритмов. | ||
== См. также == | == См. также == | ||
| Строка 36: | Строка 36: | ||
6. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26,1484-1509 (1997) | 6. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26,1484-1509 (1997) | ||
[[Категория: Совместное определение связанных терминов]] | |||
Текущая версия от 11:53, 7 декабря 2024
Постановка задачи
Каждое целое положительное число 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 представляет собой задачу факторизации.
Факторизация изучалась многие сотни лет, и для нее были найдены алгоритмы с экспоненциальным временем выполнения, включая перебор делителей, метод Лемана, [math]\displaystyle{ \rho }[/math]-алгоритм Полларда и метод группы классов Шенкса [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)