A compositeness certificate is a piece of information which guarantees that a given number 
is composite. Possible certificates consist of
a factor of a number (which, in general, is much quicker
to check by direct division than to determine initially), or of the determination
that either
 |
(i.e., 
violates Fermat's little theorem), or
 |
A quantity 
satisfying either property is said to be a witness to
's
compositeness.
