factorint(1)

NAME

factorint - factorizes big integers

SYNOPSIS

factorint [options] numbers...

DESCRIPTION

The factorint program is similar to the classic factor(6) utility (game?), but can work on much larger numbers. It factorizes the numbers given on the command line or on standard input, and prints the results on standard output, one factorization per line.

Since factorint uses probabilistic methods, both to test primality and to find prime factors, it is not guaranteed that the numbers appearing in the factorization are prime, although it's very likely. The prime factors can appear in any order, but most of the time they will appear in ascending order. It is even not guaranteed that the program will terminate.

If called with the -t (or --test-prime) option, factorint will apply the Rabin-Miller test several times (the default is to do 5 tests, but this can be changed with the --pp-tests option), and report either "prime" or "composite" on standard output. If factorint writes "composite", the number is guaranteed to be composite. If it writes "prime", the answer might be false; it's unlikely, though.

If called with the -1 (or --one-factor) option, factorint will simply look for one prime divisor, and write it on standard output. Otherwise, factorint will look for a complete factorization of the number, and write it on standard output. On numbers which are known to be composite (as reported by the Rabin-Miller test), factorint will use the following methods, in this order:

(1)

Test small divisors: we check divisibility by two and the following odd numbers. After a fixed number of such divisions, we abandon this method. The default number is 5000, thus all prime factors inferior to 10000 will be found by this method.

(2)

Now we use Pollard's rho method to find factors of moderate size, but with a "timeout" (unless the number is very small, in fact, less than a million). If no factor has been found after some number of loops, we abandon this method and proceed to step (3).

(3)

The number is composite, but its factors are so big that Pollard's method failed to find them in a reasonable time. In this case, we use the Multiple Polynomial Quadratic Sieve to find prime factors. Every time a factor is found, it is removed from the number and we go back to step (2).

Usually, the default parameters chosen by factorint will be good enough, but in some circumstances it can be useful to modify them. For instance, if you know that your number has only very big prime factors, then it is worthwhile to skip step (2) by setting the timeout to zero (loops). On the contrary, if you think it might have a prime factor which is not too big, you may want to increase the timeout.

OPTIONS

-t, --test, --test-prime

Don't factorize the numbers, but just print "prime" or "composite". This is much, much faster for big numbers.

-1, --one, --one-factor

Don't factorize the numbers completely, but just print one prime factor.

-m, --mail

Starts factorint as a background task; the results will be e-mailed to you. This option will be ignored if numbers are read from stdin, instead of being command-line arguments; you can go around this restriction with the xargs(1) utility. Note also that this option implies -n10, for reasons you'll understand easily.

--mailto address

Like above, but allows you to specify any return address. The address will be passed without modification into the "From:" field of the message passed to sendmail(8), so it can even contain multiple recipients.

-n, --nice adjust

Increases your current niceness by adjust. This option has a cumulative effect.

--help, --usage

Prints a small usage summary, and exits successfully.

--version, --copyright

Prints the version number, a small copyright message, and exits successfully. This manpage documents version 0.41.

-q, --quiet

Quiet mode: the "rotating cursor" animation is disabled. See the BUGS section at the end of this manpage.

--small-divisors num

Number of small divisors tested. Default is 5000.

--pseudo-prime-tests, --pp-tests num

Number of pseudo-primality tests. Default is 5.

--pollard-loops num

Sets the timeout for Pollard's rho method. With num loops you should be able to find prime factors up to num^2 roughly. As a special case, a value of -1 means "no limit".

--mpqs-primes num

Sets the size of the factor base for the MPQS algorithm.

--mpqs-interval num

Sets the size of the sieve interval in MPQS. In Silverman's article, the size of the interval is 2M+1.

--mpqs-exponent num

Sets the tolerance exponent to num/1000. This is more or less the number T in Silverman's article.

--mpqs-debug file

Writes debugging information about MPQS into file. This is especially useful when factorizing very big numbers (sixty digits or more) and you'd like to know (a) which parameters the program chose for you, and (b) how things are progressing.

numbers...

A number is any sequence of digits, optionally prefixed with a sign. If no numbers are given on the command line, factorint will read them from standard input (if there are several of them, they must be separated with whitespace).

FILES

/usr/lib/sendmail

The sendmail(8) executable.

/tmp/factors??????

Temporary files used to prepare mails.

EXIT CODE

Non-zero if and only if invalid options are passed on the command line.

BUGS

There is a small probability that the program will never terminate, or return an incomplete factorization, or return "prime" for some composite numbers.

On some terminals without reverse wraparound, like the Linux console, the rotating cursor can cause an optical "glitch" if it happens on the last column on the display: after the character+backspace sequence, the cursor will not return to its previous position, but one character behind; thus, the last character on the screen will be overwritten. You can avoid this with --quiet which disables the rotating cursor.

SEE ALSO

factor(6), induce(1), samuel(1), saml(3), sendmail(8), xargs(1).

AUTHOR

Thierry Bousch ([email protected])