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

RE: [PrimeNumbers] Wobling comments: ECPP, Cyclotomy, Konyagin/Pomerance

Expand Messages
  • Paul Leyland
    ... You may wish to consider what the factoring community does in analgous cases. It s occasionally the case that a factorization is found by two methods
    Message 1 of 5 , Jan 2, 2003
    • 0 Attachment
      > But here is the big problem: definition.
      >
      > What makes a prime N an "ECPP" (or "Cyclotomy" or
      > "Konyagin/Pomerance") prime? What if enough prime
      > factors of N+/-1 are discovered later for more
      > classical methods--does it lose the "ECPP"...?
      > What if it is possible, but not obvious how, to use a
      > simpler method and the prime is submitted as ECPP
      > soon after to be done another way?

      You may wish to consider what the factoring community does in analgous cases.

      It's occasionally the case that a factorization is found by two methods essentially simultaneously. Most commonly, an ECM run spits out a small factor when a NFS or QS computation is still sieving, though other circumstances are occasionally found. For instance, Paul Zimmermann found a factor by P+1 of 118*^10^118+1 just after I'd started a SNFS run.

      A similar circumstance occurs when a factor which is found by one method is found to be discoverable by another. I don't mean trivial cases such as using Pollard rho rather than trial division to find 8-digit factors but, rather, ECM discovering a factor which could have been found more quickly by P-1 or P+1. An extreme case and, admittedly, a contrived case was found in Simon Singh's Cipher challenge where a factorization of a 512-bit integer actually performed by GNFS could have been done in about 1% of the computation by P-1.

      The factoring community invariably records the first reported method in these cases.


      Paul
    • David Broadhurst <d.broadhurst@open.ac.u
      ... 1) ECPP is at present an archivable class, with a top-20. I believe that it should stay like this, with Chris trying to chase up the folk in Marcel s
      Message 2 of 5 , Jan 2, 2003
      • 0 Attachment
        > ECPP, Cyclotomy, Konyagin/Pomerance

        1) ECPP is at present an archivable class, with a top-20.

        I believe that it should stay like this, with Chris trying to
        chase up the folk in Marcel's top-20 who are not yet in his.

        Once proven by ECPP, no subsequent easier validation can demote
        such a prime, since the top-20 is for primes first proven by ECPP.

        2) Cyclotomy is at present an archivable class, with a top-20.

        I believe that should be relegated to a mere comment.

        No-one will be affected since all of the present top-20 are archivable
        according to their mathematical definitions, irrespective of their
        proof method.

        3) Konyagin/Pomerance is at present neither an archivable class
        nor an accepted comment.

        I believe it should stay like this.

        If folk want to indicate that KP was the proof method they can do
        so as I do, using the <url,...,notes> addendum.

        David Broadhurst
      • David Broadhurst <d.broadhurst@open.ac.u
        ... Maybe Marcel could try to encourage his top-20 to contact Chris? Congrats to Jeff Heleen: http://www.ellipsa.net/pages/primotop20.html (10^4769 - 1) / 3 -
        Message 3 of 5 , Jan 2, 2003
        • 0 Attachment
          > 1) ECPP is at present an archivable class, with a top-20.
          > I believe that it should stay like this, with Chris trying to
          > chase up the folk in Marcel's top-20 who are not yet in his.

          Maybe Marcel could try to encourage his top-20 to contact Chris?

          Congrats to Jeff Heleen:

          http://www.ellipsa.net/pages/primotop20.html

          (10^4769 - 1) / 3 - 2*10^2384
          4769 decimal digits
          Certified by Jeff Heleen (2002)
          * Running time: 1464h
          * Processor: AMD Athlon 1.3 GHz

          David
        Your message has been successfully submitted and would be delivered to recipients shortly.