** Next:** 5.1 Pollard's
** Up:** Some Lectures on Number
** Previous:** 4.5 Hensel's lemma

After running the Miller-Rabin test we are either armed with the
``certainty'' (as far as internal error-checking mechanisms within
the computer permit us to be certain!) that some number *N* is
composite or a very high probability that it is indeed prime. For some
situations neither of these is enough. We wish to offer an explicit
``proof'' by way of a factorisation of the number in the composite
case; or by a certificate or ``witness'' to its primality in the
second case. Such certificates may also be required if we wish to
prove that the factorisation we have obtained is complete!

**Subsections**

Kapil Hari Paranjape
2002-10-20