info prev up next book cdrom email home

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

\begin{displaymath}
a^{p-1} \not\equiv 1\ {\rm (mod\ } p),
\end{displaymath}

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

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

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




© 1996-9 Eric W. Weisstein
1999-05-26