Number Theory Formula Sheet

Math for CS · Axiom Academy

Formula Sheet Number Theory Reference Compact reference of every key formula in Unit 4 Divide a by b , get quotient q and remainder r . Repeat until remainder is 0 . The last nonzero remainder is . Write the exponent k in binary: . For each bit b_i (low to high): if b_i = 1 , multiply by mod n ; then square mod n . Choose primes: pick two large primes p and q . Public exponent: pick e with and . Private exponent: compute via extended Euclidean. Public key: (n, e) . Private key: (n, d) . Public parameters: a large prime p and a generator g modulo p . Alice: picks secret a , sends . Shared secret: Alice computes B^ a , Bob computes A^ b . Both equal . Need a modular inverse? Extended Euclidean algorithm. Need for prime p ? Reduce exponent mod p - 1 (Fermat), then square-and-multiply. Need for composite n with ? Reduce exponent mod (Euler), then square-and-multiply. Solving simultaneous congruences with coprime moduli? Chinese Remainder Theorem. RSA decryption speed-up? Use CRT mod p and q separately, then recombine. Verifying primality (probabilistic)? Use Fermat / Miller-Rabin tests.

This is the written version of the interactive lesson above. See the full Math for CS course.