Editing Primality test (section)

{{Short description|Algorithm for determining whether a number is prime}}
A '''primality test''' is an [[algorithm]] for determining whether an input number is [[prime number|prime]]. Among other fields of [[mathematics]], it is used for [[cryptography]]. Unlike [[integer factorization]], primality tests do not generally give [[prime factor]]s, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its [[Run-time complexity|running time]] is [[Polynomial time|polynomial]] in the size of the input). Some primality tests prove that a number is prime, while others like [[Miller–Rabin primality test|Miller–Rabin]] prove that a number is [[Composite number|composite]]. Therefore, the latter might more accurately be called ''compositeness tests'' instead of primality tests.