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.


      Is that free as in Willy or as in bird?

      Do you Yahoo!?
      Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
    • Show all 3 messages in this topic