4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 3: | Строка 3: | ||
Факторизация изучалась многие сотни лет, и для нее были найдены алгоритмы с экспоненциальным временем выполнения, включая перебор делителей, метод Лемана, <math>\rho</math>-алгоритм Полларда и метод группы классов Шенкса [1]. С изобретением криптографического алгоритма RSA с открытым ключом в конце семидесятых годов эта задача приобрела практическую значимость и стала привлекать гораздо больше внимания. Безопасность RSA тесно связана со сложностью факторизации; | Факторизация изучалась многие сотни лет, и для нее были найдены алгоритмы с экспоненциальным временем выполнения, включая перебор делителей, метод Лемана, <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. Шор предложил квантовый алгоритм факторизации с полиномиальным временем выполнения. | ||
== Основные результаты == | == Основные результаты == |
правка