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

11202Re: [PrimeNumbers] Fw: Time (lg n)^(4+o(1)) for randomized primality proving

Expand Messages
  • Phil Carmody
    Jan 30, 2003
    • 0 Attachment
      --- Yves Gallot <galloty@...> wrote:
      > Did someone read it?
      >
      > Is it theoretically fast and/or practically fast?

      OK, it looks like it's a somewhat novel interpretation of the word
      'certificate', with certificate finding taking O(d^(2+o(1))), and
      verification taking O(d^(4+o(1))). (d=ln(n))

      Using that definition, APRCL and BLS have a certificate - a list of
      all the things you need to compute (and that take all the time).

      I looked at his verification claims, and to be honest I've rarely seen so
      many o(1)s. Given the slow growth of the third log in the APRCL exponent,
      and the already-seen following of the predicted growth, I reckon that he's
      going to have to look a long way to get those o(1)s to become negligible.
      (The axes are cryptic (but log/log) at http://fatphil.org/maths/APRCL/
      where there's a chart of some tests I did just last month, and the gradient
      is clear. I will have some >1000 digit values added to that chart soon).

      His own wording makes it sound as if he thinks that it will become faster
      than APRCL and ECPP for a real example. The fact that he's sitting on his
      optimisations means that it's too soon to judge. You must remember that
      Professor Bernstein is not just a theoriser, but also an implementer, and a
      darned good one at that, so I'm hoping that he will support his own
      predictions with real figures.

      Phil



      =====
      Is that free as in Willy or as in bird?

      __________________________________________________
      Do you Yahoo!?
      Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
      http://mailplus.yahoo.com
    • Show all 3 messages in this topic