There was something about this subject that perplexed me.

It seemed to imply a free lunch in primality proving.

As there is no such thing, I sought the demystification.

For what it's worth, here is what I ended up with.

Corrections welcomed! If busy, skip to joke at end.

A probable primality test (and, in an utterly negligible

subset of cases, a BLS proof) of a number N is fast because

it involves only O(d) multiplications of numbers with O(d)

digits, where d=log(N). With FFT, the test scales like d^2.

Contrast this with a Wilsonian proof that (N-1)!=-1 mod N,

needing O(exp(d)) multiplications at O(d) digits.

But what about certificate validation?

It may take O(d^5) multiplications at O(d) digits to make

an ECPP certificate, but to validate that certificate takes

perhaps O(d^2) multiplications, it seems me. If so Cert_Val

scales like d^3, though Titanix scales like d^6. The O(d^3)

ECPP *proof* time is then asymptotically less than the

O(d^4) Miller *test* time that would furnish a proof if GRH

were to be proven, one fine day. [Please don't repeat that

the Titanix running time is longer: that is not the point

at issue here, which is certificate validation.]

It is less well known that every prime has at least one

certificate of primality consisting of a *fixed* number,

O(100), of multiplications however large the prime!

This is implicit in Ribenboim's [1] brief account of the

Jones-Sato-Wada-Wiens polynomial [2] in 26 indeterminates.

It is legitimate public relations, but perhaps not good

pedagogy, to give a polynomial that maps 26 integers to

primes or negative integers. The transparent device of

subtracting squares from 1 shows what is really going on.

Primality of k+2 is proven by 14 simultaneous diophantine

equations, namely the vanishing of the things that refs

[1,2] put in squared square-brackets. Moreover, 7 of

these (brackets 2,1,3,11,9,12,13 in Ribenboim's ordering)

may be taken as mere definitions of the integers

z,q,e,l,y,m,x (in that order) in terms of k and 26-1-7=18

auxiliary integers, subject to 14-7=7 conditions. Of these,

6 conditions are Pellian square tests (in brackets

4,5,6,7,8,10) and the last (14) is a factorization test.

The theorem of [2] thus tells us that for every prime

there exists a certificate of primality with 18

auxiliary integers proving 7 necessary and sufficient

conditions in less than 100 elementary operations.

So what's the snag?

Well the obvious snag is to create that certificate!

Yet that is not the subject of concern, here.

A less obvious snag is that it would take *exponentially*

longer to validate this certificate than it takes to

validate an ECPP certificate for a prime of the same size.

This second point is made particularly clear by Cristoph

Baxa [3]. The underlying sleight of hand of the method of

Jones et al [2] is that it replaces the equation G=(k+1)!

by a set of necessary and sufficient diophantine equations,

with no reference to primality. Then one adds the Wilsonian

remark that G=(k+1)! may be written as G=g*k+2*g+k+1, in

Ribenboim's second bracket, if and only if k+2 is prime.

All the skull-duggery resides in solving Pellian equations

by exponentially growing Lucas sequences and hence creating

factorially large solutions for the diophantine equations.

The morsel of prime number theory was stated by John Wilson

(1741-1793) and proven by Joseph-Louis Lagrange (1736-1813)

in the oft-repeated process of adding francophone rigour to

opportunistic anglophone assertion. [Yves: plaisanterie!]

So the number of digits in the elements of the certificate

is O(d*exp(d)). One trades the vast Wilsonian expense of

O(exp(d)) multiplications at O(d) digits for the also vast

expense of a few multiplications at O(d*exp(d)) digits.

There is no free lunch, even in certificate validation!

Maybe this is the purgatory that awaits mathematicians.

Outside the pearly gates, Sao Pedro (or Sao Paulo?) says:> So you are the guys and gals that read how to prove this

David Broadhurst

> number prime with only 87 multiplications and additions.

> Here's the input; there are pencils and paper: do it,

> and then the Boss will let you in. She's ordered lunch

> for you in 10^87 minutes time; do try not to be late!

References:

[1] Paulo Ribenboim

The New Book of Prime Number Records

Springer, 1995, p.191.

[2] James Jones, Daihachiro Sato, Hideo Wada, Douglas Wiens

Diophantine Representation of the Set of Prime Numbers

American Mathematical Monthly

Vol 83, Issue 6, 1976, pp.449-464.

[3] Cristoph Baxa

A Note on Diophantine Representations

American Mathematical Monthly

Vol 100, Issue 2, 1993, pp.138-143.