Return-Path: william@bourbon.usc.edu
Delivery-Date: Tue Apr 11 14:27:53 2006
Received: from bourbon.usc.edu (bourbon.usc.edu [128.125.9.75])
by merlot.usc.edu (8.13.1/8.13.1) with ESMTP id k3BLRrJ6029502
for ; Tue, 11 Apr 2006 14:27:53 -0700
Received: from bourbon.usc.edu (localhost.localdomain [127.0.0.1])
by bourbon.usc.edu (8.13.1/8.13.1) with ESMTP id k3BLN1ua031815
for ; Tue, 11 Apr 2006 14:23:01 -0700
Received: (from william@localhost)
by bourbon.usc.edu (8.13.1/8.13.1/Submit) id k3BLN1vo031814
for csac@merlot; Tue, 11 Apr 2006 14:23:01 -0700
Date: Tue, 11 Apr 2006 14:23:01 -0700
From: william@bourbon.usc.edu
Message-Id: <200604112123.k3BLN1vo031814@bourbon.usc.edu>
To: csac@merlot.usc.edu
Subject: AKS primality test
Hi,
For those who are interested, some information about the AKS
primality test mentioned in class today can be found at the
following places:
http://en.wikipedia.org/wiki/AKS_primality_test
The main theorem there is that if n is prime, then
(x-a)^n = x^n - a (mod n)
where ^ is the exponentiation operator and = is the
congruency symbol. What about x? Well, the above notation
is expressed a polynomial ring and that's where the x came
from. But what is a polynomial mod n? I'm not sure what it
means.
The above congruency is to be tested in a finite field of
GF(n^r) where r is another prime number (please see the above
web page for details).
At the bottom of the above page, it says that the running
time of AKS is O((log n)^10.5) where (log n) is the number of
bits in n. With Millar-Rabin with t=1, it takes about (log n)
modular exponentiations and each modular exponentiation takes
2 times (log n) modular multiplications. So, that's O((log n)^2).
So, AKS is quite slow relative to Millar-Rabin (as expected).
I'm also not sure how hard it is to implement arithematics in
GF(n^r). But the significance of AKS is that it has *proved*
that the problem of determining whether a number is prime or
not (known as the PRIMES problem) can be solved in polynomial
time.
To see AKS in a larger context, please see:
http://en.wikipedia.org/wiki/Primality_test
The above page also mentioned Adleman and Huang, who are
professors in the CS department here. Prof. Adleman is the
A in RSA. Prof. Huang teaches CS 556 (the crypto class here)
regularly.
--
Bill Cheng // bill.cheng@usc.edu