7.1 Number theory background and classical factoring

Number theory forms the backbone of many cryptographic systems. It deals with properties of integers, modular arithmetic, and prime numbers. These concepts are crucial for understanding how modern encryption works and why certain mathematical problems are hard to solve.

Number theory's applications in cryptography rely on the difficulty of certain mathematical operations. For instance, while multiplying large prime numbers is easy, factoring their product is computationally challenging. This asymmetry forms the basis of widely used encryption methods like RSA.

Number Theory Fundamentals

Fundamentals of number theory

Top images from around the web for Fundamentals of number theory

• 

  number theory - Purpose of Fermat's Little Theorem - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  number theory - Purpose of Fermat's Little Theorem - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  number theory - Purpose of Fermat's Little Theorem - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  number theory - Purpose of Fermat's Little Theorem - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 2

Top images from around the web for Fundamentals of number theory

• 

  number theory - Purpose of Fermat's Little Theorem - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  number theory - Purpose of Fermat's Little Theorem - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  number theory - Purpose of Fermat's Little Theorem - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  number theory - Purpose of Fermat's Little Theorem - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 2

• Modular arithmetic performs arithmetic operations on integers within a fixed range or modulus ($n$)
  • Addition: $(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$ (5 + 7 ≡ 2 (mod 10))
  • Multiplication: $(a \times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n$ (3 × 4 ≡ 2 (mod 10))
• Congruence relation $a \equiv b \pmod{n}$ holds if and only if $n$ divides $(a - b)$
  • Congruence classes are sets of integers that have the same remainder when divided by $n$ (2, 7, 12 are in the same congruence class modulo 5)
• Euler's theorem states that for coprime integers $a$ and $n$, $a^{\phi(n)} \equiv 1 \pmod{n}$
  • $\phi(n)$ is Euler's totient function, counting the number of positive integers up to $n$ that are coprime to $n$ ($\phi(12) = 4$ since 1, 5, 7, 11 are coprime to 12)
• Fermat's little theorem is a special case of Euler's theorem
  • If $p$ is prime and $a$ is not divisible by $p$, then $a^{p-1} \equiv 1 \pmod{p}$ ($3^6 \equiv 1 \pmod{7}$)

Complexity of factoring algorithms

• Factoring decomposes a composite number into its prime factors (60 = 2 × 2 × 3 × 5)
• Classical factoring algorithms have limitations due to the believed hardness of factoring large numbers
  • Trial division divides the number by primes up to its square root with time complexity $O(\sqrt{n})$
  • Pollard's rho algorithm uses a sequence of numbers to find a factor with average time complexity $O(n^{1/4})$
  • Quadratic sieve finds smooth numbers to create a congruence of squares with time complexity $O(e^{(\log n)^{1/2}(\log \log n)^{1/2}})$
• Best known classical algorithms have subexponential time complexity, which is exponential with respect to the number of digits in the input (factoring a 2048-bit number is much harder than factoring a 1024-bit number)

Factoring vs RSA cryptosystem

• RSA cryptosystem is a public-key cryptosystem based on the difficulty of factoring large numbers
  • Key generation:
    1. Choose two large prime numbers $p$ and $q$
    2. Compute $n = pq$ and $\phi(n) = (p-1)(q-1)$
    3. Select public exponent $e$ coprime to $\phi(n)$
    4. Compute private exponent $d$ such that $ed \equiv 1 \pmod{\phi(n)}$
  • Encryption: $c \equiv m^e \pmod{n}$
  • Decryption: $m \equiv c^d \pmod{n}$
• The security of RSA relies on the difficulty of factoring large numbers
  • If an attacker can factor $n$, they can compute $\phi(n)$ and derive the private key $d$

Applications of modular arithmetic

• Modular exponentiation efficiently computes $a^b \bmod n$ using repeated squaring
  • Example: Compute $3^{100} \bmod 17$ by repeatedly squaring 3 and reducing modulo 17
• Solving linear congruences finds solutions to equations of the form $ax \equiv b \pmod{n}$
  • Use the extended Euclidean algorithm to find the modular multiplicative inverse of $a$ modulo $n$
  • Example: Solve $3x \equiv 4 \pmod{7}$ by finding the inverse of 3 modulo 7 and multiplying both sides
• Chinese remainder theorem solves a system of simultaneous linear congruences
  • Example: Find $x$ such that $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, and $x \equiv 2 \pmod{7}$ by combining the congruences using their pairwise coprime moduli