Question

Question: Use pseudocode to write out the probabilistic primality test described in Example 16.

Short answer

Answer

The probabilistic primality test is described as:

procedureprobabilistic prime$\left(n,k\right)$

Composite: = false

$i:=0$

While composite = falseand$i⩽k$

$i:=i+1$

Choose$b$ uniformly at random with$i<b<n$

Apply Miller’s test to base$b$

If$n$fails the test thencomposite = true

Ifcomposite = true then print{“composite”)

elseprint (“probably prime”)

return unknown

Step-by-step solution

Given information  

A permutation of the integers $1$through $n$has already been sorted (that is, it is in increasing order), or instead, is a random permutation.

Definition and formulas

The input to this algorithm is the integer $\mathit{n}\mathbf{>}\mathbf{1}$to be tested for primality and the numberof iterations desired.

If the output is “composite” then we know for sure that$\mathit{n}$is composite. If we get the output as “probably prime” then we do not know whether or not$\mathit{n}$is prime, and of course it makes no sense to talk about the probability that$\mathit{n}$is prime(either it is or it is not there is no choice involved). We only know that the chance that a composite number would produce the output “probably prime” is at most $\frac{\mathbf{1}}{{\mathbf{4}}^{\mathbf{K}}}$.

Designing the probabilistic primality test

So, using the pseudocode we get the probabilistic test as given below:

procedureprobabilistic prime$(n,k)$

Composite: = false

$i:=0$

While composite = falseand$i⩽k$

$i:=i+1$

Choose uniformly at random with$i<b<n$

Apply Miller’s test to base$b$

If$n$fails the test thencomposite = true

Ifcomposite = true then print{“composite”)

elseprint (“probably prime”)

return unknown