deterministic primality test

Joseph Ashwood ashwood at msn.com
Fri Aug 9 05:26:22 EDT 2002


[I've got some doubts about the content here but I think the
discussion is certainly on charter --Perry]

Since I have received a number of private replies all saying approximately
the same thing; lookup for small n, use algo for large. Allow me to extend
my observation.
To quote myself from earlier:
> 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;

n = prime number > 2
1: n is not of the form (we already know it is prime)
2: r=2
3: 2 < 3
4: gcd = 1 (since N is prime)
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 the algorithm cannot be executed on any prime value with the exception of
2 (which it correctly states is prime). It is possible that the algorithm is
simply incomplete. The apparent intension is:
6: if(r == 2) q = 1;
    else q is the largest prime factor of r-1

A few additional observations under the assumption that this is the desired
statement:
The algorithm is equivalent to (I've left the numbering for the original
instruction order:
1: if (n is of the form a^b, b>1) output COMPOSITE;
2: r=2
3: while(r < n) {
5:    if(r is prime)
4:        if(gcd(n,r)=/=1) output COMPOSITE;
6:         if(r == 2) q = 1;
            else q is the largest prime factor of r-1
7.        if(q >= 4sqrt(r)log(n)) and (n^((r-1)/q) =/= 1 (mod r))
8                break
9:    r <-r+1
proving this is trivial. Since r is being stepped sequentially the only new
results will occur when r is prime (otherwise gcd is not dependable), this
will reduce the number of calls to gcd, and so reduce the asymptotic time.
This is obviously bounded by the time it takes to check if r is prime.
However note that we can now replace it conceptually with, without changing
anything:
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;
6:         if(r == 2) q = 1;
            else q is the largest prime factor of r-1
7.        if(q >= 4sqrt(r)log(n)) and (n^((r-1)/q) =/= 1 (mod r))
8                break
9-2:    r <-nextprime(r)

The asymptotic time is now bounded primarily by the runningtime of
nextprime(), the current best running time for this is not polynomial (but
there are better ways than their step by 1, prime check method). In fact
assuming that the outer while loop is the primary exit point (which is
certainly true for the worst case), the algorithm presented takes O(n) time
(assuming binary notation, where n is the function input n), this is
equvalent to the convential notation O(2^m), where m is the length of the
input. The best case is entirely different. Best case running time is
O(gcd()), which is polynomial. Their claim of polynomial running time is
certainly suspect. And over the course of the entire algorithm, the actual
running time is limited by a function I've dubbed listAllPrimesLessThan(n),
which is well studied and the output has exponential length, making such a
function strictly exponential.

Additionally it has been noted that certain composite values may pass the
test, regardless of the claim of perfection. It is unlikely that this
function is of much use.
                    Joe


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



More information about the cryptography mailing list