2

Hypothetically, I am 100% confident that a large multi-million digit number is prime because I expended the resources to run an extensive primality test. Let's say the number Truly is a prime. Is there any proof I could provide that would save others from having to run more extensive tests?

We can do the opposite, I can hand over a big number and say it's not prime by providing evidence: a factor. Depending on the size of numbers it may still take a non-trivial amount of time to prove it, but it would take comparably much less time than starting a primality test from scratch.

Corey Ogburn
  • 501
  • 7
    You might want to read https://en.wikipedia.org/wiki/Primality_certificate – Henry Jul 09 '21 at 22:09
  • @Henry Unless you wrote that page yourself and know it won't be compromised by vandals, or, more likely, by idiots, I wouldn't recommend you tell anyone to read that page. – Robert Soupe Jul 09 '21 at 22:27
  • 2
    I wholeheartedly recommend you read https://mathworld.wolfram.com/PrattCertificate.html by Eric Weisstein. I trust him a lot more than I trust some random IP address. – Robert Soupe Jul 09 '21 at 22:30
  • 1
    paper by Andrew Granville, easier reading than the AKS article https://www.ams.org/journals/bull/2005-42-01/S0273-0979-04-01037-7/home.html Plus Granville is not an idiot – Will Jagy Jul 10 '21 at 00:36
  • @WillJagy I take it you found the Granville paper by scrolling to the bottom of the Wikipedia article. I concede I do that sometimes, too. – Robert Soupe Jul 10 '21 at 00:52
  • 2
    @RobertSoupe no, it was in a journal I get. Why the strong words about a wikipedia article? – Will Jagy Jul 10 '21 at 00:53
  • @WillJagy I'm just so tired of people treating it like it's Britannica, and it's almost always the first Google result. – Robert Soupe Jul 10 '21 at 01:02
  • The problem with AKS is there is no certificate, albeit you can inform them AKS is polynomial time therefore they should be satisfied. There are well-specified formats for ECPP proofs which have multiple independent implementations of verifiers. Those also incorporate simple n-1, n+1,and hybrid methods. The Wikipedia page isn't a bad thing to read to understand the concept of primality certificates. – DanaJ Jul 10 '21 at 02:04
  • @RobertSoupe most STEM pages get corrected by STEM experts on Wikipedia. – Roddy MacPhee Jul 13 '21 at 16:35
  • @RoddyMacPhee That might be true. But if those experts have written materials on the subject for which they are personally accountable, and which are subject to review by some editorial board, I would much rather cite those. – Robert Soupe Jul 13 '21 at 20:49

1 Answers1

3

Yes. There are various theorems about prime numbers stating that if $n$ meets condition $X$ then $n$ is definitely a prime number. Some of those theorems depend on $n - 1$, which is a very easy calculation. We can use, for example, the converse of Fermat's "little" theorem to create a Pratt certificate.

Let's say, for the sake of example, that 139 is prime but we're not allowed to use trial division to prove that it is prime (even though a computer can do it in a nanosecond, if even that long).

Clearly 138 is composite, as it's divisible by 2, 3 and 23. We see that $141^{138} \equiv 1 \pmod{139}$. But $$141^{\frac{138}{2}} = 141^{69} \equiv 138 \pmod{139},$$ $$141^{\frac{138}{3}} = 141^{46} \equiv 96 \pmod{139}$$ and $$141^{\frac{138}{23}} = 141^{6} \equiv 64 \pmod{139}.$$

The important thing is that none of those congruences are equal to 1.

So 141 is a "witness" for a Pratt certificate for 139. Of course making a Pratt certificate for 139 is overkill. But for a prime with 139 digits, it's preferable to trial division.

According to Wolfram Mathworld, Wolfram Mathematica uses Pratt certificates for numbers below $10^{10}$ and the more sophisticated Atkin-Goldwasser-Kilian-Morain certificates for larger numbers.

Robert Soupe
  • 14,663