The Higher Arithmetic (Book) by Davenport

book tier1 math thehigherarithmeticbook

goodreads, wiki, amazon

openarchive, gutenberg

authors:

• Harold Davenport
  

pdf links: pdf_1, pdf_2, pdf_3

https://notebooklm.google.com/notebook/d2d93a83-ce0d-4728-a833-a5badb65ee2f

• Timeline of Number Theory
  

Endorsed by Algebraic Numbers essay of Barry Mazur in The Princeton Companion to Mathematics:

• "I recommend that readers who wish to begin this journey carry in their backpacks Gauss's Disquisitiones Arithmeticae as well as Davenport's The Higher Arithmetic (1992), which is one of the gems of exposition of the subject, and which explains the founding ideas clearly and in depth using hardly anything more than high school mathematics"

tag:#TheHigherArithmeticBook 

AI Summary

The Higher Arithmetic is a foundational text on number theory, now in its eighth edition. It introduces concepts and theorems in a way that is accessible without deep prior knowledge, yet touches on profound mathematical significance. Recommended for both independent study and as a reference, it is considered superior to other English texts for undergraduate number theory courses. Authored by H. Davenport, with editing and additional material by James H. Davenport, the 2008 edition includes new material on primality testing.

Core Concepts: Natural Numbers and Proof

• Subject: The higher arithmetic, or theory of numbers, investigates the properties of natural numbers (1, 2, 3, ...). It's a modern science, dating from Fermat's discoveries.
  

• Difficulty: Characterized by the great difficulty in proving seemingly simple general theorems, contributing to its "magical charm". It is the "purest" branch of pure mathematics, deriving inspiration from numerical experiment.
  

• Exactness: Demands exactness of thought and exposition due to its nature. Numerical examples primarily illustrate general theory, not calculation methods.
  

• Laws of Arithmetic: Forms the logical basis.
  

  • Addition: Commutative (\(a+b=b+a\)) and associative (\(a+(b+c)=(a+b)+c\)).
    

  • Multiplication: Commutative (\(ab=ba\)), associative (\(a(bc)=(ab)c\)), and distributive (\(a(b+c)=ab+ac\)). Also includes cancellation laws: if \(a+x=a+y\) then \(x=y\), and if \(ax=ay\) then \(x=y\).
    

  • Subtraction: \(a-b\) exists if \(b<a\), and is unique.
    

  • Division: \(a/b\) exists if \(a=bx\) for some \(x\), and is unique.
    

• Divisibility: Peculiar to number theory.
  

  • \(1\) divides every number, and \(a\) divides \(a\).
    

  • If \(a\) divides \(b\), then \(a \le b\).
    

  • If \(a\) divides \(b\) and \(b\) divides \(c\), then \(a\) divides \(c\).
    

  • If \(a\) divides \(b\) and \(c\), then \(a\) divides \(b+c\) and \(b-c\) (if \(c<b\)).
    

  • Extends to integers: \(b\) is divisible by natural number \(a\) if \(b/a\) is an integer. \(0\) is divisible by every natural number.
    

  • If \(a\) divides \(b\) and \(c\), then \(a\) divides \(ub+vc\) for any integers \(u,v\).
    

