Cryptography deals with very large primes quite a bit, for example 2^{255} – 19 = 57896044618658097711785492504343953926634992332820282019728792003956564819949.

There are lots of ways to test whether a number *p* is prime:

**Trial division**

Divide it by all the numbers between 2 and √*p*and verify the remainder is nonzero in every case**Sieve of Eratosthenes**

Generate all the primes between 2 and √*p*using the Sieve of Eratosthenes and then do trial division but with only those primes – see my previous blog post Generating primes using the Sieve of Eratosthenes plus a few optimizations**Agrawal-Kayal-Saxena (AKS)**

See my previous blog post Teaching someone to fish and the AKS primality test**Computer-generated proofs**

SafeCurves: Proofs of primality has a list of primes of cryptographic interest, and a computer-generated proof for each listed prime. Here’s the proof for 57896044618658097711785492504343953926634992332820282019728792003956564819949.- … lots of others

One of the techniques that sees a lot of use in practice is the Miller–Rabin primality test. I wrote an implementation in PowerShell. Here’s some example output, testing the prime 2^{255} – 19, and the composite 2^{255} – 63:

```
.\miller-rabin.ps1 -prime ([System.Numerics.BigInteger]::Pow(2, 255) - 19) -rounds 10000
57896044618658097711785492504343953926634992332820282019728792003956564819949 = 2^2 14474011154664524427946373126085988481658748083205070504932198000989141204987 + 1
All witnesses state that 57896044618658097711785492504343953926634992332820282019728792003956564819949 COULD BE PRIME
.\miller-rabin.ps1 -prime ([System.Numerics.BigInteger]::Pow(2, 255) - 63) -rounds 10000
57896044618658097711785492504343953926634992332820282019728792003956564819905 = 2^6 904625697166532776746648320380374280103671755200316906558262375061821325311 + 1
11328271172437154995197519604260009402971642463559414996414256118294343278719^(2^r 904625697166532776746648320380374280103671755200316906558262375061821325311) with r = 0 to (6 - 1) has no 1 or -1 so 57896044618658097711785492504343953926634992332820282019728792003956564819905 is DEFINITELY COMPOSITE
```

The way Miller-Rabin works is kind of like Among Us. We have a player *p* who claims to be an innocent prime, but might actually be an evil composite.

So we surround *p* with witnesses who keep an eye on her activities. If we see her vent or kill, then AH-HAH! She is a composite! Vote her off!

If we *don’t* see her vent or kill, even though we have lots of witnesses around her, then there are two possibilities: either she’s legitimately an innocent crewmate, or she’s a *very sneaky* impostor who is able to pull off her killing and venting in such a way as to evade the gaze of our witnesses.

So Miller-Rabin will never tell you *for sure* that a number is prime. It will only tell you a number is DEFINITELY COMPOSITE or PROBABLY PRIME.

## One thought on “Testing primeness of really big numbers with the Miller-Rabin algorithm”