On 11/1/2011 8:01 AM, mikeoakes2 wrote:
> "djbroadhurst" wrote:
> > > After about 5 hours pari-GP has told me this:-
> > > *** factor: Warning: MPQS: factoring this number will take several hours
> > In this case msieve fits the bill:
> > $ tail -3 msieve.out
> > Tue Nov 1 10:28:27 2011 prp44 factor:
> > Tue Nov 1 10:28:27 2011 prp45 factor:
> > Tue Nov 1 10:28:27 2011 elapsed time 00:43:03
> It would be interesting to know what program(s) can improve on David's 43 mins.
Another excellent factoring program is Yafu, which stands for Yet Another
Factoring Utility ;). You can download it from sourceforge here:
If you try to factor a general number, by default yafu will try several
different methods (fermat, rho, p+1, p-1, ecm, siqs, and nfs) to completely
factor the number. On my computer it spent a total of 49.1 minutes trying to
factor this number. However, only 37.3 minutes were spent in SIQS, which
ultimately factored the number.
The use of nfs in yafu is aided by the ggnfs binaries. The README and
docfile.txt describe how to set it all up. Also, it can use multiple threads to
factor numbers. If I had assigned more threads to factoring this C89, I'm sure
each stage, including SIQS, would have finished faster.
One good collection of current factoring programs is Jeff Gilchrist's site here:
You can get windows binaries for GGNFS, GMP-ECM, MSIEVE, and YAFU. There is
also a "Beginners Guide to NFS factoring using GGNFS and MSIEVE" here:
This can help anyone factor "large numbers" using a python script to automate
all the different stages of NFS factoring. Hopefully you and others will find
this information useful. Below, I've included the snippet from the Yafu output
showing the factorization of the C89 with SIQS.
starting SIQS on c89: 3254253608993048495956650768301024007584718792417975142515
==== sieving in progress (1 thread): 69872 relations needed ====
==== Press ctrl-c to abort and save state ====
69944 rels found: 21021 full + 48923 from 811421 partial, (376.81 rels/sec)
freed 61 duplicate relations
SIQS elapsed time = 2243.3906 seconds.
b = 1
Total factoring time = 2947.6094 seconds
PRP44 = 44643300072722108400698902752086877193190113
PRP45 = 728945576086893794974061219407402693792528577