> < ^ From:

^ Subject:

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

> < [top]