Re: [PrimeNumbers] Re: Ruler, compass and prime power
- 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:
> > 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.
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
- --- In email@example.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
> 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.