Re: Primality test

[Hans Aberg]

At 00:24 +0200 2002/08/14, Torbjorn Granlund wrote:
>OK, I had a brief look at it.  If my reading is correct, the method is not
>>completely practical, O(n^9) or something like that.  Is this your
>>interpretation as well?

The paper says:
  Theorem 5.1. The asymptotic time complexity of the algorithm is O(log^12 n).
But subsequent discussions also suggests that O(log^2 n) might be possible
in actual use.

Here, I interpret log n as ~ number of digits in n. If the upper limit,
log^12 n, is reached and one is interested in primes with a few hundred
digits (as in cryptology), then it is not practical. But if it is closer to
the lower limit, it might.

I am told that in cryptology, one is currently using faster methods in
order to produce large primes. Perhaps the method above, if refined, will
have some impact on that in the future.

>I am quite busy right now, and don't have time for this stuff.
>Would you mind making a test implementation into GNU.

The reason I sent it to the GNU GMP was that I became curious about it, but
realized that neither I would have time for implementing it.

Also, the discussion above suggests that there is no immediate strong need
for its implementation: If somebody becomes curious about it and wants to
test it in practise, then I think one might implement it.

Otherwise, one would probably do better waiting for a suitable refinement
emerging. Right now, it is probably mostly an interesting thing with not so
much practical value. Stay tuned, though.

  Hans Aberg