.\" Copyright 1995,96 Thierry Bousch
.\" Licensed under the Gnu Public License, Version 2
.\"
.\" $Id: factorint.1,v 2.2 1996/06/01 09:20:15 bousch Exp $
.\"
.TH FACTORINT 1 "June 1996" "SAML"
.SH NAME
factorint \- factorizes big integers
.SH SYNOPSIS
.B factorint
.RI [ options ]
.IR numbers ...
.SH DESCRIPTION
The \fBfactorint\fR program is similar to the classic \fBfactor\fR(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.
.PP
Since \fBfactorint\fR 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.
.PP
If called with the \fB\-t\fR (or \fB\-\-test\-prime\fR) option,
\fBfactorint\fR will apply the Rabin-Miller test several times (the
default is to do 5 tests, but this can be changed with the
\fB\-\-pp\-tests\fR option), and report either "prime" or "composite" on
standard output. If \fBfactorint\fR writes "composite", the number is
guaranteed to be composite. If it writes "prime", the answer might
be false; it's unlikely, though.
.PP
If called with the \fB\-1\fR (or \fB\-\-one\-factor\fR) option,
\fBfactorint\fR will simply look for one prime divisor, and write it on
standard output. Otherwise, \fBfactorint\fR 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), \fBfactorint\fR will use the following methods,
in this order:
.IP (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.
.IP (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).
.IP (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).
.PP
Usually, the default parameters chosen by \fBfactorint\fR 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.
.SH OPTIONS
.TP
.BR \-t ", " \-\-test ", " \-\-test\-prime
Don't factorize the numbers, but just print "prime" or "composite".
This is much, much faster for big numbers.
.TP
.BR \-1 ", " \-\-one ", " \-\-one\-factor
Don't factorize the numbers completely, but just print one prime factor.
.TP
.BR \-m ", " \-\-mail
Starts \fBfactorint\fR 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 \fBxargs\fR(1) utility. Note also that this option implies
\fB\-n\fI10\fR, for reasons you'll understand easily.
.TP
.BI \-\-mailto " address"
Like above, but allows you to specify any return address. The \fIaddress\fR
will be passed without modification into the "From:" field of the message
passed to \fBsendmail\fR(8), so it can even contain multiple recipients.
.TP
.BR \-n ", " \-\-nice "\fI adjust"
Increases your current niceness by \fIadjust\fR. This option has a
cumulative effect.
.TP
.BR \-\-help ", " \-\-usage
Prints a small usage summary, and exits successfully.
.TP
.BR \-\-version ", " \-\-copyright
Prints the version number, a small copyright message, and exits
successfully. This manpage documents version 0.41.
.TP
.BR \-q ", " \-\-quiet
Quiet mode: the "rotating cursor" animation is disabled. See the BUGS section
at the end of this manpage.
.TP
.BI \-\-small\-divisors " num"
Number of small divisors tested. Default is 5000.
.TP
.BR \-\-pseudo\-prime\-tests ", " \-\-pp\-tests "\fI num"
Number of pseudo-primality tests. Default is 5.
.TP
.BI \-\-pollard\-loops " num"
Sets the timeout for Pollard's rho method. With \fInum\fR loops you should
be able to find prime factors up to \fInum\fR^2 roughly. As a special case,
a value of \fI\-1\fR means "no limit".
.TP
.BI \-\-mpqs\-primes " num"
Sets the size of the factor base for the MPQS algorithm.
.TP
.BI \-\-mpqs\-interval " num"
Sets the size of the sieve interval in MPQS. In Silverman's article, the
size of the interval is 2M+1.
.TP
.BI \-\-mpqs-exponent " num"
Sets the tolerance exponent to \fInum\fR/1000. This is more or less the
number T in Silverman's article.
.TP
.BI \-\-mpqs-debug " file"
Writes debugging information about MPQS into \fIfile\fR. 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.
.TP
.IR numbers ...
A number is any sequence of digits, optionally prefixed with a sign. If no
numbers are given on the command line, \fBfactorint\fR
will read them from standard input (if there are several of them, they must
be separated with whitespace).
.SH FILES
.TP
.I /usr/lib/sendmail
The \fBsendmail\fR(8) executable.
.TP
.I /tmp/factors??????
Temporary files used to prepare mails.
.SH "EXIT CODE"
Non-zero if and only if invalid options are passed on the command line.
.SH BUGS
There is a small probability that the program will never terminate, or
return an incomplete factorization, or return "prime" for some composite
numbers.
.PP
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 \fB\-\-quiet\fR which disables the rotating cursor.
.SH "SEE ALSO"
\fBfactor\fR(6), \fBinduce\fR(1), \fBsamuel\fR(1), \fBsaml\fR(3),
\fBsendmail\fR(8), \fBxargs\fR(1).
.SH AUTHOR
Thierry Bousch (bousch@topo.math.u\-psud.fr)