About this document

Miller-Rabin Primality Test Overview by Hung Nguyen is a document available to read on EtoBox.

This document summarizes a lecture on the Miller-Rabin randomized primality test. It begins with an introduction to primality testing and its importance for cryptography. It then defines randomized algorithms and complexity classes like RP, coRP, and BPP. The main theorem is that the problem of determining primality (PRIMES) is in coRP, meaning there is a randomized test that always outputs "prime" for primes and "composite" with probability at least 1/2 for composites. The lecture covers previous primality

Author

Hung Nguyen

Language

EN