• Proof by Induction: Essential for propositions about every natural number (e.g., Lagrange's theorem on sums of four squares).
  

  • Cannot prove general propositions by infinite verification.
    

  • Principle: If a proposition is true for 1, and if its truth for all numbers up to \(n-1\) implies its truth for \(n\), then it is true for every natural number.
    

  • Example: Sum of first \(n\) odd numbers is \(n^2\).
    

  • From a commonsense view, induction is obvious; it explains "and so on" in enumerating natural numbers.
    

Primes and Factorization

• Prime Numbers: Natural numbers greater than 1 with no proper factors (factors other than 1 or itself). First few: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. 1 is not counted as a prime.
  

• Composite Numbers: Neither 1 nor prime; representable as a product of primes. This is provable by induction.
  

• Infinitude of Primes: Euclid's proof (Book IX, Prop. 20). For any finite set of primes \(2, 3, ..., P\), the number \(N = (2 \times 3 \times 5 \times ... \times P) + 1\) is either prime or has a prime factor greater than \(P\).
  

• Fundamental Theorem of Arithmetic: Any natural number can be represented in one and only one way as a product of primes.
  

  • Conventions: A prime is a "product" of one factor; 1 is an "empty" product, value 1.
    

  • History: Not in Euclid, first clearly stated and proved by Gauss in Disquisitiones Arithmeticae (1801).
    

  • Proof (Induction, direct): Uniqueness proved by induction. If \(n = pqr... = p'q'r'...\) are two factorizations, and a prime (say \(p\)) is common, it can be cancelled, reducing to a smaller number. If no common primes, \(p\) divides \(n\), so \(p\) must be in the second factorization (by a preliminary remark), leading to a contradiction.
    

  • Importance of Addition/Subtraction: The proof relies on forming \(n - pp'\), highlighting that uniqueness cannot be based solely on multiplication. Hilbert's example of numbers \(4x+1\) (where \(693 = 9 \times 77 = 21 \times 33\) are factorizations into "pseudo-primes" within the system) demonstrates this.
    

• Consequences of Fundamental Theorem:
  

  • Divisors: If \(n = p^a q^b ...\), its divisors are \(p^\alpha q^\beta ...\) where \(0 \le \alpha \le a\), etc..
    

  • Number of Divisors: \(d(n) = (a+1)(b+1)...\).
    

  • Sum of Divisors: \(\sigma(n) = (1+p+...+p^a)(1+q+...+q^b)...\).
    

  • Perfect Numbers: \(n\) such that \(\sigma(n)=2n\) (sum of divisors, including \(n\), equals \(2n\)). Euclid proved \(2^{k-1}p\) is perfect if \(p\) is prime and \(p+1=2^k\) (i.e., \(p\) is a Mersenne prime). Euler proved all even perfect numbers are of this form. Unknown if odd perfect numbers exist.
    

  • Relatively Prime (Coprime): Numbers with no common divisor other than 1.
    

  • Greatest Common Divisor (H.C.F.): Product of common prime factors raised to the lesser of their exponents in each number. Common divisors of \(m,n\) are precisely all divisors of their H.C.F..
    

  • Least Common Multiple (L.C.M.): Product of all primes occurring in either number, raised to the highest power. Common multiples are precisely all multiples of their L.C.M..
    

  • Divisibility Theorem: If \(a\) divides \(bc\) and is relatively prime to \(b\), then \(a\) divides \(c\).
    

Euclid's Algorithm

• Purpose: Systematic process for finding the H.C.F. of two natural numbers.
  

• Process: Repeated application of division with remainder. If \(a=qb+c\) (\(c<b\)), common divisors of \(a,b\) are the same as common divisors of \(b,c\). The process terminates because the remainders decrease, with the last non-zero remainder being the H.C.F..
  

• Property of H.C.F. (\(h\)): It is representable as a linear combination of \(a\) and \(b\): \(h = ax - by\) for some integers \(x,y\). Any number of the form \(ax-by\) is a multiple of \(h\).
  

• Alternative Proof of Fundamental Theorem: Euclid's algorithm shows that the H.C.F. of \(na\) and \(nb\) is \(n\) times the H.C.F. of \(a\) and \(b\). This leads to Euclid's theorem: if a prime \(p\) divides \(na\), it must divide \(n\) or \(a\) (or both). This theorem is then used to prove the uniqueness of prime factorization.
  

Congruences

• Notation: \(a \equiv b \pmod m\) means \(a-b\) is divisible by \(m\). Introduced by Gauss, it facilitates calculations where numbers differing by a multiple of \(m\) are equivalent.
  

• Properties:
  

  • \(10 \equiv 1 \pmod 9 \implies n \equiv \sum \text{digits} \pmod 9\) (divisibility rule for 9 and 3).
    

  • \(10 \equiv -1 \pmod {11} \implies n \equiv \text{alternating sum of digits} \pmod {11}\) (divisibility rule for 11).
    

• Complete Set of Residues: Any set of \(m\) numbers, no two congruent modulo \(m\). E.g., \(0, 1, ..., m-1\).
  

• Linear Congruences: \(ax \equiv b \pmod m\). Soluble if \(\text{H.C.F.}(a,m)\) divides \(b\). If \(\text{H.C.F.}(a,m)=1\), there is a unique solution modulo \(m\).
  

• Modular Arithmetic: Operations (addition, multiplication, subtraction) are carried out modulo \(m\). Division \(x/y\) is finding \(z\) such that \(yz \equiv x \pmod m\), possible only if \(y\) is relatively prime to \(m\). If \(m\) is prime, division is possible for any non-zero denominator.
  

• Fermat's Little Theorem: If \(p\) is a prime and \(x \not\equiv 0 \pmod p\), then \(x^{p-1} \equiv 1 \pmod p\). Equivalent to saying the order of \(x\) (mod \(p\)) divides \(p-1\). Proved by Leibniz (using multinomial expansion) or Ivory (product of residues).
  

• Order of a Number: For \(x\) relatively prime to \(m\), the least \(l\) such that \(x^l \equiv 1 \pmod m\). Powers of \(x\) are periodic.
  

• Euler's Totient Function (φ(m)): Counts numbers less than \(m\) and relatively prime to \(m\).
  

  • Euler's Theorem (Generalization of Fermat's): If \(x\) is relatively prime to \(m\), then \(x^{\phi(m)} \equiv 1 \pmod m\).
    

  • Formula: \(\phi(p^a) = p^a - p^{a-1} = p^{a-1}(p-1)\) for prime \(p\).
    

  • Multiplicative Property: If \(a,b\) are relatively prime, \(\phi(ab) = \phi(a)\phi(b)\).
    

  • Chinese Remainder Theorem: If \(a,b\) are relatively prime, simultaneous congruences \(x \equiv \alpha \pmod a\), \(x \equiv \beta \pmod b\) have a unique solution modulo \(ab\).
    

  • Sum of φ(d) over divisors: \(\sum_{d|m} \phi(d) = m\).
    

  • Conjecture: For any \(m\), there is an \(m' \ne m\) such that \(\phi(m') = \phi(m)\) (unproven).
    

• Wilson's Theorem: For any prime \(p\), \((p-1)! \equiv -1 \pmod p\). Proved by pairing numbers with their modular reciprocals; only 1 and \(p-1\) are their own reciprocals.
  

Quadratic Residues

• Binomial Congruences: \(ax^k \equiv b \pmod p\) can be reduced to \(x^k \equiv c \pmod p\).
  

• kth Power Residue: \(c\) is a \(k\)th power residue (mod \(p\)) if \(x^k \equiv c \pmod p\) is soluble (excluding \(c \equiv 0 \pmod p\)).
  

• Primitive Root: For any prime \(p\), there exists a number whose order modulo \(p\) is \(p-1\). Such a number is a primitive root.
  

  • Existence Proof (Legendre): Uses properties of orders of products of numbers. If \(l\) is order of \(a\), \(k\) is order of \(b\), and \(\text{H.C.F.}(l,k)=1\), then \(ab\) has order \(lk\). Number of primitive roots is \(\phi(p-1)\).
    

• Indices (Discrete Logarithms): For a primitive root \(g \pmod p\), \(g, g^2, ..., g^{p-1}(\equiv 1)\) are incongruent and congruent to \(1, ..., p-1\) in some order. The index of \(x\) is \(\xi\) if \(g^\xi \equiv x \pmod p\). Used to reduce modular multiplication to addition.
  

• Quadratic Residues (k=2): If \(p>2\), \(\text{H.C.F.}(2, p-1)=2\). Quadratic residues have even indices, non-residues have odd indices. There are \((p-1)/2\) of each. If \(a\) is a quadratic residue, \(x^2 \equiv a \pmod p\) has two solutions \(x \equiv \pm x_1\).
  

  • Multiplicative Property: Product of two residues or two non-residues is a residue. Product of residue and non-residue is a non-residue.
    

• Legendre's Symbol: \((a|p) = 1\) if \(a\) is quadratic residue, \(-1\) if non-residue. Multiplicative: \((ab|p) = (a|p)(b|p)\).
  

• Euler's Criterion: \((a|p) \equiv a^{(p-1)/2} \pmod p\).
  

  • Character of -1: \((-1|p)\) is \(1\) if \(p \equiv 1 \pmod 4\), and \(-1\) if \(p \equiv 3 \pmod 4\).
    

• Gauss's Lemma: For \(a \not\equiv 0 \pmod p\), form \(a, 2a, ..., ((p-1)/2)a\). Reduce each to lie between \(-p/2\) and \(p/2\). If \(v\) is the number of negative results, then \((a|p) = (-1)^v\).
  

  • Character of 2: \((2|p)\) is \(1\) for \(p \equiv \pm 1 \pmod 8\), and \(-1\) for \(p \equiv \pm 3 \pmod 8\).
    

  • Character of 3: \((3|p)\) is \(1\) for \(p \equiv \pm 1 \pmod {12}\), and \(-1\) for \(p \equiv \pm 5 \pmod {12}\).
    

• Law of Quadratic Reciprocity: For two distinct primes \(p,q\): \((p|q)(q|p) = (-1)^{((p-1)/2)((q-1)/2)}\). The characters are the same unless both \(p\) and \(q\) are of the form \(4k+3\), in which case they are opposite. One of the most famous theorems, discovered by Gauss.
  

• Distribution: Quadratic residues and non-residues are equally distributed among \(1, ..., p-1\). The number of pairs of consecutive numbers with prescribed characters (RR, RN, NR, NN) are all about \(p/4\) for large \(p\).
  

Continued Fractions

• Definition: Representation of a rational number as \(q_0 + \frac{1}{q_1 + \frac{1}{q_2 + \dots}}\). Terms \(q_i\) are partial quotients.
  

• Uniqueness: Each rational number has a unique continued fraction representation.
  

• Notation: \([q_0, q_1, ..., q_n]\) for numerator. Denominator is \([q_1, ..., q_n]\).
  

• Convergents: Approximations obtained by stopping at an earlier term.
  

  • Numerators (\(A_m\)) and denominators (\(B_m\)) follow recurrence relations: \(A_m = q_m A_{m-1} + A_{m-2}\) and \(B_m = q_m B_{m-1} + B_{m-2}\).
    

  • Property: \(A_m B_{m-1} - B_m A_{m-1} = (-1)^{m-1}\).
    

  • Relatively Prime: \(A_m\) and \(B_m\) are always relatively prime.
    

  • Approximation: Convergents are alternately less than and greater than the final value, and are successively nearer to it. Each convergent \(A_m/B_m\) satisfies \(|\alpha - A_m/B_m| < 1/(B_m B_{m+1})\). Better approximations often satisfy \(|\alpha - x/y| < 1/(2y^2)\) or \(1/(\sqrt{5}y^2)\).
    

• Solving \(ax-by=1\): If \(\text{H.C.F.}(a,b)=1\), the continued fraction for \(a/b\) provides \(x=B_{n-1}\) and \(y=A_{n-1}\) for \(aB_{n-1} - bA_{n-1} = (-1)^{n-1}\).
  

• Infinite Continued Fractions: Represent irrational numbers. The process never ends for irrationals. Convergents approach the irrational number as a limit. Any infinite sequence of natural numbers as terms defines an irrational number.
  

• Quadratic Irrationals: Solutions of quadratic equations with integer coefficients (e.g., \(\sqrt{N}\)). Their continued fractions are periodic after a certain stage (Lagrange's theorem, 1770). Purely periodic continued fractions characterize "reduced" quadratic irrationals (those \(\alpha > 1\) with conjugate \(\alpha'\) between -1 and 0).
  

