Public-Key Cryptography

Symmetric cryptography (AES, ChaCha20) is fast and secure, but it has a fatal bootstrapping problem: both parties must share the same secret key before they can communicate privately. If Alice wants to send a secret message to Bob, she first needs to securely exchange a key with Bob — but if she already had a secure channel to do that, she wouldn't need the encryption in the first place. This circular dependency is the key distribution problem.

Formally: given n parties who want pairwise-secure communication, symmetric cryptography requires O(n²) pre-shared keys. With a billion users on the internet, this is completely impractical. Even with a trusted Key Distribution Center (KDC), the KDC becomes a single point of failure and must hold every secret.

Diffie and Hellman's insight (1976) was that secrecy doesn't require a pre-shared secret — it only requires that the two parties can perform a computation that an eavesdropper cannot reproduce. They introduced two revolutionary concepts:

1. Asymmetric key pairs: a public key (shareable) and a private key (secret), mathematically linked.
2. Trapdoor one-way functions: functions f where computing f(x) is easy but inverting f(y) to recover x is computationally infeasible — unless you know the trapdoor (the private key).

This transforms the security model. Instead of 'we must meet in secret first,' it becomes 'I publish a mathematical lock; you close it; only I can open it.'

# The key-distribution problem illustrated
# n=5 users needing pairwise keys
n = 5
symmetric_keys_needed = n * (n - 1) // 2  # = 10
asymmetric_keys_needed = n * 2            # = 10 (5 key pairs total)

# With n=1_000_000 users:
n = 1_000_000
print(f'Symmetric: {n*(n-1)//2:,} keys')    # 499,999,500,000
print(f'Asymmetric: {n*2:,} keys')          # 2,000,000

A one-way function is a function f: {0,1}* → {0,1}* such that:

• f(x) is computable in polynomial time
• For any probabilistic polynomial-time adversary A: Pr[A(f(x)) = x] is negligible

The existence of one-way functions is not proven — it would imply P ≠ NP — but we have strong candidates based on problems believed to be hard.

A trapdoor one-way function adds a twist: there exists secret information (the trapdoor) such that given the trapdoor, inverting f becomes easy. This is exactly what a private key is: the trapdoor that makes decryption easy for the holder and infeasible for everyone else.

Concrete examples of trapdoor candidates:

The word 'hard' means 'no known polynomial-time algorithm exists, and the best known algorithms require sub-exponential or exponential time in the security parameter.' For RSA-2048, the best factoring algorithm (General Number Field Sieve) requires roughly 2^112 operations — comparable to AES-128 security.

# One-way: easy to compute, hard to invert
import sympy

# Forward: multiply two primes -> FAST (microseconds)
p = sympy.nextprime(2**511)
q = sympy.nextprime(2**512)
n = p * q          # 1024-bit number, instant

# Inverse: factor n -> INFEASIBLE for large n
# Best known: General Number Field Sieve ~exp((64/9)^(1/3) * (ln n)^(1/3) * (ln ln n)^(2/3))
# For n ~ 2^1024: roughly 2^140 operations

RSA and Diffie-Hellman are built on modular arithmetic. Here are the essential facts:

Modular exponentiation computes x^e mod n efficiently using repeated squaring in O(log e) multiplications — this is what makes encryption fast.

Euler's totient function φ(n) counts the integers from 1 to n that are coprime to n. Key facts:

• If p is prime: φ(p) = p-1
• If p, q are distinct primes: φ(pq) = (p-1)(q-1)
• Euler's theorem: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). This is the algebraic heart of RSA.

Fermat's Little Theorem (special case): if p is prime, then a^(p-1) ≡ 1 (mod p) for any a not divisible by p.

The multiplicative group (Z/nZ)*: the set of integers mod n that have a multiplicative inverse. This set forms a group under multiplication. Its order (size) is φ(n). RSA arithmetic lives inside this group.

Why this matters for RSA: if we choose e such that d·e ≡ 1 (mod φ(n)), then for any message m: (m^e)^d = m^(e·d) = m^(1 + k·φ(n)) = m · (m^φ(n))^k ≡ m · 1^k = m (mod n)

