Number Theory and Cryptography Study Notes

Number Theory Fundamentals and Prime Numbers

  • Definition 3.3: A prime number is an integer that has exactly 22 factors (11 and itself).

    • 22 is the only even prime number.

    • 11 is not a prime number because it only has 11 factor; it is the multiplicative identity.

    • 00 is the additive identity and has no factors.

  • Integers with three or more factors are composite.

  • Twin primes are pairs of prime numbers that differ by 22 (consecutive odd integers, such as 1111 and 1313, or 1717 and 1919).

  • The distribution of primes is approximated by the prime counting function:π(x)≈xln⁡(x)\pi(x) \approx \frac{x}{\ln(x)}The exact distribution is addressed by the Riemann hypothesis.

  • Infinitude of Primes: Proved by contradiction assuming a finite list of primes p1,p2,…,pnp_1, p_2, \dots, p_n. Constructing N=p1×p2×⋯×pn+1N = p_1 \times p_2 \times \dots \times p_n + 1 results in a number not divisible by any prime in the list (leaving remainder 11), proving the existence of an additional prime.

  • Fundamental Theorem of Arithmetic: Every positive integer greater than 11 has a unique prime factorisation written in non-decreasing order:n=p1a1p2a2p3a3…n = p_1^{a_1} p_2^{a_2} p_3^{a_3} \dots

  • Prime Divisor Bound: If nn is a composite integer, then nn has a prime divisor less than or equal to n\sqrt{n}.

  • Mersenne Primes: Primes of the form 2p−12^p - 1, where pp is prime. Primality is tested using the Lucas-Lehmer test (e.g., 22−1=32^2 - 1 = 3, 23−1=72^3 - 1 = 7, 25−1=312^5 - 1 = 31).

Divisibility and Modular Arithmetic

  • Definition 3.4: For integers aa and bb with a≠0a \ne 0, aa divides bb (a∣ba \mid b) if there exists an integer cc such that b=acb = ac. If no such integer exists, a∤ba \nmid b.

  • Properties of Divisibility:

    • If a∣ba \mid b and a∣ca \mid c, then a∣(b+c)a \mid (b + c).

    • If a∣ba \mid b, then a∣bca \mid bc for all integers cc.

    • If a∣ba \mid b and b∣cb \mid c, then a∣ca \mid c.

    • The number of positive integers less than or equal to nn divisible by dd is given by ⌊nd⌋\lfloor \frac{n}{d} \rfloor.

  • Definition 3.5 (Division Algorithm): For an integer aa and a positive integer dd, there exist unique integers qq (quotient) and rr (remainder) such that:a=dq+ra = dq + rwhere 0≤r<d0 \le r < d. Here, dd is the divisor and aa is the dividend.

  • Definition 3.6: For integer aa and positive integer mm, a mod ma \bmod m denotes the unique remainder rr when aa is divided by mm (0≤r<m0 \le r < m). Integers modulo nn form the ring Zn\mathbb{Z}_n.

  • Definition 3.7: For integers a,ba, b and positive integer mm, aa is congruent to bb modulo mm (a≡b(modm)a \equiv b \pmod m) if m∣(a−b)m \mid (a - b), or equivalently a mod m=b mod ma \bmod m = b \bmod m.

  • Congruence Properties:

    • a≡b(modm)a \equiv b \pmod m if and only if a=b+kma = b + km for some integer kk.

    • If a≡b(modm)a \equiv b \pmod m and c≡d(modm)c \equiv d \pmod m, then a+c≡b+d(modm)a + c \equiv b + d \pmod m and ac≡bd(modm)ac \equiv bd \pmod m.

Ring diagram displaying integers congruent modulo 7