• Pell's Equation (\(x^2 - Ny^2 = 1\)): Always has solutions in natural numbers \(x,y\), and infinitely many. The continued fraction for \(\sqrt{N}\) provides solutions. The smallest solution is obtained from the last convergent before the period repeats.
  

Sums of Squares

• Two Squares: A natural number \(N\) is representable as sum of two squares (\(x^2+y^2\)) if and only if any prime factor of \(N\) of the form \(4k+3\) divides \(N\) to an even power. Identity: \((a^2+b^2)(c^2+d^2) = (ac+bd)^2 + (ad-bc)^2\) (Fibonacci).
  

  • Primes \(4k+1\): Any prime \(p\) of the form \(4k+1\) is representable as \(x^2+y^2\) (Euler's proof). This representation is unique (apart from sign/order).
    

  • Constructions for \(x,y\): Legendre (via continued fraction of \(\sqrt{p}\)), Gauss (involving factorials), Serret (via continued fraction of \(p/h\)), Jacobsthal (via sums of Legendre symbols).
    

• Four Squares: Every natural number is representable as the sum of four squares of integers (Lagrange, 1770). Identity (Euler): product of two sums of four squares is a sum of four squares.
  

• Three Squares: Much more difficult. A number is representable as the sum of three squares if and only if it is NOT of the form \(4^k(8m+7)\). First complete proof by Gauss.
  

Quadratic Forms

• Definition: Expression \(ax^2+bxy+cy^2\) with integer coefficients \(a,b,c\).
  

• Problem: What numbers are represented by a given quadratic form?. Generally, no simple answer for individual forms.
  

• Equivalence: Two forms are equivalent if one can be transformed into the other by a unimodular substitution (integral coefficients, determinant 1).
  

  • Properties: Reflexive, symmetric, transitive.
    

  • Problem of representation is the same for equivalent forms.
    

• Discriminant (\(d=b^2-4ac\)): Invariant under unimodular substitutions.
  

  • Negative discriminant: definite forms (always positive or negative).
    

  • Positive discriminant: indefinite forms.
    

• Representation Principle: Numbers properly representable by \((a,b,c)\) are precisely those numbers that figure as first coefficients of forms equivalent to \((a,b,c)\).
  

  • If \(n\) is properly representable, then \(h^2 \equiv d \pmod{4|n|}\) must be soluble.
    

• Reduction of Positive Definite Forms: Lagrange's theory finds a "simple" equivalent form. Any positive definite form is equivalent to a reduced form where \(c \ge a\) and \(-a < b \le a\), or \(c=a\) and \(0 \le b \le a\).
  

  • Uniqueness: There is one and only one reduced form equivalent to a given form.
    

  • Finiteness: Only a finite number of reduced forms for a given negative discriminant \(d\). This number is the class-number \(C(d)\).
    

• Class-number Formula (Dirichlet): For fundamental discriminant \(-p\) (where \(p\) is prime), \(C(-p) = (B-A)/p\), where \(A\) is sum of quadratic residues \(1, ..., p-1\) and \(B\) is sum of non-residues.
  

  • Gauss conjectured \(C(d) \to \infty\) as \(d \to -\infty\), proved by Heilbronn (1934).
    

  • Known \(C(d)=1\) for nine values of \(-d\) (3, 4, 7, 8, 11, 19, 43, 67, 163); proved by Stark (1966) that these are all.
    

Diophantine Equations

• Definition: Equations to be solved with integral values for unknowns. Often unrelated results; extensive theories (e.g., quadratic forms) become independent.
  

• Pythagorean Triples (\(x^2+y^2=z^2\)): General solution known since Euclid. Primitive solutions (no common factors): \(x=p^2-q^2, y=2pq, z=p^2+q^2\) where \(p,q\) are coprime and one is even, one odd.
  

• Elliptic Equations/Curves (\(y^2=x^3-Ax-B\)):
  

  • Transformations: Can simplify forms (e.g., from Weierstrass form \(y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6\) to \(y^2=x^3-Ax-B\)). Rational solutions map to integral solutions on projective curves (\(Y^2Z=X^3-AXZ^2-BZ^3\)).
    

  • Discriminant (\(\Delta=16(4A^3-27B^2)\)): Non-zero for non-singular curves.
    

  • Geometric Interpretation: Points on the curve form a group under a geometric addition law. A line through two points \(P,Q\) on the curve intersects it at a third point \(R\). If \(P,Q\) have rational coordinates, \(R\) also has rational coordinates. This allows generating new rational solutions.
    

  • Point at Infinity (O): Solution not corresponding to rational points in affine plane.
    

  • Group Law: Addition is commutative and associative.
    

  • Mordell-Weil Theorem: There are always finitely many independent rational points (generators of the group of rational points). This number is the rank (\(r\)). There is no known algorithm to find the exact rank.
    

  • Torsion Points: Points for which some multiple is O.
    

    • Mazur's Theorem: For elliptic curves over rationals, the number of torsion points is one of {1, 2, ..., 10, 12, 16}.
      

    • Lutz-Nagell Theorem: Integral torsion points (x,y) must have integral coordinates, and \(y^2\) must divide \(\Delta\) (unless \(y=0\)).
      

• Elliptic Equations Modulo Primes: Study of solutions modulo \(p\) reveals information about rational solutions.
  

  • Hasse's Theorem: Number of points \(n_E\) (including O) modulo \(p\) is \(p+1+t\), where \(|t| < 2\sqrt{p}\).
    

  • Reduction Types: Good/stable reduction (\(\Delta \not\equiv 0 \pmod p\)), semi-stable reduction (node, \(\Delta \equiv 0, A \not\equiv 0 \pmod p\)), unstable reduction (cusp, \(\Delta \equiv A \equiv 0 \pmod p\)).
    

• Fermat's Last Theorem (\(x^n+y^n=z^n\), \(n>2\)): No solution in natural numbers. Remained unproven until Wiles (1993). Fermat likely mistaken in claiming a proof.
  

  • Case \(n=4\) (\(x^4+y^4=z^2\)): Fermat proved insoluble using infinite descent.
    

  • Faltings' Theorem (1983): For \(n>3\), \(x^n+y^n=1\) has only finitely many rational solutions.
    

  • Taniyama-Shimura-Weil Conjecture (now a theorem): All rational elliptic curves are modular. This connection (Frey, Ribet) was key to Wiles' proof.
    

• Other Diophantine Equations:
  

  • \(x^3+y^3=z^3+w^3\): Solutions (Euler and Binet formulae) yield examples like \(1^3+12^3=9^3+10^3=1729\).
    

  • Sums of Cubes: Not every number is a sum of three integral cubes (e.g., \(4,5 \pmod 9\) are impossible). Unsolved: Is every number a sum of four integral cubes?. Every number is a sum of five integral cubes.
    

• Thue-Siegel-Roth Theorem: Concerns Diophantine approximation to algebraic numbers. If \(\theta_1\) is an algebraic number of degree \(n \ge 3\), then for any \(\nu > 2\), the inequality \(|x/y - \theta_1| > 1/y^\nu\) holds for all but a finite number of rational approximations \(x/y\). This implies that many Diophantine equations have only a finite number of solutions. Does not give explicit bounds for solutions.
  

• Baker's Method: Provides explicit limits for all solutions of Diophantine equations in certain classes, using properties of logarithms of algebraic numbers.
  

Computers and Number Theory

• Impact: Rapid development of computers enables complex number-theoretic calculations, previously impossible. Requires handling large numbers beyond native computer word sizes.
  

  • Large Number Arithmetic: Use 'multi-digit' numbers with large base (e.g., \(10^4\)) and techniques similar to long multiplication/division. Karatsuba's algorithm for faster multiplication of large integers (proportional to \(d^{\log_2 3}\) vs \(d^2\) for \(d\) digits).
    

  • Applications: Random number generators, hash tables, public-key cryptography.
    

• Primality Testing:
  

  • Need for Large Primes: Cryptography requires large, 'random' primes.
    

  • Fermat Test: \(x^{p-1} \equiv 1 \pmod p\) for prime \(p\). Can show a number is composite (if \(x^{n-1} \not\equiv 1 \pmod n\)). Computation uses repeated squaring for efficiency (\(O(\log n)\) multiplications).
    

  • Carmichael Numbers (Pseudo-primes): Composite numbers \(n\) where \(x^{n-1} \equiv 1 \pmod n\) for all \(x\) coprime to \(n\) (e.g., 561). These evade the simple Fermat test.
    

  • Rabin's Algorithm (Probabilistic):
    

    • For a composite \(n\), returns "probably prime" with probability at most \(1/4\). For a prime \(n\), always says "probably prime".
      

    • Works by checking Fermat's theorem and Lagrange's theorem on \(x^2-1\). If \(n\) is composite, it will likely find a "witness" \(x\) that proves it.
      

    • Running time: \(O(\log^3 n)\) with basic multiplication.
      

  • Primality Certificates: Proving \(n\) is prime by exhibiting a primitive root \(x \pmod n\) (i.e., \(x^{n-1} \equiv 1 \pmod n\) and \(x^{(n-1)/d} \not\equiv 1 \pmod n\) for all prime divisors \(d\) of \(n-1\)). Requires factoring \(n-1\).
    

  • Proth's Theorem: For \(N=h2^n+1\) (\(h\) odd, \(h<2^n\)), if there's \(a\) such that \(a^{(N-1)/2} \equiv -1 \pmod N\), then \(N\) is prime.
    

  • AKS Algorithm (Deterministic): Agrawal, Kayal, Saxena (1999) proved PRIMES is in P, meaning primality can be determined in polynomial time. Based on polynomial version of Fermat's Little Theorem: \((x+1)^n \equiv x^n+1 \pmod n\) if and only if \(n\) is prime. Running time is roughly \(O(\log^6 n)\). Certificates are short but costly to verify.
    

• Random Number Generators ('Pseudo-random'):
  

  • Goal: Long period, 'look random'. Not truly unpredictable.
    

  • Mid-square method: Poor, quickly gets stuck or repeats short loops.
    

  • Birthday Paradox: Demonstrates that repetitions occur sooner than intuition suggests (\(\approx \sqrt{\pi N/2}\) selections for \(N\) objects).
    

  • Linear Congruential Generators (\(x_{i+1} = (ax_i+c) \pmod n\)):
    

    • Maximal period (all \(n\) values) conditions: (i) \(p|b\) for all primes \(p|n\), (ii) if \(2|n\), then \(4|b\), (iii) \(\text{H.C.F.}(n,c)=1\).
      

• Factoring Large Numbers:
  

  • Initial Steps: Trial division for small factors, then primality test (e.g., Rabin's). If composite, then advanced methods.
    

  • Fermat's Difference of Squares: \(N = x^2-y^2 = (x-y)(x+y)\). Efficient if factors are close. Extended by finding \(x^2 \equiv y^2 \pmod N\).
    

  • General Method: Find many \(x_i\) such that \(x_i^2 \equiv E_i \pmod N\) where \(E_i\) are small and can be factored into a "factor base" of small primes. Use these congruences to find a combination where the product of \(E_i\) is a perfect square, leading to \(X^2 \equiv Y^2 \pmod N\) and potentially a factor \(\text{H.C.F.}(X-Y, N)\).
    

  • Continued Fraction Algorithm: Generates \(A_m^2 \equiv E \pmod N\) from convergents of \(\sqrt{N}\). Running time \(O(L(N)^2)\).
    

  • Quadratic Sieve (Pomerance): Generates \(X^2 \equiv Y \pmod N\) congruences where \(Y\) is small and smooth. More efficient than Continued Fraction method. Running time \(O(L(N))\).
    

  • Number Field Sieve: Most advanced factoring algorithm. Running time \(O(M(N)^c)\) (where \(M(N)\) grows even slower than \(L(N)\)). Used for very large numbers.
    

• Cryptography:
  

  • Public-key Cryptography: Secure communication without pre-arranged private keys.
    

  • Diffie-Hellman Key Exchange: Two parties establish a shared secret over an insecure channel.
    

    • Relies on exponentiation and discrete logarithms. If Alice sends \(g^a \pmod P\) and Bob sends \(g^b \pmod P\), they can both compute \((g^b)^a = (g^a)^b = g^{ab} \pmod P\) as a shared secret.
      

    • Security relies on the difficulty of computing discrete logarithms for large \(P\).
      

    • Elliptic Curve Diffie-Hellman: Uses point multiplication on elliptic curves. Believed harder to break, allowing smaller parameters.
      

  • RSA Method (Rivest, Shamir, Adleman): One-way secure communication.
    

    • Alice chooses two large primes \(P,Q\) and publishes \(N=PQ\) and an exponent \(x\) (coprime to \(\phi(N)=(P-1)(Q-1)\)).
      

    • Anyone sends message \(a\) as \(a^x \pmod N\). Alice decodes by computing \(x'\) such that \(xx' \equiv 1 \pmod{\phi(N)}\), then \((a^x)^{x'} \equiv a \pmod N\).
      

    • Security relies on the difficulty of factoring \(N\). Knowing \(x'\) allows factoring \(N\).