factor-Befehl druckt die Primfaktoren der angegebenen Ganzzahl NUMBER.Was ist der Algorithmus hinter dem Faktor-Befehl in Linux?
, wenn ich es versucht
factor 12345678912345678912
auch für solche großen Zahlen, kommt es innerhalb von Mühlen.
Welchen Algorithmus verwendet es?
Das Handbuch von Gnu Coreutils informiert, dass Pollard's rho algorithm verwendet wird.
http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html
Hier ist ein Beispiel für eine Version der Quelle für GNU Faktor:
http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c
Es umfasst Routinen sowohl für Probedivision und Pollard rho. Sieht mir bei einem kurzen Scan so an, als ob es bei der Trial Division einige kleine Faktoren findet (bis etwa lg(n)^2, was in diesem Fall etwa 4000 ist), dann ist Pollard, wenn was übrig bleibt, wohl nicht-Prime. In diesem Fall ist das 205432623008947, wenn ich recht über die 4000 bin, d. H. 35129 * 5847949643. Der zweitgrößte Primfaktor in Ihrem Beispiel ist 35129 und die Quadratwurzel des größten ist um 76471. Die Trial Division allein wäre also schnell, da sie nur 25.000 Kandidaten probiert.