## Compositeness Certificate

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.