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)≢1 (mod p),

(i.e., p violates Fermat's little theorem), or

 a!=-1,1 and a^2=1 (mod p).

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

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Compositeness Certificate." From MathWorld--A Wolfram Web Resource.

Subject classifications