Newsgroups: sci.math From: bs@gauss.mitre.org (Robert D. Silverman) Subject: Re: Some other conjectures Date: Thu, 8 Jul 1993 19:01:57 GMT In article <1993Jul8.165813.14259@galois.mit.edu> jbaez@phragmen.mit.edu (John C. Baez) writes: :In article koiran@ens-lyon.fr writes: :>In article 5994@galois.mit.edu, jbaez@banach.mit.edu (John C. Baez) writes: stuff deleted.... :Gary Miller's result has nothing to do with P vs NP, and essentially goes :like this: : :Let N be a number that is composite. The *Extended* Riemann Hypothesis implies :that there is a number x < c logN (or logN to some integer pwer, I dont :quite remember the exact statement) for some constant c and a polynomial time The number x is known as the least primitive root of N (N is prime). GRH asserts that x <= c log^2 N. Eric Bach has shown that one can take c = 4. This may have been lowered to 2. (I'm not sure) :algorithm ALG(x,N) such that ALG will indeed verify that N is composite. What happens is that one does the Rabin test up to base x = c log^2 N. If N is composite, then there must be a witness among these to that fact. If N is prime, then all tests return 'prime' and the number must indeed be prime because one of the numbers used as a base must have been a primitive root. (Only 2,4, and numbers of the form p, 2p, p^n, 2p^n for p an odd prime can have primitive roots). You also must test that N is not a perfect power. Assume multiplication mod N takes time M(N). This can be O(log^2 N) using pencil/paper multiplication, or O(log N loglog N logloglog N) using FFT's. Modular exponentiation takes time O(log N M(N)). The Miller result then means that there is a O(log^3 N M(N)) algorithm for prime proving. -- Bob Silverman These are my opinions and not MITRE's. Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think"