deterministic primality test

[Anton Stiglic]

----- Original Message -----
From: "Joseph Ashwood" <ashwood at msn.com>
To: <cryptography at wasabisystems.com>
Sent: Wednesday, August 07, 2002 11:05 PM
Subject: Re: deterministic primality test

> 1: if (n is of the form a^b, b>1) output COMPOSITE;
> 2: r=2
> 3: while(r < n) {
> 4:    if(gcd(n,r)=/=1) output COMPOSITE;
> 5:    if(r is prime)
> 6:        let q be the largest prime factor of r-1;
> I don't need to finish the algorithm. Simply run this for n = 3
> 1: n is not of the form
> 2: r=2
> 3: 2 < 3
> 4: gcd = 1
> 5: 2 is prime
> 6: q = ?
>     r=2
>     q = largest prime factor of (2-1) = largest prime factor of 1. 1 has
no
> prime factors, since 1 is by definition not prime, but has no integer
> divisors except 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

I don`t think that would work either.  If n is any odd integer > 3 (not of
the form
a^b, b>1), then you will set r = 2 in step 2, go throw step 3 (2 is smaller
than n)
and step  4 (gcd(n,2) will equal 1 so you don't exit yet), and  step 5 (2 is
prime)
and bump into the same problem in step 6 (2-1 = 1 doesn't have a prime
factor).

I guess you can fix this by rather having step 5. changed to
5'.  if (r is an odd prime)

Does that make sense?

Note that it seems that Lenstra and Pomerance believe the result is correct.
See for example
http://listserv.nodak.edu/scripts/wa.exe?A2=ind0208&L=nmbrthry&F=&S=&P=956
(I found that link from a post by Mads Rasmussen on sci.crypt).
It is also worth noting as well the names that appear in the
"Acknowledgements"
section of the paper, if these people approved of the result (their names
being there
doesn't necessarily apply that fact however), it gives some good weight to
the result.

--Anton





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