IntegerFactorization(
n ) F
IntegerFactorization
computes the prime factorization of the
integer n. The result is returned as a list of the prime factors.
In case of failure an error is signalled.
The returned factors are considered to be prime by the built-in
probabilistic primality test of GAP
(IsProbablyPrimeInt
, see the Reference Manual),
as in all other factorization routines included in this package.
IntegerFactorization( n )
is equivalent to
FactInt( n : FactIntPartial:=false )[ 1 ]
(see FactInt).
IntegerFactorization
is also installed as a method for Factors
,
with a higher value than the GAP library function FactorsInt
.
gap> IntegerFactorization( Factorial(24) - 1 ); [ 625793187653, 991459181683 ]
gap> Factors( 1459^24 - 1 ); [ 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 5, 7, 13, 73, 97, 193, 283, 337, 1009, 303889, 669433, 1064341, 6722971513, 4531280671081, 313380751265929 ]
FactInt(
n ) F
FactInt
computes the prime factorization of the integer n.
The result is returned as a list of two lists, where the first one
contains the prime factors found, and the second one contains
remaining
unfactored parts of n,
if there are any (if FactIntPartial not set,
this should never happen, because in this case the
function does not return before n is factored completely).
The factors returned as prime factors are considered to be prime
by the build-in probabilistic primality test of GAP
(IsProbablyPrimeInt
, see the Reference Manual).
This also applies to all other factorization routines
provided by this package.
FactInt
recognizes the following options:
Once these option values are set by the user via PushOptions
,
all subsequent factorizations
by FactInt
and IntegerFactorization
(see IntegerFactorization)
are done using these settings without the need
to give further arguments (in respect to the use of the
GAP Options Stack, see the Reference Manual).
Setting RhoSteps, Pminus1Limit1, Pplus1Residues, Pplus1Limit1,
ECMCurves or ECMLimit1 to zero switches the respective method off.
FactInt
chooses defaults for all option values that are
not explicitly set by the user.
The option values are also taken into consideration by the routines for
the particular factorization methods described in the next chapter
when default values have to be chosen.
If |n| < 10^{12}, FactInt
just calls the library function
FactorsInt
, which is guaranteed to give the correct result for
numbers in this range. If not, it checks whether n = b^{k} ±1 for
some b, k and looks for factors corresponding to
polynomial factors of x^{k} ±1 (in order to immediately
obtain factors that do not correspond to polynomial factors
it is necessary to give a list of the prime factors of numbers
of this form as TDHints).
As the first general factorization step, FactInt
does
trial division by the primes below 1000.
After that, it checks whether the remaining
part of the number to be factored already is a prime.
If not, it does trial divisions by some already known primes, using
the list Primes2
(see GAP-Manual).
If there is still an unfactored part m, then it checks whether m
is a non-trivial power of an integer.
Then, the additional list of trial divisors given
as TDHints is processed, if present.
After the small and other ``easy'' factors have been casted out
this way, FactInt
searches for ``medium-sized'' factors using
Pollard's Rho (by the library function FactorsRho
,
see GAP-Manual),
Pollard's p-1 (see FactorsPminus1), Williams' p+1
(see FactorsPplus1) and the Elliptic Curves Method
(ECM, see FactorsECM) in this order.
After that, if there is still an unfactored part remaining and
FactIntPartial = false (or the remaining composites do not
exceed the bound given by CFRACLimit resp. MPQSLimit),
one of the factor base methods (CFRAC, see FactorsCFRAC or
MPQS, see FactorsMPQS) is used to do the ``hard work'', depending
on the value of FBMethod, which could be "MPQS"
or "CFRAC"
.
Finally, it is checked whether the product of all factors
is equal to n and whether all factors in the first list of the
result pass the GAP pseudoprime test IsProbablyPrimeInt
and all factors in the second list are really composites.
These checks are also done by all other factorization routines
provided by this package.
gap> FactInt( Factorial(39) + 1 : RhoSteps := 16384, Pminus1Limit1 := 100000, Pplus1Limit1 := 2000, ECMLimit1 := 5000, ECMCurves := 10, FBMethod := "MPQS" ); [ [ 79, 57554485363, 146102648914939, 30705821478100704367 ], [ ] ]
[Up] [Previous] [Next] [Index]
FactInt manual