[Verse 1]
Need to check if numbers hide their secrets well
Composite masqueraders wearing prime disguise
Miller-Rabin cuts through mathematical lies
Probabilistic hunter with a story to tell
Take your number n minus one and factor out
Every power of two until you find what's left
Call that odd remainder d, you've passed the test
Now we're ready for the witness roundabout
[Chorus]
Write n minus one as d times two to the r
Probabilistic primality from afar
Pick a witness a, compute powers in sequence
If they hit the marks, we trust the precedence
Miller-Rabin speaking truth through repetition
Fermat's little theorem drives our mission
[Verse 2]
Compute a to the d modulo your candidate
If it's one you're golden, witness can't betray
If it's n minus one, another passing grade
Otherwise keep squaring, don't let chances fade
Square it r minus one times, watch the pattern grow
If you ever hit n minus one you're clear
But if all attempts just vanish in thin air
Your number's composite, that's what the math will show
[Chorus]
Write n minus one as d times two to the r
Probabilistic primality from afar
Pick a witness a, compute powers in sequence
If they hit the marks, we trust the precedence
Miller-Rabin speaking truth through repetition
Fermat's little theorem drives our mission
[Bridge]
Error probability shrinks with every round
One in four becomes one in a thousand
Choose your witnesses randomly each time
Cryptographic certainty through algorithmic rhyme
[Verse 3]
Deterministic version picks specific base
Two through seventy-three covers all the ground
For numbers under billions, truth will be found
No more probability, just mathematical grace
RSA encryption trusts this clever scheme
Generating primes for public private keys
Miller-Rabin guards our digital securities
Prime detection powering the cryptographic dream
[Outro]
Factor out the twos and test the witnesses
Modular exponentiation never misses
Polynomial runtime keeps the system flowing
Prime or composite, now you're really knowing