[Verse 1]
Pick a witness, random integer a
One to n minus one, that's our array
First we check if greatest common divisor
Between a and n equals one, no compromiser
Write n minus one as two raised to r times d
Where d stays odd, that's our factorized key
Compute a to the d power modulo n
If it's one or negative one, we begin again
[Chorus]
Witness stands, composite falls
Miller-Rabin never stalls
Square and check, square again
Fermat's ghost can't comprehend
Probabilistic but so strong
Catches liars all along
Witness stands, composite falls
Miller-Rabin conquers all
[Verse 2]
Now we square repeatedly, r minus one times
Watching for that negative one sign
If we hit negative one somewhere in between
Then n might be prime, keeps the slate clean
But if we cycle through without that mark
Composite certainty, no question mark
Each witness gives us three-fourths chance right
To spot a fake prime hiding from sight
[Chorus]
Witness stands, composite falls
Miller-Rabin never stalls
Square and check, square again
Fermat's ghost can't comprehend
Probabilistic but so strong
Catches liars all along
Witness stands, composite falls
Miller-Rabin conquers all
[Bridge]
Carmichael numbers thought they were slick
Fooled Fermat's test with their little trick
But Miller-Rabin sees through their disguise
Strong pseudoprimes meet their demise
Run it k times, error shrinks down
Four to the negative k, precision profound
[Verse 3]
Industrial cryptography needs this speed
Deterministic tests just can't feed
The hunger for massive prime validation
Miller-Rabin serves the entire nation
RSA keys born from this algorithm
Secure communications, our digital rhythm
Witnesses testify in polynomial time
Making factorization uphill climb
[Outro]
From academic halls to server farms
Miller-Rabin sounds no false alarms
Probability theory meets number's soul
Making broken composites whole
The witness speaks, the verdict's cast
Primality testing unsurpassed