Il comando fattore stampa i fattori primi del numero intero specificato NUMERO.qual è l'algoritmo dietro il comando factor in linux?
quando ho provato
factor 12345678912345678912
anche per tali grandi numeri, risultati nel mulini.
quale algoritmo sta utilizzando?
Il manuale di Gnu coreutils informa che è in uso Pollard's rho algorithm.
http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html
Ecco un esempio di una versione della fonte per il fattore GNU:
http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c
Esso include routine sia per la divisione prova e rho di Pollard. Mi guarda su una scansione veloce come se utilizzasse la divisione di prova per trovare alcuni piccoli fattori (fino a circa lg(n)^2, che è circa 4000 in questo caso), quindi Pollard se ciò che è rimasto non è probabilmente-primo. In questo caso è 205432623008947 se ho ragione circa il 4000, ovvero 35129 * 5847949643.
Il secondo fattore primo principale nell'esempio è 35129 e la radice quadrata del più grande è intorno a 76471. Quindi la divisione di prova da sola sarebbe veloce, dal momento che deve solo provare circa 25 mila candidati.