Encryption and decryption are multiplicative inverses of each other in the exponent, and the inverses cancel because of Euler's theorem.

def mod_exp(base, exp, mod):
    """Fast modular exponentiation: O(log exp) multiplications."""
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:           # exp is odd
            result = result * base % mod
        exp >>= 1
        base = base * base % mod
    return result

def euler_totient(p, q):
    """For RSA semiprime n = p*q."""
    return (p - 1) * (q - 1)

# Verify Euler's theorem: a^phi(n) ≡ 1 (mod n)
p, q = 61, 53
n = p * q          # 3233
phi = euler_totient(p, q)  # 3120
a = 1234
assert mod_exp(a, phi, n) == 1  # always true when gcd(a,n)=1

RSA (1977) was the first practical public-key cryptosystem. Its security rests on the RSA problem: given n = p·q and c = m^e mod n, recover m. This is believed to require factoring n, which is computationally infeasible for large n.

Key Generation:

1. Choose two large random primes p and q (2048-bit each in practice, giving 4096-bit n)
2. Compute n = p·q (the modulus) and φ(n) = (p-1)(q-1)
3. Choose public exponent e: typically 65537 = 2^16 + 1 (small, has only two 1-bits, fast to compute, odd, and coprime to most φ(n))
4. Compute private exponent d = e^(-1) mod φ(n) using the Extended Euclidean Algorithm
5. Public key: (e, n). Private key: (d, n). Destroy p, q, φ(n).

Encryption: c = m^e mod n Decryption: m = c^d mod n

Why decryption works: c^d = (m^e)^d = m^(ed). Since ed ≡ 1 (mod φ(n)), we have ed = 1 + k·φ(n) for some integer k. By Euler's theorem, m^φ(n) ≡ 1 (mod n), so m^(ed) = m^(1+kφ(n)) = m · (m^φ(n))^k ≡ m · 1 = m (mod n).

Digital signatures with RSA reverse the roles: sign with the private key (compute s = m^d mod n), verify with the public key (check that s^e ≡ m mod n). Only the private-key holder can sign; anyone can verify.

Critical practical notes:

• Raw RSA (textbook RSA) is not semantically secure — same plaintext always produces the same ciphertext. Real systems use OAEP padding (Optimal Asymmetric Encryption Padding) which randomizes encryption.
• RSA is slow — roughly 1000x slower than AES. In practice, RSA encrypts a random session key (e.g. an AES-256 key), and AES encrypts the actual data. This is called a hybrid cryptosystem.
• For signatures, you hash the message first (SHA-256), then sign the hash. Signing a 4MB file takes microseconds, not minutes.

from math import gcd

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(e, phi):
    g, x, _ = extended_gcd(e % phi, phi)
    if g != 1:
        raise ValueError('No inverse')
    return x % phi

def mod_exp(b, exp, mod):  # fast exponentiation
    r = 1; b %= mod
    while exp > 0:
        if exp & 1: r = r * b % mod
        exp >>= 1; b = b * b % mod
    return r

# --- RSA toy example (use small primes for illustration) ---
p, q = 61, 53
n = p * q          # 3233
phi = (p-1)*(q-1)  # 3120
e = 17             # public exponent (gcd(17,3120)==1)
d = mod_inverse(e, phi)  # 2753

# Encrypt m=65
m = 65
c = mod_exp(m, e, n)   # c = 2790
assert mod_exp(c, d, n) == m  # decryption recovers 65

# Digital signature
s = mod_exp(m, d, n)   # sign with private key
assert mod_exp(s, e, n) == m  # verify with public key

Diffie-Hellman (1976) solves the key-exchange problem directly: two parties who have never met can establish a shared secret over a public channel, with an eavesdropper unable to learn the secret.

The discrete logarithm problem (DLP): given a prime p, a generator g of the multiplicative group (Z/pZ)*, and a value h = g^x mod p, find x. No efficient classical algorithm is known for large p. The best general algorithm (Index Calculus) runs in sub-exponential time, requiring p ≈ 2048 bits for 128-bit security.

The Diffie-Hellman protocol:

1. Alice and Bob publicly agree on parameters: a large prime p and generator g (this is non-secret)
2. Alice picks secret a, computes A = g^a mod p, sends A to Bob
3. Bob picks secret b, computes B = g^b mod p, sends B to Alice
4. Alice computes K = B^a = g^(ba) mod p
5. Bob computes K = A^b = g^(ab) mod p
6. K = g^(ab) mod p is the shared secret. An eavesdropper sees p, g, A, B but cannot compute g^(ab) from these without solving the Computational Diffie-Hellman (CDH) problem.

The CDH assumption: given g^a and g^b, it is computationally infeasible to compute g^(ab). This is at least as hard as DLP, and is widely believed to be equivalent.

Important caveat — no authentication: vanilla DH is vulnerable to a man-in-the-middle attack. Mallory can intercept A and B, substitute her own values, and establish separate shared secrets with Alice and Bob. Real protocols (TLS, Signal) authenticate the DH exchange using digital signatures (certificates in TLS, long-term identity keys in Signal).

Decisional DH (DDH): an even stronger assumption — given g^a, g^b, you cannot even distinguish g^(ab) from a random group element. DDH holds in many groups and is the basis for El Gamal encryption.

import secrets

# Public parameters (in practice, use RFC 3526 / RFC 7919 groups)
# For illustration, use small numbers; real p must be ~2048 bits
P = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74  # 256-bit MODP group prime (truncated for illustration)
G = 2  # standard generator

def dh_keypair(p, g):
    private = secrets.randbelow(p - 2) + 2   # in [2, p-2]
    public  = pow(g, private, p)              # g^private mod p
    return private, public

def dh_shared(their_public, my_private, p):
    return pow(their_public, my_private, p)   # their_pub^my_priv mod p

# Alice
a_priv, A = dh_keypair(P, G)
# Bob
b_priv, B = dh_keypair(P, G)

# Exchange A <-> B over public channel
Ka = dh_shared(B, a_priv, P)   # Alice computes B^a
Kb = dh_shared(A, b_priv, P)   # Bob computes A^b
assert Ka == Kb  # shared secret established

Elliptic curves are not ellipses — the name comes from their relation to elliptic integrals. An elliptic curve over a field F is the set of points (x, y) satisfying:

y² = x³ + ax + b (plus a point at infinity O)

where the discriminant 4a³ + 27b² ≠ 0 (ensuring no cusps or self-intersections).

Why curves? The group law. You can define an addition operation on the points of an elliptic curve that makes them an abelian group:

• P + Q: draw the line through P and Q, find the third intersection with the curve, reflect over the x-axis. That reflected point is P + Q.
• P + P (doubling): use the tangent line at P.
• Identity: the point at infinity O acts as 0.

Scalar multiplication: k·P = P + P + ... + P (k times). This is fast using the double-and-add algorithm (analogous to repeated squaring).

The Elliptic Curve Discrete Logarithm Problem (ECDLP): given points P and Q = k·P, find k. Over carefully chosen curves and finite fields, no sub-exponential algorithm is known for ECDLP, unlike the DL problem in Z/pZ. This is what makes ECC so powerful: a 256-bit ECC key provides roughly the same security as a 3072-bit RSA key.

ECC over finite fields: in practice, we work over F_p (integers mod a prime p) or F_{2^m}. The curve parameters are chosen by standards bodies (NIST P-256, P-384; Curve25519 by Bernstein; secp256k1 used by Bitcoin).

ECDH (Elliptic Curve Diffie-Hellman): replace g^a with a·G (scalar multiplication on the curve). Alice computes a·G, Bob computes b·G; shared secret is a·(b·G) = b·(a·G) = (ab)·G.

Curve25519: designed by Dan Bernstein for speed and resistance to implementation errors. Uses the Montgomery curve y² = x³ + 486662x² + x over F_{2^255 - 19}. The prime 2^255 - 19 is chosen for fast reduction. This curve is used in TLS 1.3, Signal, WireGuard, and SSH.

# Elliptic curve arithmetic over F_p (simplified, educational)
# Real implementations use constant-time code and standard libraries.

