Testing primeness of really big numbers with the Miller-Rabin algorithm

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:

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.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s