a witness for the compositeness, and the test stops.
#Get back to the step one until the required accuracy is reached.

After one or more iterations, if n is not found to be a composite number, then it can be declared probably prime.

Fermat primality test

The simplest probabilistic primality test is the Fermat primality test (actually a compositeness test). It works as follows:

:Given an integer n, choose some integer