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