- On 11/1/2011 8:01 AM, mikeoakes2 wrote:
>

Another excellent factoring program is Yafu, which stands for Yet Another

> "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:

> 44643300072722108400698902752086877193190113

> > Tue Nov 1 10:28:27 2011 prp45 factor:

> 728945576086893794974061219407402693792528577

> > 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.

>

> Mike

Factoring Utility ;). You can download it from sourceforge here:

http://sourceforge.net/projects/yafu/files/

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:

http://gilchrist.ca/jeff/factoring/index.html

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:

http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html

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.

-David C.

starting SIQS on c89: 3254253608993048495956650768301024007584718792417975142515

1734309566476859467023346359201

==== 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

***factors found***

PRP44 = 44643300072722108400698902752086877193190113

PRP45 = 728945576086893794974061219407402693792528577 - --- In primenumbers@yahoogroups.com, David Cleaver <wraithx@...> wrote:
>

I saw that, thanks David!

>

>

> Ben, I've been trying to tell them how awesome Yafu is! You can see my message

> here:

> http://tech.groups.yahoo.com/group/primenumbers/message/23598

>

> If anyone needs any factoring utilities, yafu should be first on the list. Then

> some combination of yafu/msieve/ggnfs to factor larger numbers. I tried to

> spell it all out in the above post. Hopefully I didn't misrepresent any info

> about yafu. Please correct me if I was wrong. If anyone has any questions,

> feel free to ask on this list.

>

> -David C.

>

> P.S. For full disclosure, I helped contribute a small amount of code to yafu. :)

>

Since this is a list dedicated to primes, I'll also just mention briefly that yafu has one of the fastest sieve of Eratosthenes implementations I'm aware of, for generating lists of primes in arbitrary ranges up to 10^19. Maybe that is useful to folks here too.

cheers,

- ben.