Русская Википедия:Детерминированный алгоритм факторизации Ленстры

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

Шаблон:Hider

Примечания

Шаблон:Примечания

Литература