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

Re: [PrimeNumbers] Re: A Record Prime Factor by Pollard's "p

Expand Messages
  • joe.mclean@it.glasgow.gov.uk
    RE : Factoring. Two of the sites of most use for this sort of stuff are ; Will Edgington s page : http://www.garlic.com/~wedgingt/mersenne.html and Paul
    Message 1 of 5 , Mar 5, 2001
      RE : Factoring.

      Two of the sites of most use for this sort of stuff are ;

      Will Edgington's page : http://www.garlic.com/~wedgingt/mersenne.html

      and

      Paul Zimmerman's page : http://www.loria.fr/~zimmerma/records/ecmnet.html

      In terms of the list of methods below, you;ve missed out the Quadratic Sieve,
      which was the mainstay for a long time before NFS came along and is still used
      in various forms. I've implemented at various times everything except NFS and
      ECM (the maths is too difficult for me). I'm amazed that UBASIC provided such a
      result - it can't possibly be as fast as specifically designed code. However, by
      it's nature, there is always a chance at finding reaonably big factors.

      With finding factors of Fermat numbers, there are even more methods available,
      since the form of divisors is so restrictive : Leonid Durman and Tony Forbes
      both have freely available software that hunts specifically for Fermat factors.

      Joe McLean.

      ______________________________ Reply Separator _________________________________
      Subject: [PrimeNumbers] Re: A Record Prime Factor by Pollard's "p-1"
      Author: Phil Carmody <fatphil@...> at Internet
      Date: 05/03/01 01:45


      On Sun, 04 March 2001, Andy Steward wrote:
      [On the NMBRTHRY mailing list]
      > Early on 3rd March 2001, my own Ubasic "p-1" code found the following
      > factor of 922^47-1:
      >
      > p39=188879386195169498836498369376071664143
      > p-1=2.3.13.47.101.813613.1174951.1766201.3026227.99836987
      >
      > I therefore claim the world record factor found by this method (unless
      > any of you know better).

      Well done, Andy.
      Is UBasic as fast for this kind of job as C would be with one of the standard
      bignum packages. Or a dedicated number-theoretic package, such as pari or LiDIA?

      I was looking on the prime pages, for some info on the p-1 factoring method, and
      I noticed that there is no "Factoring into primes" section on the prime pages.
      My favourite search engine quickly pointed me in the direction of Wolfram/Eric
      Weisstein's Mathworld, several dead links, and some source code in an unknown
      language... So perhaps we could put our heads together to create the kernel of a
      new prime pages page of factoring methods? As far as my memory serves me
      (traditionally very poorly), it would be nice to get information on the
      following.
      - Trial division
      - Pollard p-1
      - Pollard p+1
      - Continued Fractions
      - Pollard Rho
      - NFS
      - ECM
      Note - I haven't got a clue what any of the above are (apart from one), I'm just
      parroting.

      I do have Knuth, so I am prepared to put my reading spec's on to learn a few of
      the above, but that still leaves half of them for others.

      Any takers?

      Phil

      Mathematics should not have to involve martyrdom;
      Support Eric Weisstein, see http://mathworld.wolfram.com
      Find the best deals on the web at AltaVista Shopping!
      http://www.shopping.altavista.com

      Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
      The Prime Pages : http://www.primepages.org



      Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
    • Paul Leyland
      ... Sieve, ... used Indeed, it s still doing sterling service and is probably the method of choice for general integers in the range 50-110 digits. I have
      Message 2 of 5 , Mar 5, 2001
        > In terms of the list of methods below, you;ve missed out the Quadratic
        Sieve,
        > which was the mainstay for a long time before NFS came along and is still
        used

        Indeed, it's still doing sterling service and is probably the method of
        choice for general integers in the range 50-110 digits. I have several QS
        jobs running right now.

        At the moment, GNFS takes over for about 100-160 digits whereas SNFS will
        handle special integers up to around 240 digits.

        Finding small factors (8 - 30 digits say) of large integers is best done
        with ECM; smaller factors are best found by trial division (<5 digits or so)
        and Pollard rho for the intervening range.

        Another good algorithm for factoring small integers, up to 25 digits say, is
        SQFOF. Such a tool comes in handy at times.

        > - Continued Fractions

        Personally, I'd drop this one. It has long been superseded by QS.


        Paul
      • Phil Carmody
        ... Yuppers. Amusingly, as I _thought_ QS, I typed _NFS_! I d counciously forgotten about NFS. ... In the words of my Finnish teacher you can t even pronounce
        Message 3 of 5 , Mar 5, 2001
          On Mon, 05 March 2001, Paul Leyland wrote:
          > > In terms of the list of methods below, you;ve missed out the Quadratic
          > Sieve,
          > > which was the mainstay for a long time before NFS came along and is still
          > used

          Yuppers. Amusingly, as I _thought_ QS, I typed _NFS_! I'd counciously forgotten about NFS.

          > Another good algorithm for factoring small integers, up to 25 digits say, is
          > SQFOF. Such a tool comes in handy at times.

          In the words of my Finnish teacher "you can't even pronounce it".
          (actually it sounds like an insult!)
          I've never heard of it, care to elaborate?

          > > - Continued Fractions
          >
          > Personally, I'd drop this one. It has long been superseded by QS.

          My source is Knuth, ACP vol 2 - SNA, alone. Knuth waxes lyrical about it. He makes it sound of great historical importance.
          I'm not qualified to even sneeze in the presence of QS. Do I see a volunteer? (quick - everyone else step back 1 pace :-) )

          Does anyone have _any_ information on "Valles two-thirds algorithm"? I know it _was_ on mathworld, but that was when mathworld was still available.

          Phil

          Mathematics should not have to involve martyrdom;
          Support Eric Weisstein, see http://mathworld.wolfram.com
          Find the best deals on the web at AltaVista Shopping!
          http://www.shopping.altavista.com
        • Paul Leyland
          ... Implementing NFS from scratch is somewhat non-trivial. I d estimate about a year s work to get something worthwhile. QS, on the other hand, is rather
          Message 4 of 5 , Mar 5, 2001
            > Yuppers. Amusingly, as I _thought_ QS, I typed _NFS_! I'd
            > counciously forgotten about NFS.

            Implementing NFS from scratch is somewhat non-trivial. I'd estimate about a
            year's work to get something worthwhile. QS, on the other hand, is rather
            easier --- especially as several implementations are available as source
            code.

            > > Another good algorithm for factoring small integers, up to 25 digits
            say, is
            > > SQFOF. Such a tool comes in handy at times.
            >
            > In the words of my Finnish teacher "you can't even pronounce it".
            > (actually it sounds like an insult!)
            > I've never heard of it, care to elaborate?

            Perhaps you've never heard of it, at least in part, because I didn't spell
            it properly! Try SQUFOF, aka
            Daniel Shanks' "Square Forms Factorization" algorithm. It finds factors of N
            in about (logN)^0.25 and so is much faster than trial division which is
            (logN)^0.5. Like CFRAC, it calculates the continued fraction expansion of
            sqrt(N), but doesn't use a factor base but, rather looks for a square
            directly. It's this last difference than makes SQUFOF an exponential
            algorithm and CFRAC subexponential. OTOH, it's very fast for relatively
            small integers.

            If memory serves, and I haven't looked for a *long* time, there's an
            implementation of SQUFOF in the good old RSA-129 version of the MPQS siever
            still to be found at ftp://ftp.ox.ac.uk/pub/math/ The double large prime
            version of MPQS requires the factorization of large numbers of relatively
            small integers and SQUFOF ruled supreme in this role for several years.
            These days, we tend to use ECM with small parameters but SQUFOF is still
            competitive.

            > > > - Continued Fractions
            > >
            > > Personally, I'd drop this one. It has long been superseded by QS.
            >
            > My source is Knuth, ACP vol 2 - SNA, alone. Knuth waxes
            > lyrical about it. He makes it sound of great historical importance.

            It is indeed of great historical importance, as is Fermat's method.
            Nonetheless, both are quite outdated now. Certainly implement it if you
            want to do so, but don't expect it to be competitive.

            Paul
          • Phil Carmody
            This has turned into a quite fun day (sad sad man that I am - sue me!) http://www.math.niu.edu/~rusin/known-math/index/11Y05.html Seems to be a fairly good
            Message 5 of 5 , Mar 5, 2001
              This has turned into a quite fun day (sad sad man that I am - sue me!)

              http://www.math.niu.edu/~rusin/known-math/index/11Y05.html

              Seems to be a fairly good resource after the non-existant one.

              (Hmmm, does anyone have a copy of Weisstein? I'm thinking nefarious thougts here...)

              About 6 months ago I found some ultra-lucid p-1, p+1, and rho source code on the internet, I even mailed the author a few hints on how he could optimise a couple of them. So - can I find that link again? Not for the life of me.

              Phil

              Mathematics should not have to involve martyrdom;
              Support Eric Weisstein, see http://mathworld.wolfram.com
              Find the best deals on the web at AltaVista Shopping!
              http://www.shopping.altavista.com
            Your message has been successfully submitted and would be delivered to recipients shortly.