deterministic primality test

[Anton Stiglic]

----- Original Message -----
From: "Dan Riley" <dsr at mail.lns.cornell.edu>
To: <cryptography at wasabisystems.com>
Sent: Thursday, August 08, 2002 1:56 PM
Subject: Re: deterministic primality 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.

That's true.  They also mention that the r that will satisfy the criteria
(the criteria being that r-1 has a prime factor q >= 4*sqrt(r)*log(n)
and q|o_r(n)) will be in the interval [c1*(log n)^6, c2*(log n)^6],
for positive integers c1 and c2.

In the proof they say
"Choose constants c1 >= 4^6 and..."
So I guess that in step 2 you could actually start with
r = 4^6
and the algorithm would work (and you wouldn't have the problem
with r=2,  2-1 not having a prime factor).


> 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.

This is common not only among many number theorists but cryptography
theorists and other theoreticians as well.  They can be convinced that an
algorithm can work just by analyzing pseudo-code, they often don't
implement anything at all.  Or some will simply use special languages that
allow you to implement math algorithms at a high level (such as MAGMA),
but the code produced is not something you would use in production software.
Of course they are some theoreticians that are very good at implementing
algorithms (I'm thinking of prof. D.J Bernstein for example), but many don't
implement anything.


--Anton





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