Trial division

Trial division tests whether an integer has nontrivial factors by checking candidate divisors up to its square root. It can also factor an integer by repeatedly testing primes.

Divisibility: Divisibility is the relation in which one integer is an exact multiple of another. Each trial asks whether a candidate divides the target with no remainder.
Primality test: A primality test determines whether an integer is prime or composite. Trial division gives a simple definitive test when the candidate range is manageable.
Miller–Rabin primality test: The Miller–Rabin test is a probabilistic algorithm that identifies composite numbers and reports primes with bounded error. It tests large candidates far faster, but unlike exhaustive trial division can be probabilistic.
Integer: An integer is a whole number, including zero and negative whole numbers. Trial division operates on positive integers greater than one when testing primality.
Prime number: A prime number is an integer greater than one with exactly two positive divisors: one and itself. Testing prime candidates is sufficient because every composite number has a prime factor.
Prime factorization: Prime factorization writes an integer greater than one as a product of prime powers. Repeatedly dividing by candidate primes extracts the target’s complete prime-power decomposition.
AKS primality test: The AKS primality test is a deterministic algorithm that decides primality in polynomial time. It provides a deterministic alternative whose asymptotic efficiency exceeds trial division.
Composite number: A composite number is a positive integer greater than one with a divisor other than one and itself. Finding such a divisor is exactly what makes a trial-division primality test fail.
Square root: A square root of a number is a value that, when multiplied by itself, gives that number. If no divisor is at most the square root, any larger factor would pair with a smaller one.
Wheel factorization: Wheel factorization skips candidate divisors that share factors with a chosen product of small primes. It speeds trial division by eliminating candidates already ruled out by small primes.

Linked from 12 pages