class Point:
    def __init__(self, x, y, curve):
        self.x = x; self.y = y; self.curve = curve
    def is_infinity(self):
        return self.x is None

INFINITY = Point(None, None, None)  # identity element

def point_add(P, Q, a, p):
    """Add two points on y^2 = x^3 + ax + b over F_p."""
    if P.is_infinity(): return Q
    if Q.is_infinity(): return P
    if P.x == Q.x and (P.y + Q.y) % p == 0:
        return INFINITY  # P + (-P) = O
    if P.x == Q.x and P.y == Q.y:  # point doubling
        lam = (3 * P.x**2 + a) * pow(2 * P.y, -1, p) % p
    else:                           # point addition
        lam = (Q.y - P.y) * pow(Q.x - P.x, -1, p) % p
    xr = (lam**2 - P.x - Q.x) % p
    yr = (lam * (P.x - xr) - P.y) % p
    return Point(xr, yr, P.curve)

def scalar_mult(k, P, a, p):
    """Double-and-add: compute k*P."""
    result = INFINITY
    addend = P
    while k > 0:
        if k & 1:
            result = point_add(result, addend, a, p)
        addend = point_add(addend, addend, a, p)
        k >>= 1
    return result

# Toy curve: y^2 = x^3 - x + 1 over F_97
a, b, field_p = -1, 1, 97
G = Point(3, 6, 'toy')  # a known point on this curve

k = 7
kG = scalar_mult(k, G, a, field_p)
print(f'7G = ({kG.x}, {kG.y})')

In cryptography, 'secure' is not a feeling — it is a precisely defined property relative to a computational assumption. This is the provable security paradigm, pioneered by Goldwasser, Micali, and Rivest.

Security definitions: We define security games. For example, IND-CPA (indistinguishability under chosen-plaintext attack): an adversary who can encrypt any messages of their choice cannot distinguish the encryption of m₀ from the encryption of m₁ with probability better than 1/2 + negligible(λ), where λ is the security parameter.

Reductions: We prove 'if you can break scheme X, you can solve hard problem Y.' For example: 'if RSA-OAEP is broken (IND-CCA2 sense), then the RSA problem can be solved.' This means breaking RSA-OAEP is at least as hard as the RSA problem. The security of the scheme reduces to the hardness of the underlying math.

The hardness hierarchy for our three systems:

FACTORING → RSA PROBLEM → RSA-OAEP IND-CCA2 security
DLP (mod p) → CDH → DDH → El Gamal IND-CPA security
ECDLP → ECDH → ECDH-based scheme security

Arrows mean 'breaking the left implies solving the right is easy.' The further right, the weaker the assumption needed.

Why 112-bit security for RSA-2048? The General Number Field Sieve (GNFS) factors an L-smooth number n in time L[1/3, 1.923] — sub-exponential in the number of bits. For n ≈ 2^{2048}, this translates to roughly 2^{112} operations. For ECDLP on a 256-bit curve, the best algorithm is Pollard's rho: O(√(group order)) ≈ O(2^{128}). This is why 256-bit ECC ≈ 3072-bit RSA in security.

Post-quantum threat: Shor's algorithm (1994) solves both integer factorization and discrete logarithm in polynomial time on a quantum computer. This would break RSA, DH, and ECC simultaneously. NIST standardized post-quantum algorithms in 2024: CRYSTALS-Kyber (key encapsulation) and CRYSTALS-Dilithium (signatures), both based on Learning With Errors (LWE) over lattices, which has no known quantum speedup.

# Security level comparison
# Source: NIST SP 800-57 Part 1 Rev. 5

security_levels = {
    # (RSA key size, ECC key size, symmetric equivalent)
    80:  (1024, 160,  'DES-equivalent (deprecated)'),
    112: (2048, 224,  'Triple-DES equivalent'),
    128: (3072, 256,  'AES-128 equivalent'),
    192: (7680, 384,  'AES-192 equivalent'),
    256: (15360, 521, 'AES-256 equivalent'),
}

print(f'{"Bits":>6}  {"RSA":>7}  {"ECC":>5}  Note')
for bits, (rsa, ecc, note) in security_levels.items():
    print(f'{bits:>6}  {rsa:>7}  {ecc:>5}  {note}')

