Number Theory and Cryptography Study Notes
Number Theory Fundamentals and Prime Numbers
Definition 3.3: A prime number is an integer that has exactly factors ( and itself).
is the only even prime number.
is not a prime number because it only has factor; it is the multiplicative identity.
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 (consecutive odd integers, such as and , or and ).
The distribution of primes is approximated by the prime counting function:The exact distribution is addressed by the Riemann hypothesis.
Infinitude of Primes: Proved by contradiction assuming a finite list of primes . Constructing results in a number not divisible by any prime in the list (leaving remainder ), proving the existence of an additional prime.
Fundamental Theorem of Arithmetic: Every positive integer greater than has a unique prime factorisation written in non-decreasing order:
Prime Divisor Bound: If is a composite integer, then has a prime divisor less than or equal to .
Mersenne Primes: Primes of the form , where is prime. Primality is tested using the Lucas-Lehmer test (e.g., , , ).
Divisibility and Modular Arithmetic
Definition 3.4: For integers and with , divides () if there exists an integer such that . If no such integer exists, .
Properties of Divisibility:
If and , then .
If , then for all integers .
If and , then .
The number of positive integers less than or equal to divisible by is given by .
Definition 3.5 (Division Algorithm): For an integer and a positive integer , there exist unique integers (quotient) and (remainder) such that:where . Here, is the divisor and is the dividend.
Definition 3.6: For integer and positive integer , denotes the unique remainder when is divided by (). Integers modulo form the ring .
Definition 3.7: For integers and positive integer , is congruent to modulo () if , or equivalently .
Congruence Properties:
if and only if for some integer .
If and , then and .

Greatest Common Divisor and Euclidean Algorithms
Definition 3.8: The greatest common divisor (or highest common factor) of non-zero integers and , denoted , is the largest integer such that and .
Using prime factorisations:
Definition 3.9: The lowest common multiple is the smallest positive integer divisible by both and :
Using prime factorisations:
Definition 3.10: Two integers and are relatively prime (coprime) if .
Euclidean Algorithm: Efficiently finds in time using successive divisions based on the lemma:The process terminates when the remainder is , and the last non-zero remainder equals .
Extended Euclidean Algorithm: Expresses the greatest common divisor as a linear combination of the inputs (Bézout's identity):
Modular Inverses: An integer is the inverse of if:A unique inverse modulo exists if and only if , computed by solving for via the Extended Euclidean algorithm.
Exponentiation and Practical Applications
Modular Exponentiation: The algorithm computes by repeated squaring and bitwise reduction of the exponent without exceeding precision limits.
Fermat's Little Theorem: If is prime and is an integer:If , then:
Euler's Totient Theorem: Generalisation stating that if , then:where is Euler's totient function, which counts the number of integers up to coprime to .
Hash Functions: One-way mappings assigning key to memory bucket . Collisions occur when due to non-injective mapping.
Pseudorandom Numbers: Generated recursively via the linear congruential method:A generator with is a pure multiplicative generator (e.g., multiplier and modulus yielding period ).
ISBN-13 Codes: Error-detection scheme evaluated using alternating weights of and :
Error-Correcting Codes: Redundancy schemes such as repetition codes (tripling bits: , ) detect and correct single-bit channel errors via majority logic.
Hamming Distance: Definition 3.5 establishes as the number of corresponding positions in which binary strings and differ.
Abstract Algebra and Complex Numbers
Single Binary Operator Structures: Ordered by increasing axiomatic complexity:
Magma: Closed under binary operation ().
Semigroup: Associative magma ().
Monoid: Semigroup with identity element ().
Group: Monoid with unique inverses ().
Abelian Group: Commutative group ().

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., , or where is prime).
Gödel's Incompleteness Theorem (1931): A consistent axiomatic system cannot prove all true statements about natural numbers.
Complex Numbers: Defined as , with real part , imaginary part , and .
Complex Conjugate: .
Modulus (Magnitude): .
Argument: .
Polar Form: .

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").

Caesar Cipher: Monoalphabetic shift of positions ( historically):C = (x - n) \bmod 26\n* Affine Cipher: Uses a linear transformation:E(x) = (ax + b) \bmod 26\gcd(a, 26) = 112a12 \times 26 = 312D(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\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 KMC = M \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).

RSA Cryptosystem: Asymmetric algorithm invented by Ron Rivest, Adi Shamir, Leonard Adleman, and independently Clifford Cocks:
Key Generation:
Choose large primes and , calculate , and totient .
Select public exponent such that .
Compute private exponent such that .
Encryption:
Decryption:
Primality Testing and Integer Factorisation
Sieve of Eratosthenes: Deterministic method finding all primes up to by sequentially crossing out multiples of each discovered prime starting at .

Miller-Rabin Primality Test: Probabilistic test writing odd with odd:
A base is a strong witness to compositeness if:andfor all .
If is composite and , at most bases are strong liars.
Pollard's Rho Algorithm: Factorisation method searching for cycle collisions using :
Updates and .
Computes until a non-trivial factor is discovered.

Questions & Discussion
Q1: Find the binary expansion of .
Q2: Evaluate for integers .
Q3: Calculate the modular reductions: , , , , , and .
Q4: Use the division algorithm to divide by yielding quotient and remainder for:
Q5: Calculate the greatest common divisors: , , , and .
Q6: Use the Euclidean algorithm to find the greatest common divisor for pairs and .
Q7: Find integers and such that for pairs and .
Q8: Determine primality for and compute prime factorisations for .
Q9: Verify that is the inverse of .
Q10: Find the inverse of .
Q11: Encrypt "DO NOT PASS" using numeric substitution with and .
Q12: Decrypt the Caesar ciphertext "EOXH MHDQV".
Q13 (Challenge): Show that can be factored if and are both known.
Q14: Encrypt "UPLOAD" using RSA with and .
Q15: Decrypt the RSA message "50 26 46 69 61" with and .
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.