5 Factorisation and Certificates

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!