A Las Vegas algorithm is an algorithm for which the expected run-time is small, but it always outputs the right answer. A Monte Carlo algorithm is an algorithm for which the worst-case run-time is small, but it errs with a small probability.
To demonstrate this idea, we will present a Monte Carlo algorithm to determine whether or not a number is prime. But first, we will state without proof that there is a function IsComposite (n, a) that takes n and a number a \in\{2,3, \ldots, n-1\} with the following properties:
- If n is prime, then IsComposite (n, a) always returns false.
- If n is composite, then IsComposite (n, a) incorrectly returns false for less than half of the numbers a \in\{2,3, \ldots, n-1\}.
Knowing this function, we can now describe this primality test algorithm:
\textbf{Data}: a positive integer n
\textbf{Result}: whether or not n is prime
\textbf{for} i=1,2, \ldots, 100 \textbf{do}
\quad a \leftarrow 1+\mathbf{D}(n-2)
\quad \textbf{if} IsComposite (n, a) \textbf{then}
\quad \quad \textbf{return} n is composite
\quad \textbf{end}
\textbf{end}
\textbf{return} n is prime
What is the probability this algorithm outputs “n is composite” when n is actually prime? What is the probability that this algorithm outputs " n is prime" when n is actually composite? How can we decrease these two probabilities?