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
See also Adleman-Pomerance-Rumely Primality Test, Fermat's Little Theorem, Miller's Primality Test, Primality Certificate, Witness