Greatest Common Divisor and Euclidean Algorithms

  • Definition 3.8: The greatest common divisor (or highest common factor) of non-zero integers aa and bb, denoted gcd⁡(a,b)\gcd(a, b), is the largest integer dd such that d∣ad \mid a and d∣bd \mid b.

    • Using prime factorisations:gcd⁡(a,b)=∏pimin⁡(ai,bi)\gcd(a, b) = \prod p_i^{\min(a_i, b_i)}

  • Definition 3.9: The lowest common multiple lcm(a,b)\text{lcm}(a, b) is the smallest positive integer divisible by both aa and bb:lcm(a,b)=a×bgcd⁡(a,b)\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}

    • Using prime factorisations:lcm(a,b)=∏pimax⁡(ai,bi)\text{lcm}(a, b) = \prod p_i^{\max(a_i, b_i)}

  • Definition 3.10: Two integers aa and bb are relatively prime (coprime) if gcd⁡(a,b)=1\gcd(a, b) = 1.

  • Euclidean Algorithm: Efficiently finds gcd⁡(a,b)\gcd(a, b) in O(log⁡(b))O(\log(b)) time using successive divisions based on the lemma:gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a, b) = \gcd(b, a \bmod b)The process terminates when the remainder is 00, and the last non-zero remainder equals gcd⁡(a,b)\gcd(a, b).

  • Extended Euclidean Algorithm: Expresses the greatest common divisor as a linear combination of the inputs (Bézout's identity):ax+by=gcd⁡(a,b)ax + by = \gcd(a, b)

  • Modular Inverses: An integer xx is the inverse of a(modm)a \pmod m if:ax≡1(modm)ax \equiv 1 \pmod mA unique inverse modulo mm exists if and only if gcd⁡(a,m)=1\gcd(a, m) = 1, computed by solving for xx via the Extended Euclidean algorithm.

Exponentiation and Practical Applications

  • Modular Exponentiation: The algorithm computes am mod na^m \bmod n by repeated squaring and bitwise reduction of the exponent without exceeding precision limits.

  • Fermat's Little Theorem: If pp is prime and aa is an integer:ap≡a(modp)a^p \equiv a \pmod pIf p∤ap \nmid a, then:ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p

  • Euler's Totient Theorem: Generalisation stating that if gcd⁡(a,n)=1\gcd(a, n) = 1, then:aϕ(n)≡1(modn)a^{\phi(n)} \equiv 1 \pmod nwhere ϕ(n)\phi(n) is Euler's totient function, which counts the number of integers up to nn coprime to nn.

  • Hash Functions: One-way mappings h(k)=k mod Mh(k) = k \bmod M assigning key kk to memory bucket MM. Collisions occur when h(k1)=h(k2)h(k_1) = h(k_2) due to non-injective mapping.

  • Pseudorandom Numbers: Generated recursively via the linear congruential method:xn+1=(axn+c) mod mx_{n+1} = (ax_n + c) \bmod mA generator with c=0c = 0 is a pure multiplicative generator (e.g., multiplier 75=168077^5 = 16807 and modulus 231−12^{31} - 1 yielding period 231−22^{31} - 2).

  • ISBN-13 Codes: Error-detection scheme evaluated using alternating weights of 11 and 33:∑wixi≡0(mod10)\sum w_i x_i \equiv 0 \pmod{10}

  • Error-Correcting Codes: Redundancy schemes such as repetition codes (tripling bits: 0→0000 \to 000, 1→1111 \to 111) detect and correct single-bit channel errors via majority logic.

  • Hamming Distance: Definition 3.5 establishes d(x,y)d(x, y) as the number of corresponding positions in which binary strings xx and yy differ.

Abstract Algebra and Complex Numbers

  • Single Binary Operator Structures: Ordered by increasing axiomatic complexity:Magma→Quasigroup→Semigroup→Monoid→Group→Abelian Group\text{Magma} \to \text{Quasigroup} \to \text{Semigroup} \to \text{Monoid} \to \text{Group} \to \text{Abelian Group}

    • Magma: Closed under binary operation (a∘b∈Sa \circ b \in S).

    • Semigroup: Associative magma ((a∘b)∘c=a∘(b∘c)(a \circ b) \circ c = a \circ (b \circ c)).

    • Monoid: Semigroup with identity element ee (a∘e=e∘a=aa \circ e = e \circ a = a).

    • Group: Monoid with unique inverses (a∘b=b∘a=ea \circ b = b \circ a = e).

    • Abelian Group: Commutative group (a∘b=b∘aa \circ b = b \circ a).

Hasse diagram showing algebraic structures with a single binary operation
  • Two Binary Operator Structures:

    • Ring: Abelian group under addition, monoid under multiplication, and distributive.

    • Field: Ring whose non-zero elements form an Abelian group under multiplication (e.g., R\mathbb{R}, or Zp\mathbb{Z}_p where pp is prime).

  • Gödel's Incompleteness Theorem (1931): A consistent axiomatic system cannot prove all true statements about natural numbers.

  • Complex Numbers: Defined as z=x+iyz = x + iy, with real part Re(z)=x\text{Re}(z) = x, imaginary part Im(z)=y\text{Im}(z) = y, and i2=−1i^2 = -1.

    • Complex Conjugate: zˉ=z∗=x−iy\bar{z} = z^* = x - iy.

    • Modulus (Magnitude): ∣z∣=x2+y2|z| = \sqrt{x^2 + y^2}.

    • Argument: arg⁡(z)=tan⁡−1(yx)\arg(z) = \tan^{-1}\left(\frac{y}{x}\right).

    • Polar Form: z=reiθz = r e^{i\theta}.

Argand diagram showing complex number z with cartesian coordinates x and y and polar coordinates r and theta

Classical Cryptography

  • Kerckhoffs's Principle: A cryptographic system must remain secure even if its entire mechanism is known to the adversary ("the enemy knows the system").

Symmetric cryptosystem model with Alice, Bob, Eve, plaintext, ciphertext, and secret key
  • Caesar Cipher: Monoalphabetic shift of nn positions (n=3n = 3 historically):E=(x+n) mod 26E = (x + n) \bmod 26C = (x - n) \bmod 26\n* Affine Cipher: Uses a linear transformation:E(x) = (ax + b) \bmod 26RequiresRequires\gcd(a, 26) = 1.Thereare. There are12validvaluesforvalid values fora,yielding, yielding12 \times 26 = 312totalkeys.Decryptioniscomputedvia:total keys. Decryption is computed via:D(y) = a^{-1}(y - b) \bmod 26\n* Substitution Cipher: Uses arbitrary permutations of the alphabet (26! keys); vulnerable to frequency analysis.\n* Pigpen Cipher: Monoalphabetic geometric substitution cipher mapping letters to grid fragments and dots.\n\n![Pigpen cipher geometric grid assignments](https://assets.knowt.com/pdf-flow-prod/73c994b7-66f8-4924-9e6a-a1865c07994e-figures/8.png)\n\n* Vigenère Cipher: Polyalphabetic shift using a repeating keyword; susceptible to the Kasiski examination.\n* One-Time Pad: Perfectly secure symmetric cipher proven by Claude Shannon using a truly random key Kofequallengthtoplaintextof equal length to plaintextM::C = M \oplus KM=C⊕KM = C \oplus K

Modern and Public Key Cryptography

  • Modern Block Ciphers: Operates on fixed-size blocks via rounds of substitution and permutation transformations (e.g., DES, AES).

Structure of the Advanced Encryption Standard showing round keys, byte substitution, row shifts, and mix columns
  • RSA Cryptosystem: Asymmetric algorithm invented by Ron Rivest, Adi Shamir, Leonard Adleman, and independently Clifford Cocks:

    • Key Generation:

    • Choose large primes pp and qq, calculate n=pqn = pq, and totient ϕ(n)=(p−1)(q−1)\phi(n) = (p - 1)(q - 1).

    • Select public exponent ee such that gcd⁡(e,ϕ(n))=1\gcd(e, \phi(n)) = 1.

    • Compute private exponent dd such that de≡1(modϕ(n))de \equiv 1 \pmod{\phi(n)}.

    • Encryption:C=Me mod nC = M^e \bmod n

    • Decryption:M=Cd mod nM = C^d \bmod n

Primality Testing and Integer Factorisation

  • Sieve of Eratosthenes: Deterministic method finding all primes up to nn by sequentially crossing out multiples of each discovered prime kk starting at k2k^2.

Sieve of Eratosthenes table up to 100
  • Miller-Rabin Primality Test: Probabilistic test writing odd n−1=2srn - 1 = 2^s r with rr odd:

    • A base aa is a strong witness to compositeness if:ar≢1(modn)a^r \not\equiv 1 \pmod nanda2jr≢−1(modn)a^{2^j r} \not\equiv -1 \pmod nfor all 0≤j≤s−10 \le j \le s - 1.

    • If nn is composite and n≠9n \ne 9, at most ϕ(n)4\frac{\phi(n)}{4} bases are strong liars.

  • Pollard's Rho Algorithm: Factorisation method searching for cycle collisions using f(x)=(x2+1) mod nf(x) = (x^2 + 1) \bmod n:

    • Updates a=f(a)a = f(a) and b=f(f(b))b = f(f(b)).

    • Computes d=gcd⁡(a−b,n)d = \gcd(a - b, n) until a non-trivial factor 1<d<n1 < d < n is discovered.

Pollard rho algorithm cycle trajectory diagram

Questions & Discussion

  • Q1: Find the binary expansion of 547547.

  • Q2: Evaluate k mod 5k \bmod 5 for integers k∈{1,2,3,4,5,6,7,8,9,10}k \in \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}.

  • Q3: Calculate the modular reductions: 11 mod 211 \bmod 2, 11 mod 611 \bmod 6, 12 mod 612 \bmod 6, 12 mod 712 \bmod 7, 13 mod 713 \bmod 7, and 14 mod 714 \bmod 7.

  • Q4: Use the division algorithm to divide aa by bb yielding quotient qq and remainder rr for:

    • a=88,b=11a = 88, b = 11

    • a=31,b=3a = 31, b = 3

    • a=−29,b=9a = -29, b = 9

  • Q5: Calculate the greatest common divisors: gcd⁡(10,25)\gcd(10, 25), gcd⁡(18,15)\gcd(18, 15), gcd⁡(7,7)\gcd(7, 7), and gcd⁡(19,25)\gcd(19, 25).

  • Q6: Use the Euclidean algorithm to find the greatest common divisor for pairs (91,104)(91, 104) and (32,78)(32, 78).

  • Q7: Find integers xx and yy such that ax+by=gcd⁡(a,b)ax + by = \gcd(a, b) for pairs (91,104)(91, 104) and (32,78)(32, 78).

  • Q8: Determine primality for 21,29,71,11121, 29, 71, 111 and compute prime factorisations for 136,487,6600136, 487, 6600.

  • Q9: Verify that 1515 is the inverse of 7(mod26)7 \pmod{26}.

  • Q10: Find the inverse of 13 mod 6013 \bmod 60.

  • Q11: Encrypt "DO NOT PASS" using numeric substitution with f(p)=(p+3) mod 26f(p) = (p + 3) \bmod 26 and f(p)=(p+13) mod 26f(p) = (p + 13) \bmod 26.

  • Q12: Decrypt the Caesar ciphertext "EOXH MHDQV".

  • Q13 (Challenge): Show that n=pqn = pq can be factored if nn and (p−1)(q−1)(p - 1)(q - 1) are both known.

  • Q14: Encrypt "UPLOAD" using RSA with n=5×13n = 5 \times 13 and e=7e = 7.

  • Q15: Decrypt the RSA message "50 26 46 69 61" with n=7×11n = 7 \times 11 and e=13e = 13.

  • Q16: Contrast the discrete logarithm problem and Elliptic Curve Cryptography with RSA.

  • Q17: Mitigation strategies against frequency analysis when encoding single letters into RSA.

  • Q18: Implementation of hybrid cryptosystems using RSA for symmetric key exchange and block ciphers for data encryption.