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

Wobling comments: ECPP, Cyclotomy, Konyagin/Pomerance

Expand Messages
  • Good Question <caldwell@utm.edu>
    While programing a comment lint for the new database system an old question has come up. In the past we have let ECPP be an archivable class. With some
    Message 1 of 5 , Jan 1, 2003
    • 0 Attachment
      While programing a comment lint for the new database system
      an old question has come up. In the past we have let
      "ECPP" be an archivable class. With some trepidation I
      marked several "Cyclotomy". David often uses
      "Konyagin/Pomerance". I strongly feel the first
      desrves to remain an archivable class; but I am not sure
      what to do with the other two.

      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?

      The answer to this question is very important to
      those that spend months on one type of proof and
      a simpler one is found.

      It is also important to me, because if we remove
      the ECPP once an easier method is found then
      eventually all primes marked ECPP will lose that
      status (maybe 30 years later...), so it makes my
      task harder--somehow periodically all such primes
      would need to be rechecked.

      So I am leaning towards leaving the method first
      used marked, even if there is a better way. But
      doesn't the clever Primo have some classical methods
      built in? This means using Primo would not be
      enough to make it ECPP, there would be some type
      of certificate check.

      Now I am leaning towards just making the comments
      not archivable--this would solve the problem that
      each record Primo number has a certificate full of other
      ECPP primes... and would encourage folks to focus on
      interesting numbers, not proof methods...

      Where should I lean next?

      Chris
    • Phil Carmody
      ... As we recently witnessed. ... Is it a property of the number or the proof? If a property of the number, then ECPP and APRCL classes contain the same
      Message 2 of 5 , Jan 1, 2003
      • 0 Attachment
        --- "Good Question <caldwell@...>" <caldwell@...> wrote:
        > While programing a comment lint for the new database system
        > an old question has come up. In the past we have let
        > "ECPP" be an archivable class. With some trepidation I
        > marked several "Cyclotomy". David often uses
        > "Konyagin/Pomerance". I strongly feel the first
        > desrves to remain an archivable class; but I am not sure
        > what to do with the other two.
        >
        > 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?

        As we recently witnessed.

        > The answer to this question is very important to
        > those that spend months on one type of proof and
        > a simpler one is found.

        Is it a property of the number or the proof?
        If a property of the number, then ECPP and APRCL classes contain the same
        numbers.
        If a property of the proof, then you invoke your elliptical comment below
        and your comment above.
        Therefore either view leads to problems. I think the latter ones (it is a
        property of the proof that took place) leads to less of an issue.

        > It is also important to me, because if we remove
        > the ECPP once an easier method is found then
        > eventually all primes marked ECPP will lose that
        > status (maybe 30 years later...), so it makes my
        > task harder--somehow periodically all such primes
        > would need to be rechecked.

        If it's a property of the proof, then then it's immutable.

        > So I am leaning towards leaving the method first
        > used marked, even if there is a better way. But
        > doesn't the clever Primo have some classical methods
        > built in? This means using Primo would not be
        > enough to make it ECPP, there would be some type
        > of certificate check.

        Leaning there too.

        > Now I am leaning towards just making the comments
        > not archivable--this would solve the problem that
        > each record Primo number has a certificate full of other
        > ECPP primes... and would encourage folks to focus on
        > interesting numbers, not proof methods...

        Before I express my leanage, let's argue by analogies, and see where it leads.

        If we agree (which we don't all necessarily by any means) that the tag is a
        property of the proof not the number, then is there a difference between the
        relevance of the "software used" and the "algorithm used" fields?

        I'm finding it hard to separate the two, which implies to me that having
        top-20 tables for the largest ECPP primes would imply that there ought to
        be analogous top-20 primes proved by OpenPFGW tables, for example.

        Which implies that I too have obliged myself to lean in the same direction
        as you again.

        > Where should I lean next?

        Remaining flexible is probably the key!

        Phil


        =====
        The answer to life's mystery is simple and direct:
        Sex and death. -- Ian 'Lemmy' Kilminster

        __________________________________________________
        Do you Yahoo!?
        Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
        http://mailplus.yahoo.com
      • 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 3 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 4 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 5 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.