Describe fast primality tests like Miller–Rabin

The "Trial Division" method (checking factors up to the square root) is far too slow for the massive numbers used in cryptography (which can be over 600 digits long).

Instead, we use probabilistic primality tests. The most famous one is the Miller-Rabin test.

How Miller-Rabin Works (Simplified):

The Miller-Rabin test doesn't try to factor a number. Instead, it checks if the number "behaves" like a prime number based on certain properties defined in number theory.

• It's a "Probabilistic" Test: This means it doesn't give a 100% "yes" or "no" answer. It gives a 100% "definitely composite" or a "very probably prime" answer.
• Witnesses: The test involves picking a random number a (called a "witness") and performing a set of calculations (modular exponentiation) with it and the number n we are testing.
• The Outcome:
  • If nfails the test for the witness a, it is 100% guaranteed to be composite.
  • If npasses the test, it is called a "strong probable prime." It might be prime, or it might be a composite number that is "lying."
• Power in Repetition: The chance of a composite number "lying" to a single witness is low (less than 1/4). To be sure, we just repeat the test with multiple, different random witnesses (e.g., 40 or 60 times).

If a number passes the Miller-Rabin test 40 times, the probability that it's actually composite is less than (1/4)40, a number so small it's considered a practical certainty. This is how computers quickly find the large prime numbers needed to secure all internet communication.