Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Re: Ruler, compass and prime power

Expand Messages
  • David Cleaver
    ... Another excellent factoring program is Yafu, which stands for Yet Another Factoring Utility ;). You can download it from sourceforge here:
    Message 1 of 33 , Nov 1, 2011
    View Source
    • 0 Attachment
      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:
      > 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

      Another excellent factoring program is Yafu, which stands for Yet Another
      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
    • Ben Buhrow
      ... I saw that, thanks David! Since this is a list dedicated to primes, I ll also just mention briefly that yafu has one of the fastest sieve of Eratosthenes
      Message 33 of 33 , Nov 8, 2011
      View Source
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, David Cleaver <wraithx@...> wrote:
        >
        >

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

        I saw that, thanks David!

        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.
      Your message has been successfully submitted and would be delivered to recipients shortly.