Re: [PrimeNumbers] Fw: Time (lg n)^(4+o(1)) for randomized primality proving
- --- Yves Gallot <galloty@...> wrote:
> Did someone read it?OK, it looks like it's a somewhat novel interpretation of the word
> Is it theoretically fast and/or practically fast?
'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.