Computational Number Theory

← Back to Domain-Specific Abstractions by Domain

5 domain-specific abstractions whose origin domain is Computational Number Theory.

• Carmichael number — A composite integer that satisfies the Fermat congruence for every integer base, so it systematically imitates prime behavior under the basic Fermat test.
• Lattice problem — A computational search or approximation problem over integer lattices, such as finding unusually short, close or independent lattice vectors.
• Miller–Rabin primality test — A randomized strong-probable-prime test that repeatedly checks modular-power witnesses and bounds the chance that a composite integer passes all selected bases.
• Modular exponentiation — Computation of a power modulo a positive integer, returning the residue of a base raised to an integer exponent without constructing the full power.
• Quadratic residuosity problem — The computational decision problem of determining whether a number with Jacobi symbol one is a square modulo a composite whose prime factorization is unknown.