Linked from

The 17 pages that link to Primality test, each with the reason it gives.

• Prime numberNarrower topic: Primality testing generalizes trial division to much larger integers.

• Number theoryRelated: Efficient tests make prime selection and verification feasible in computation and cryptography.

• Integer factorizationCompared with: Testing primality is much easier than finding all prime factors of a composite integer.

• Decision problemBroader topic: Primality is a concrete decision problem with an efficient algorithm.

• Quadratic reciprocityRelated: Residue computations using reciprocity can simplify some primality-testing calculations.

• RSA cryptosystemRelated: Key generation needs large primes, typically found with probabilistic primality tests.

• Quadratic residueRelated: Residue-based criteria appear in some tests distinguishing primes from composites.

• Trial divisionNarrower topic: Trial division gives a simple definitive test when the candidate range is manageable.

• Lucas sequenceNarrower topic: Special Lucas sequences underpin efficient tests for primality.

• Édouard LucasNarrower topic: Lucas’s criteria belong to the broader study of efficient primality testing.

• Fermat numberNarrower topic: Testing enormous Fermat numbers is a specialized challenge within computational primality testing.

• Sophie Germain primeRelated: Finding such a prime requires testing both p and 2p + 1 for primality.

• Wilson's theoremNarrower topic: Wilson's congruence gives a deterministic primality criterion with very high computational cost.

• Computable setBroader topic: The prime numbers form a computable set, with a polynomial-time decision algorithm.

• PseudoprimeNarrower topic: Pseudoprimes arise when a test's prime-identifying condition also accepts composites.

• Agoh–Giuga conjectureNarrower topic: The conjecture would give a direct, if computationally costly, primality criterion.

• Proth's theoremNarrower topic: Proth's theorem supplies a deterministic test for its restricted number family.