# Conclusion: ECC-256 provides 128-bit security with keys
# 12x smaller than RSA-3072. Smaller keys = faster TLS,
# smaller certificates, less bandwidth.

Pure asymmetric cryptography is 1000x slower than symmetric encryption. The solution universally adopted in practice is the hybrid cryptosystem: use asymmetric cryptography to establish a shared secret, then use that secret as the key for fast symmetric encryption.

The standard pattern:

1. Key Encapsulation Mechanism (KEM): use RSA or ECDH to securely transmit (or derive) a random session key K.
2. Data Encapsulation Mechanism (DEM): use K with AES-GCM or ChaCha20-Poly1305 to encrypt the actual data.
3. Authentication: use signatures (RSA-PSS, ECDSA, Ed25519) to bind public keys to identities via certificates.

TLS 1.3 key exchange (the protocol behind HTTPS): TLS 1.3 mandates forward secrecy by requiring ephemeral Diffie-Hellman (ECDHE). The handshake is:

1. Client sends: ClientHello + list of supported groups + ephemeral public key share
2. Server responds: ServerHello + server's ephemeral public key + certificate (signed by CA) + server Finished
3. ECDH is performed: both derive the same master secret
4. Session keys derived via HKDF; all further data encrypted with AES-128-GCM or ChaCha20-Poly1305

Forward secrecy: even if the server's long-term private key is compromised later, past sessions cannot be decrypted because the ephemeral DH keys were deleted. This is a fundamental improvement over RSA key exchange (used in TLS 1.2), where recording the TLS traffic and later stealing the private key would decrypt all past sessions.

