math concept
10 topics use this
Math concept
Number Theory
Core equation
$$a^{\phi(n)} \equiv 1 \pmod{n} \quad \text{(Euler)}$$
Number theory studies the integers and their properties. Once considered pure mathematics, it now forms the mathematical backbone of modern cryptography — RSA, elliptic curves, and lattice-based schemes all rely on number-theoretic hardness assumptions.
Modular arithmetic
$a \equiv b \pmod{n}$ means $n \mid (a-b)$. The integers mod $n$ form a ring $\mathbb{Z}/n\mathbb{Z}$.
| Euler’s theorem: for $\gcd(a,n)=1$, $a^{\phi(n)} \equiv 1 \pmod{n}$ where $\phi(n) = | {k \leq n : \gcd(k,n)=1} | $ is Euler’s totient function. RSA is a direct corollary. |
Primes and factoring
Fundamental theorem of arithmetic: every integer $> 1$ factors uniquely into primes.
Prime number theorem: $\pi(x) \sim x/\ln x$ — primes thin out logarithmically.
The integer factorisation problem — given $n = pq$, find $p,q$ — is believed hard classically but easy for quantum computers (Shor’s algorithm), breaking RSA.
The discrete logarithm problem
In a cyclic group $\mathbb{Z}_p^*$, given $g^x \bmod p$, finding $x$ is computationally hard — the basis of Diffie–Hellman and DSA security.
Fields that use this concept
Engineering & CS
Cryptography
AES Block Cipher
The Advanced Encryption Standard, a symmetric block cipher operating on 128-bit blocks with Galois field arithmetic.
Commitment Schemes
Cryptographic primitives allowing a party to commit to a value while keeping it hidden, and later reveal it with a binding guarantee.
Diffie-Hellman Key Exchange
A protocol enabling two parties to establish a shared secret over an insecure channel using discrete logarithms.
Digital Signatures
Cryptographic schemes binding a message to a signer's identity, providing authentication, integrity, and non-repudiation.
Elliptic Curve Cryptography
Public-key cryptography built on the algebraic structure of elliptic curves over finite fields.
Lattice-Based Cryptography
Post-quantum cryptographic constructions built on the computational hardness of lattice problems like LWE and SVP.
RSA Cryptosystem
A public-key cryptosystem based on the computational hardness of factoring large integers.
Secret Sharing Schemes
Methods for distributing a secret among multiple parties so that only authorized subsets can reconstruct it.
Zero-Knowledge Proofs
Interactive or non-interactive protocols enabling a prover to convince a verifier of a statement's truth without revealing any additional information.
Physical sciences
Quantum computing