Детерминированный алгоритм факторизации Ленстры

Детерминированный алгоритм факторизации Ленстры Сложность $O(n^{1/3}{\log }^{2}n)$.

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

Литература

• Шаблон:Source