deterministic primality test
Joseph Ashwood
ashwood at msn.com
Wed Aug 7 23:05:49 EDT 2002
----- Original Message -----
From: "Don Davis" <dtd at world.std.com>
> http://www.cse.iitk.ac.in/primality.pdf
>
> PRIMES in P
> M. Agrawal, N. Kayal, N. Saxena
> Dept. of C.S. & Eng,
> Indian Inst. of Tech. Kanpur
> Aug 6, 2002
>
> Abstract: We present a deterministic polynomial time
> algorithm that determines whether an input number is
> prime or composite.
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
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
but regardless the algorithm as it stands fails a basic test.
Joe
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com
More information about the cryptography
mailing list