[GAP Forum] Factoring large integers

[Stefan Kohl]

On Wed, October 19, 2016 11:11 am, [Muniru Asiru] maasiru at yahoo.com wrote:
>
> I need to factor large integers.  One of then is
> d:=208792137511016848023422421216659133913113038868420856362546192700228823547384086468768314408434778574357732094492450898877804848025959323284721735578041792204431293469827064868376517438126765900138542676486099702859181721290457656418761796076484288301990972494617227238953673093108532474354655441019362615154103484247530007425892848695540897;;
> I tested d for being prime or not by using IsPrime(d); which returns false which
> confirms that d is composite. Â 
> I tried PartialFactorization(d,6); which returns d.  Also Factors(d);  did not return
> a result in 15 minutes. Â 
> How do I find the factors of d using GAP?

If the second-largest factor is 'relatively small',
you can factor your number with GAP / FactInt if you just wait 'some longer'.
How long it will take depends very much on the size of the factors
and on good or bad luck.

However if your number has two factors of roughly comparable size,
you will need a dedicated program implementing the GNFS (generalized
number field sieve) and either *A LOT* of patience or a supercomputer
(note that your number is greater than a 1024-bit RSA modulus).

Best regards,

    Stefan

-----------------------------------------------------------------------------
http://www.gap-system.org/DevelopersPages/StefanKohl/
-----------------------------------------------------------------------------