A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, 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 running time is polynomial in the size of the input). Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore we might call the latter compositeness tests instead of primality tests.
Read more about Primality Test: Naive Methods, Probabilistic Tests, Fast Deterministic Tests, Complexity, Number-theoretic Methods
Famous quotes containing the word test:
“I am willing, for a money consideration, to test this physical strength, this nervous force, and muscular power with which I’ve been gifted, to show that they will bear a certain strain. If I break down, if my brain gives way under want of sleep, my heart ceases to respond to the calls made on my circulatory system, or the surcharged veins of my extremities burst—if, in short, I fall helpless, or it may be, dead on the track, then I lose my money.”
—Ada Anderson (1860–?)