Dear Members of the GAP Forum

FactInt is a new GAP 4 share package developed by Stefan Kohl at the
University of Stuttgart. It implements the following algorithms for
factoring integers:

Pollard's p-1 method
Williams' p+1 method
Brillhart-Morrison's continued fraction method (CFRAC)
Lenstra's elliptic curve method (ECM)
Pomerance's quadratic sieve method (MPQS)

The first two methods are useful for finding factors p such that
all prime factors of p-1 resp. p+1 are 'small',
e.g. smaller than 1000000.

CFRAC is historically the predecessor of the MPQS (see below).

The ECM - routine is - roughly spoken - capable of finding
factors of about 15 digits in some minutes, factors of about 20 digits
in some hours and factors of about 25 digits in some days on a
'usual' PC, when the number to be factored has got roughly
about 100 decimal digits.
The expected time needed to find a factor of a given size is
proportional to the square of the number of digits of the input number.

The MPQS - routine is capable of factoring an arbitrary integer of

- 40 digits in about 2 min.,
- 50 digits in about 20 min.,
- 60 digits in about 3 h,
- 70 digits in about 30 h

on a Pentium 200, where the timings may vary by a factor of 2 or 3.

These are all only 'probabilistic' methods, and especially the time
needed for ECM depends highly on the actual - good or bad - luck.

The package provides a general factorization function which uses
an appropriate combination of the mentioned methods to reach
a good average performance for 'arbitrary' integers.
Using this function, it is for example possible to factor a number
with factors of, let's say, 15, 18, 20, 22, 26, 34 and 36 digits
(and maybe several smaller ones) in a 'reasonable' amount of time,
where the small factors are 'thrown out' first, then the ECM
finds the factors of 15,...,26 digits and finally, the MPQS factors
the remaining product of two factors.

During the factoring process, extensive optional messages
(using the `Info' - mechanism) about the progress etc. are given.

For further details, see the manual.

Mike Atkinson