- Warning: This whole post, while I believe it is correct, quite

likely is useless and stupid and of mere curiosity or recreational

value.

As you probably know, the AKS primality test runs in

polynomial time

http://en.wikipedia.org/wiki/AKS_primality_test

but it is of little or no practical interest.

Wilson's theorem from about 1770

states N is prime iff

(N-1)! + 1 is divisible by N.

http://en.wikipedia.org/wiki/Wilson%27s_theorem

Suppose temprorarily we are not worried about computer TIME (BIT OPS), but merely about NUMBER OF INTEGER ARITMETIC OPERATIONS

(we have fantasy computer hardware that'll do a

huge-precision +,-,* or / in

1 time step no matter how many digits are in the integers)

then I point out it is possible to use Wilson's theorem to

test primality in polynomial #steps. That is, in a #steps polynomial

in the number of digits in N. A rough sketch of how:

Using integer / and * and + and - we can compute A mod B.

You can compute 10000000...00001^N [a very long number whose digits all are 0s except for leading and tail 1, raised to power N]

and from the digits of the result you get via Binomial theorem, the

binomial coefficients (N choose K). (The extraction

of the desired digit-range can be done with powering and mod

operations.) Do this for the right N's

and K's and combine the binomial coefficient results

using (N choose K) = N!/[K!(N-K)!] to get a

fast computation of the factorial (N-1)!.

The number 1000...0001 needs to be order N^2

digits long (ouch!). The whole computation should run in O(logN)^2

arithmetic operations using "binary powering" and a mildly clever scheme for combining binomial coeffs which I'll leave to you.

THE HOLY GRAIL:

OK, now the question is, can we turn this into an actually-fast scheme?

To do so, you'd want to somehow compute things using modular arithmetic with cleverly chosen moduli (and cleverly chosen radices in the huge multidigit numbers, or use symbolic polynomials not numbers and only compute the coefficient of the desired term not the undesired terms... or use some flavor of chinese remaindering... or something) so we do not ever need huge-precision numbers so that the

whole algorithm can be done in polynomial memory-space and/or time.

I do not have a method to propose to accomplish this. On the other hand it sounds mildly plausible there might be a way to do it, and I do not have any proof to propose that you can't do it!

--

Warren D. Smith

http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

and

math.temple.edu/~wds/homepage/works.html - --- In primenumbers@yahoogroups.com,

"WarrenS" <warren.wds@...> wrote:

> THEOREM. Let N>1 be an integer.

We don't need a Turing machine for that, do we?

> Turing machine can compute (N-1)! mod N in an amount of

> time polynomial in logN.

> PROOF.

> Test N for primality using AKS test.

> If N is prime then the answer is -1 by Wilson's theorem,

> otherwise it is 0.

We can do it with a real machine and any real

machine is less powerful than a Turing machine.

David