Ed25519 signatures: EdDSA over Curve25519. 64-byte signatures, 32-byte public keys, extremely fast (verify in ~60 microseconds). Used in SSH, TLS, Signal, and GPG. Deterministic: no random number generator failures possible (unlike ECDSA, where a bad RNG in the signing process leaked Sony PS3's private key in 2010).

# Conceptual hybrid encryption (using Python's cryptography library)
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
import os

# --- SENDER ---
# Generate ephemeral ECDH keypair (Curve25519)
ephemeral_priv = X25519PrivateKey.generate()
ephemeral_pub  = ephemeral_priv.public_key()

# Recipient's long-term public key (received out-of-band)
recipient_priv = X25519PrivateKey.generate()          # (normally pre-existing)
recipient_pub  = recipient_priv.public_key()

# Perform ECDH -> shared secret
shared_secret = ephemeral_priv.exchange(recipient_pub)

# Derive AES key from shared secret via HKDF-SHA256
symmetric_key = HKDF(
    algorithm=hashes.SHA256(), length=32,
    salt=None, info=b'hybrid-demo'
).derive(shared_secret)

# Encrypt with AES-256-GCM (authenticated encryption)
nonce = os.urandom(12)
ct = AESGCM(symmetric_key).encrypt(nonce, b'Hello, World!', None)

# --- RECEIVER ---
shared_secret2 = recipient_priv.exchange(ephemeral_pub)
symmetric_key2 = HKDF(
    algorithm=hashes.SHA256(), length=32,
    salt=None, info=b'hybrid-demo'
).derive(shared_secret2)
pt = AESGCM(symmetric_key2).decrypt(nonce, ct, None)
assert pt == b'Hello, World!'

Encryption solves confidentiality, but who signed this? Digital signatures solve authentication and non-repudiation: they bind a message to a private key holder in a way anyone can verify but only the key holder can produce.

RSA signatures: Sign(m, sk) = H(m)^d mod n. Verify(m, sig, pk) = (sig^e mod n == H(m)). Security: existential unforgeability under chosen-message attack (EUF-CMA).

ECDSA (used in TLS, Bitcoin, code signing): Deterministic variant (RFC 6979) is preferred to avoid RNG failures. Each signature is (r, s) where r = x-coordinate of k·G for random k, and s = k^{-1}(H(m) + r·priv) mod n.

Ed25519 (EdDSA): deterministic, based on Schnorr signatures over Curve25519. Signing is deterministic (k derived from private key and message via hash), so no RNG needed. Faster than ECDSA, simpler to implement correctly.

The trust problem: knowing a public key is not enough — you must trust that the key belongs to who they claim. This is the Public Key Infrastructure (PKI) problem.

Certificate Authorities (CAs): a CA is a trusted third party that signs X.509 certificates binding a public key to an identity (domain name, organization). Your browser ships with ~150 trusted root CAs. When you visit https://example.com, the server presents a certificate chain: 'example.com's public key' signed by an Intermediate CA, signed by a Root CA your browser trusts.

Limitations of CAs: any compromised CA can forge certificates for any domain (DigiNotar hack, 2011). Mitigations include Certificate Transparency (CT) logs (append-only, auditable), HPKP (deprecated), and CAA DNS records. The Signal protocol uses a different model: Trust On First Use (TOFU) with key transparency, avoiding CAs entirely.

Web of Trust (PGP): instead of hierarchical CAs, PGP uses a decentralized trust graph where users sign each other's keys. Powerful in principle, practically difficult to maintain.

# Ed25519 sign and verify (Python cryptography library)
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey

# Key generation
private_key = Ed25519PrivateKey.generate()
public_key  = private_key.public_key()

# Sign a message
message   = b'Transfer $1000 to Alice'
signature = private_key.sign(message)
print(f'Signature length: {len(signature)} bytes')  # always 64 bytes

# Verify (anyone with the public key can do this)
try:
    public_key.verify(signature, message)
    print('Signature valid')
except Exception:
    print('Signature INVALID')

# Tamper detection
tampered = b'Transfer $9000 to Alice'
try:
    public_key.verify(signature, tampered)
except Exception:
    print('Tampering detected')  # always raised

The Extended Euclidean Algorithm (EEA) is the engine under the hood of RSA and many other cryptographic primitives. It computes not only gcd(a, b) but also the Bezout coefficients x, y such that:

ax + by = gcd(a, b)

If gcd(e, φ(n)) = 1 (a requirement in RSA key generation), then:

e·x + φ(n)·y = 1 ⟹ e·x ≡ 1 (mod φ(n))

So x is the modular inverse of e modulo φ(n) — that is, x = d, the RSA private key exponent.

The algorithm is a simple extension of Euclid's algorithm, which is based on the fact that gcd(a, b) = gcd(b, a mod b). At each step we track how the current remainder is a linear combination of the original a and b. The algorithm terminates in O(log(min(a,b))) steps.

Miller-Rabin primality test: RSA requires generating large primes. We can't trial-divide a 1024-bit number. The Miller-Rabin test is a probabilistic primality test based on Fermat's little theorem and properties of square roots of 1 modulo primes. It runs in O(k log²n) time where k is the number of rounds. With k=40, the probability of falsely declaring a composite prime is less than 4^{-40} ≈ 10^{-24}. Python's sympy.isprime and OpenSSL both use Miller-Rabin.

Chinese Remainder Theorem (CRT) for fast RSA: since we know the factors p and q, we can compute RSA decryption modulo p and q separately (4x faster), then combine using CRT. This is the standard optimization in all RSA implementations.

def extended_gcd(a, b):
    """Returns (gcd, x, y) such that a*x + b*y = gcd."""
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    return gcd, y1, x1 - (a // b) * y1

def mod_inverse(e, m):
    """Modular inverse of e mod m (exists iff gcd(e,m)=1)."""
    gcd, x, _ = extended_gcd(e, m)
    if gcd != 1:
        raise ValueError(f'No inverse: gcd({e},{m})={gcd}')
    return x % m

# RSA private key computation
e   = 65537
phi = (61 - 1) * (53 - 1)  # = 3120, for p=61, q=53
d   = mod_inverse(e, phi)   # = 2753

# Verify: e*d ≡ 1 (mod phi)
assert (e * d) % phi == 1

# Miller-Rabin primality test (simplified)
def miller_rabin(n, k=20):
    import random
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1; d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x in (1, n - 1): continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1: break
        else:
            return False  # definitely composite
    return True  # probably prime