Cryptography deals with very large primes quite a bit, for example 2255 – 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 2255 – 19, and the composite 2255 – 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.