Compositeness Certificate

A compositeness certificate is a piece of information which guarantees that a given number $p$ 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

$$a^{p-1} \not\equiv 1\ {\rm (mod\ } p),$$

(i.e., $p$ violates Fermat's Little Theorem), or

$$a\not=-1,1 {\ \rm and\ } a^2\equiv 1\ \left({{\rm mod\ } {p}}\right).$$

A quantity $a$ satisfying either property is said to be a Witness to $p$'s compositeness.

See also Adleman-Pomerance-Rumely Primality Test, Fermat's Little Theorem, Miller's Primality Test, Primality Certificate, Witness