DEV Community

Cover image for Miller Robin Primality Test
Remon Hasan
Remon Hasan

Posted on

1

Miller Robin Primality Test

Similar to Fermat primality test, Miller-Rabin primality test could only determine if a number is a probable prime.

It is based on a basic principle where if , but , then is composite.

The algorithm in simple steps can be written as,

Given a number () for which primality is to be tested,
Step 1: Find
Step 2: Choose in range
Step 3: Compute . If is , can be prime.
Step 4: Compute . If , is composite.
If , is prime.
Step 5: Repeat Step 4 for times.
Step 6: If neither or appeared for , is composite.

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay