Primality certificates

[fjarri]

See https://en.wikipedia.org/wiki/Primality_certificate for an overview.

We could add:

• Pratt certificates. Simple, but the calculation can be slow.
• Atkin–Goldwasser–Kilian–Morain certificates. Requires some EC machinery; perhaps primeorder could be used for that.
• Pocklington certificates. Those can be used for random prime generation; although it is unclear if the generated primes are "random enough".

[dvdplm]

Pratt certificates are simple in concept but requires knowing the prime factors of n - 1 which is unfeasible for big primes (anecdotally WolframAlpha uses Pratt for numbers up to max 10^10).

There is also the problem of finding a witness (i.e. an integer w s.t. w^(n - 1) ≡ 1 mod n but w^((n - 1)/p_i) ≢ 1 mod n for all prime factors p_i of n), but this seems to be much more tractable: for integer sizes on the order of 2^2048 we'd need ~7 trials to find a suitable w (the # of attempts is given by 2*ln(ln(n))).

Note for posterity: I was a bit confused by the terminology; the "Pratt certificates" are based on the "Lucas primality test" which is NOT the same as the "Lucas pseudoprime" which is what this crate implements calling it lucas_test.

Atkin–Goldwasser–Kilian–Morain certificates seem plenty more involved and before spending more time on that I think we should have a conversation about what purpose they'd serve. It seems fascinating but also: do we really need it?

Pocklington certificates suffer from much the same downside as Pratt certificates: must find a large prime factor p of n - 1 (where "large" means p > √n -1), which is computationally hard. Furthermore, not all prime numbers have such a large p factor for n - 1 which means that for a candidate prime n, the Pocklington criterion might reject it even though n is actually prime. It is unclear (to me), just how many actual primes would be rejected by Pocklington. I assume this is what you mean by "random enough".