Каков алгоритм, лежащий в основе команды factor в linux?

Ответ 1

Руководство Gnu coreutils сообщает, что используется алгоритм Полларда rho.

http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html

Ответ 2

Здесь приведен пример одной версии источника для коэффициента GNU:

http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c

Он включает подпрограммы как для пробного деления, так и для Полларда rho. Похоже на быстрый просмотр, как если бы он использовал пробное деление, чтобы найти некоторые небольшие факторы (примерно до lg(n)^2, что в этом случае составляет около 4000), а затем Поллард, если то, что осталось, не является, вероятно, простым. В этом случае 205432623008947, если я прав около 4000, т.е. 35129 * 5847949643.

Второй по величине простой коэффициент в вашем примере - 35129, а квадратный корень самого большого - около 76471. Таким образом, одно только пробное деление было бы быстрым, так как ему нужно было попробовать только около 25 тысяч кандидатов.