deterministic primality test

[Dan Riley]

"Joseph Ashwood" <ashwood at msn.com> writes:
> I have my doubts about the thoroughness of the examination of this
> algorithm. From Page 4 (any inconsistencies are due to my typing):
> Input: integer n > 1
[...]
> So it fails to be executable on the second prime. I haven't done an in depth
> analysis of the algorithm beyond this. It is entirely possible that it only
> needs the small revision from:
> Input: integer n > 1
> to
> Input: integer n > 3
> but regardless the algorithm as it stands fails a basic test.

The proof of lemma 4.2, which asserts the existence of a suitable r,
is only valid "for large enough n".  3 is certainly too small.  I am
curious how large n does have to be--my guess would be that the
minimum is far too large for calculation by hand to be practical.

I do find it curious that they don't mention having implemented the
algorithm, but that could be normal for number theory papers for all I
know.
-- 
"The mere tendency of speech to encourage unlawful acts is not a
sufficient reason for banning it. [...]  The right to think is the
beginning of freedom, and speech must be protected from the government
because speech is the beginning of thought."  --Anthony Kennedy

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com