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