Субэкспоненциальные алгоритмы

Экспоненциальные алгоритмы

1. Алгоритм Шенкса (алгоритм больших и малых шагов).

2. Алгоритм Силвера – Полига-Хеллмана – работает, если известна факторизация числа .

3. -метод Полларда.

Их временная сложность

,

где ; . Эффективность алгоритма зависит от того, насколько и .

1. Алгоритм Адлемана (1979 г.), сложность .

2. Алгоритм COS (1986 г.), сложность авторов Копперсміта, Одлыжко и Шреппеля. В 1991 г. с его помощью выполнено логарифмирование по модулю , в 1997 г. – по модулю . Доказано, что при алгоритм COS лучше решета числового поля.

3. алгоритм решета числового поля, разработанный Широкауэром и др. (при модуле ), временная сложность .

Дата добавления: 2014-01-07