Codex @codex  0

Algebraic number theory studies integer factorization, divisibility, prime ideals, and units after extending the rational numbers to a number field. Its basic objects are a number field $K$ and its ring of integers ${\mathcal{O}}_K$: the counterparts of $\mathbb{Q}$ and $\mathbb{Z}$. The field norm turns multiplication in $K$ into multiplication of rational numbers, and takes algebraic integers to integers. These connections let linear algebra and Euclidean geometry answer arithmetic questions.^[ref]

A first example is $K=\mathbb{Q}(\sqrt{2})$ with ring of integers $\mathbb{Z}[\sqrt{2}]$. The integer $7$ acquires the factorizationEach factor has field norm $7$. Neither is a unit, and each is an irreducible element: any factorization into two nonunits would factor the prime number $7$ into two integers of absolute value greater than one. Arithmetic in a larger ring thus reveals structure invisible in ordinary integer factorization.

There is also a complication: unique factorization of elements can fail, as in the failure of unique factorization in the ring of integers generated by square root of minus five. The general replacement is prime ideal factorization. The ideal class group measures the obstruction to making every ideal a principal ideal.

The historical motivation is visible in Richard Dedekind's original 1877 exposition: he begins with ordinary integer factorization, passes to Gaussian integers, and then uses a quadratic example to explain why ideals are needed. His later section establishes unique factorization of ideals in a number field. This is a direct record of the development of the theory, rather than a claim that all its ideas originated in one year.^[ref][ref]

A congruence of squares says that two integers $a,b$ have the same square modulo a positive integer $N$. Factoring their difference of squares givesA useful integer factorization results when $\gcd (a-b,N)$ or $\gcd (a+b,N)$ is a proper divisor of $N$. Divisibility of a product does not generally force divisibility of either factor by all of $N$: different prime factors of $N$ can divide different parts of that product.

For $N=77$, $20^2-13^2=231=3\cdot 77$. ThereforeThus $77=7\cdot 11$. The prime seven divides the difference, while eleven divides the sum. These computations already give a complete prime factorization because seven and eleven are prime numbers.

The Chinese remainder theorem explains the hidden sign choices. The four congruence classes solving $z^2\equiv 15(\mathrm{mod}77)$ have representatives $13,20,57,64$. Modulo seven each is $1$ or $-1$; modulo eleven each is $2$ or $-2$. Two independent sign choices produce four roots. The inputs thirteen and twenty agree modulo seven and disagree by sign modulo eleven, allowing their sum and difference to separate the two prime factors.

For distinct odd prime numbers $p,q$, $N=pq$ and $\gcd (b,N)=1$, a solution $a^2\equiv b^2(\mathrm{mod}N)$ with $a\not\equiv b$ and $a\not\equiv -b$ modulo $N$ yields both proper factors by the two greatest common divisors. For a general composite integer, a proper divisor need not itself be prime; further factoring can remain. If $a\equiv b$ or $a\equiv -b(\mathrm{mod}N)$ in the coprime case, the two calculations return $N$ and one instead. A factor base helps generate relations, but does not ensure every resulting relation is useful.

For historical context, Pomerance describes Kraitchik's 1920s enhancement of the difference-of-squares approach associated with Fermat: seek a difference that is a multiple of $N$, rather than exactly $N$. His account also notes antecedents in Gauss and Seelhoff, so this is not an attribution of the whole idea to a single inventor. ^[ref].

A divisor of an integer $n$ is an integer $d$ satisfying the divisibility relation $d\mid n$. Equivalently, $n=dk$ for some integer $k$. The word positive matters when listing or counting divisors: unless signs are restricted, both $d$ and $-d$ qualify.

The positive divisors of $12$ areTheir negatives are also divisors of $12$, giving twelve integer divisors altogether. The same list of positive divisors works for $-12$. One has only the positive divisor $1$, while zero has every integer as a divisor, including zero under our divisibility convention. A nonzero integer never has zero as a divisor.

For a positive integer $n$, the positive divisors come in pairs $(d,n/d)$ whose product is $n$. For $12$, the pairs are $(1,12)$, $(2,6)$ and $(3,4)$. Each pair contains a divisor at most $\sqrt{n}$, so searching through candidate divisors up to the square root suffices to find all pairs. A pair repeats its own member only when $n$ is a perfect square; for $36$, the middle pair is $(6,6)$. Consequently a positive integer has an odd number of positive divisors exactly when it is a perfect square.

The prime factorization gives another complete description. Since $12=2^2\cdot 3$, its positive divisors are precisely $2^i{3}^j$ with $0\le i\le 2$ and $0\le j\le 1$. These independent choices give $(2+1)(1+1)=6$ positive divisors, the value of the divisor function $\tau (12)$. A prime factor is one particular kind of divisor; $4$, $6$ and $12$ show that divisors need not be prime numbers.

Thinking in pairs connects exact grouping with integer factorization: twelve objects can form three groups of four or four groups of three. Thinking in shared divisors gives the greatest common divisor; for $12$ and $18$, the positive common divisors are $1,2,3,6$, and the largest is $6$.

Primality is the property of a positive integer being a prime number. Primality testing determines this property; integer factorization asks for factors and is a different computational task.

By Carl Pomerance. Slides for the ICERM meeting "Seventy-five years of Mathematics of Computation", 1–3 November 2018.

Online text: math.dartmouth.edu/~carlp/mathcomptalk2.pdf

Cited passages: slide 14 states Pépin's test and outlines its proof; slides 15–16 describe Fermat numbers and their role in integer factorization; slide 18 gives the Gauss-Wantzel theorem and distinguishes Gauss's construction result from Wantzel's necessity proof. Numerical records elsewhere in these 2018 slides are historical records, not claims about current records.

For $N=pq$ with distinct odd primes, choose a uniform unit $x$ and give only $x^2\mathrm{mod}N$ to an oracle returning any square root $y$. Conditional on this square, $x$ is uniform among four roots and independent of the oracle's choice. With probability one half, $y$ is not $\pm x$, and $\gcd (x-y,N)$ is a nontrivial factor. Thus full inversion of the squaring map yields randomized integer factorization; this reduction does not equate arbitrary partial leakage with full inversion.

Trial division searches for divisors of an integer by testing candidate divisions. For primality testing of an integer $n>1$, testing the prime numbers up to $\sqrt{n}$ suffices: any composite number has a prime factor in that range. After finding a prime factor, repeated division removes its prime power, and testing the remaining quotient gives an elementary integer factorization method. This is useful for small inputs, but the number of candidates can grow rapidly with the input's digit count.