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)