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$.

Factorization expresses an object as a product of simpler factors. Integer factorization decomposes an integer; polynomial factorization decomposes a polynomial. The permitted factors depend on the ambient algebraic structure.

A general-purpose classical integer factorization algorithm combining polynomial relations, arithmetic in number fields and sparse linear algebra to construct congruent squares modulo the input. Its familiar general-input complexity estimate is heuristic and subexponential in the input's value, roughly $\exp (O(n^{1/3}(\log n{)}^{2/3}))$ for $n$ input bits. This is not polynomial in the bit length. Special input structure, small factors and preprocessing can make other algorithms preferable.

The essential exponent condition isOtherwise the modular multiplicative inverse defining $d$ does not exist. For large prime numbers greater than three, this is equivalent toIf, for example, $p\equiv 1(\mathrm{mod}3)$, the multiplicative group modulo $p$ has order divisible by three, and cubing is not a bijection; distinct plaintexts can have the same ciphertext. Unique decryption of all messages would then be impossible.

The prime numbers must also be distinct for the displayed totient formula, and selected sufficiently large and independently that integer factorization of $n=pq$ is infeasible. A small factor, equal factors, or an exceptionally small difference between $p$ and $q$ gives an avoidable factorisation weakness. These size and generation conditions address security; the congruence condition addresses invertibility of cubing.

The fact that a nontrivial factor usually appears before a full return does not say that either event appears soon. Each iteration of the RSA cycling attack is inexpensive, but the number of iterations can be enormous. The multiplicative orders governing returns modulo $p$ and $q$ need not be small, and writing down a large return exponent does not provide a fast way to search the preceding iterations.

If this procedure factored arbitrary well-generated RSA cryptosystem moduli in feasible time with substantial success, it would solve the associated integer factorization problem efficiently. If it instead rapidly returned the predecessor of a ciphertext without factoring, it would solve the RSA inversion problem. Both are intended to be infeasible for appropriate parameters. Efficient integer factorization certainly breaks RSA cryptosystem security; the reverse implication for general RSA inversion problem algorithms is not known.

Thus the stated observation alone provides no serious general attack on well-generated parameters. It also does not prove a lower bound: special moduli or messages with short cycles can be weak, and the hardness claims are computational assumptions.

For a positive integer $N$, a Dirichlet character $\psi$ modulo $N$ is a group homomorphism $(\mathbb{Z}/N\mathbb{Z}{)}^{\times }\to {\mathbb{C}}^{\times }$, extended periodically to the integers and set equal to zero on integers not coprime to $N$. Its nonzero values are roots of unity. For $\mathrm{Re}s>1$, its Dirichlet L-function is the absolutely convergent Dirichlet seriesComplete multiplicativity of $\psi$ proves the Euler product by expanding each factor as a geometric series and applying unique integer factorization; absolute convergence justifies these rearrangements.

Suppose $\psi$ is a nonprincipal Dirichlet character. Choose a unit $u$ with $\psi (u)\ne 1$. Multiplication by $u$ permutes a complete residue system, so ${\sum }_{a=1}^N\psi (a)=\psi (u){\sum }_{a=1}^N\psi (a)$, and the sum is zero. Consequently $A(x)={\sum }_{n\le x}\psi (n)$ is bounded: complete periods contribute zero and the remaining incomplete period has at most $N$ terms. The Abel summation formula gives, initially for $\mathrm{Re}s>1$,For $\mathrm{Re}s>0$ the integral converges, locally uniformly together with its derivatives in $s$, because on a compact set with $\mathrm{Re}s\ge \delta >0$ the differentiated integrands are bounded by constants times $x^{-1-\delta }(1+\log x{)}^k$. Thus holomorphy of a Dirichlet series from bounded partial sums proves

For a nonreal $\psi$, the character ${\psi }^2$ is also nonprincipal. The supplied logarithmic Euler product yields, for real $\sigma >1$,At a prime dividing $N$ the numerator is $3$. At every other prime put $\psi (p{)}^k=e^{i\theta }$; then the numerator is $3+4\cos \theta +\cos 2\theta =2(1+\cos \theta {)}^2\ge 0$. This Euler product positivity for L-function nonvanishing proves that the product inside the logarithm is at least one. If $L_N(\psi ,1)=0$, its holomorphy would give $L_N(\psi ,\sigma )=O(\sigma -1)$. Meanwhile $L_N({\psi }^2,\sigma )$ is bounded near one and the Riemann zeta function has a simple pole there. The product would therefore be $O(\sigma -1)$ and tend to zero, a contradiction.

For a real nonprincipal $\psi$, suppose instead that $L_N(\psi ,1)=0$. The product $H(s)=\zeta (s)L_N(\psi ,s)$ would then be holomorphic on the whole half-plane $\mathrm{Re}s>0$, because the zero cancels the only zeta pole there. In $\mathrm{Re}s>1$ it has coefficientsThese are nonnegative zeta-times-real-L coefficients. They are multiplicative, and their prime-power values are $k+1$ if $\psi (p)=1$, one or zero according as $k$ is even or odd if $\psi (p)=-1$, and one if $\psi (p)=0$. In particular $b_n\ge 0$ and $b_{m^2}\ge 1$ for every $m$.

The Taylor series of the assumed holomorphic $H$ about $2$ converges in the disk $|s-2|<2$. Termwise differentiation of its absolutely convergent Dirichlet series at $2$ gives $(-1{)}^k{H}^{(k)}(2)={\sum }_n{b}_n(\log n{)}^k/n^2$. Evaluate the Taylor series at $s=1/2$ and apply the Tonelli theorem to the resulting nonnegative terms:This contradicts holomorphy at $1/2$. The argument is the positive-coefficient mechanism of the Landau theorem for a Dirichlet series with nonnegative coefficients, with the needed step proved explicitly. Combining the real and nonreal cases gives the nonvanishing of a nonprincipal Dirichlet L-function at one:

Now let $a$ be coprime to $N$. The Dirichlet theorem on primes in arithmetic progressions asserts that infinitely many prime numbers satisfy $p\equiv a(\mathrm{mod}N)$. To prove it, separate the first-power terms in the given logarithmic Euler product:For $\sigma \ge 1$, the remainder is bounded uniformly byFor a nonprincipal character, holomorphy and nonvanishing near one give a local holomorphic logarithm. Along a short real interval to the right of one, this logarithm and the supplied continuous logarithm differ by a fixed integer multiple of $2\pi i$. Hence the prime-character sum near one is bounded:For the principal Dirichlet character ${\psi }_0$,The latter follows from the simple zeta pole and the bounded remainder. Finally Orthogonality of Dirichlet characters givesHere $\phi$ is the Euler totient function. The right-hand side tends to infinity as $\sigma \downarrow 1$, whereas a finite set of primes would give a bounded left-hand side. Therefore

Put $\alpha =\sqrt{N}$ and use conventional convergent indexing starting at zero; the same argument covers all the printed positive indices. The continued fraction complete quotients satisfy ${\alpha }_{j+1}=1/({\alpha }_j-a_j)$, $a_j=\lfloor {\alpha }_j\rfloor$. After the first step they exceed one, while their algebraic conjugates lie in $(-1,0)$. Indeed ${\alpha }_1^{\prime }=1/(-\sqrt{N}-a_0)\in (-1,0)$, and if ${\alpha }_j^{\prime }\in (-1,0)$ with $a_j\ge 1$, then $1/({\alpha }_j^{\prime }-a_j)\in (-1,0)$.

Write ${\alpha }_{k+1}=(\sqrt{N}+m)/d$, where $m,d$ are integers and $d>0$. This form follows by rationalization at each step: $m_{j+1}=a_j{d}_j-m_j$ and $d_{j+1}=(N-m_{j+1}^2)/d_j$, starting from $m_0=0,d_0=1$. The two conjugate inequalities giveso $d<2\sqrt{N}$. The standard convergent recursions also giveSubstitute the displayed form of ${\alpha }_{k+1}$ and compare rational and irrational coefficients. This yields $p_k=m{q}_k+d{q}_{k-1}$ and $N{q}_k=m{p}_k+d{p}_{k-1}$. Therefore the small norm residues from square-root continued fractions obeyThe initial convergent satisfies the same relation with the usual $p_{-1}=1,q_{-1}=0$. This avoids the insufficient estimate obtained by merely replacing the convergent error with $1/q_k^2$.

For integer factorization, choose a factor base of small primes for which $N$ is a quadratic residue, together with $-1$ to record negative residues; a prime dividing $N$ already supplies a factor. Test the small nonzero integers $r_k=p_k^2-N{q}_k^2$ for being B-numbers. Complete factorization over the base records each prime exponent modulo two. Once enough relations are collected, linear algebra over ${\mathbb{F}}_2$ can choose a nonempty subcollection whose exponent sum is even, including the sign. ThenIf $X\not\equiv \pm Y(\mathrm{mod}N)$, one of $\gcd (X-Y,N)$ or $\gcd (X+Y,N)$ can yield a nontrivial factor. Relations with a noninvertible $p_k$ may already give a factor through its gcd. The small-residue bound makes smoothness more likely; it does not guarantee that any one dependency gives a nontrivial factor.

Use the square-root encryption convention called the Rabin-Williams scheme in the Cambridge course notes. Choose distinct large primes $p,q\equiv 3(\mathrm{mod}4)$, keep them secret, and publish $N=pq$. A message block $m\in \{0,\dots ,N-1\}$ is encrypted asUsually require $\gcd (m,N)=1$; otherwise the message itself reveals a factor. For a quadratic residue $c$ modulo $p$, Euler criterion gives $c^{(p-1)/2}=1$, so $c^{(p+1)/4}$ is a square root. Compute both signs modulo each prime, then combine the four sign choices by the Chinese remainder theorem. For a unit ciphertext there are four roots modulo $N$. Message redundancy identifies the intended root; squaring alone does not identify it uniquely.

To reduce integer factorization to recovery of square roots, choose $x$ uniformly from $(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$, compute $c=x^2$, and ask the alleged decoder for any root $y$ of $c$. Conditional on $c$, the secret $x$ is uniform among its four roots, even if the decoder deterministically chooses $y$. With probability $1/2$, $y\not\equiv \pm x(\mathrm{mod}N)$. Then the signs agree modulo one prime and disagree modulo the other. Sincethe greatest common divisor factors $N$. Independent trials require an expected two successful oracle calls. If a trial's chosen $x$ is not a unit, $\gcd (x,N)$ already factors $N$. This establishes the computational equivalence between factorization and inversion of the squaring map; it does not claim that learning any partial information about a formatted message is equivalent to full inversion.

For coin flipping by telephone, Alice publishes $N$ with its factorization secret. Bob chooses uniformly a unit $x$ with $0<x<N/2$ and sends $c=x^2\mathrm{mod}N$. Alice computes the two roots $r_1,r_2$ in this half interval, selects a binary digit in which they differ, and announces a guess for that digit of Bob's $x$. Bob reveals $x$; Alice verifies its range and square, and their common bit records whether her guess was correct. Alice then reveals $p,q$, so Bob verifies the primes, product, and differing digit.

Conditional on $c$, Bob's original root is equally likely to be $r_1$ or $r_2$, so Alice's guess succeeds with probability $1/2$. Bob cannot change his answer to the other half-interval root without finding a nontrivial second square root, which would factor $N$ by the argument above. Thus, assuming factorization is hard and the prescribed sampling and completed exchange are followed,The revealed factors make the completed transcript checkable. The protocol does not prevent a party from aborting communication.

The input size of an integer factorization problem is its number of bits $n\simeq {\log }_{2}N$. Trial division up to $\sqrt{N}$ is exponential in $n$; advanced classical algorithms do substantially better, but no general polynomial-time classical factoring algorithm is known. The heuristic general-purpose general number field sieve has subexponential rather than polynomial scaling, roughly $\exp (O(n^{1/3}(\log n{)}^{2/3}))$. This describes known algorithmic performance, not a proof that efficient classical factoring is impossible or that every large integer is difficult.

Choose $a$ with $1<a<N$. A nontrivial greatest common divisor $\gcd (a,N)$ already supplies a factor; otherwise find the multiplicative order $r$ of $a$ modulo $N$. If $r$ is even and $a^{r/2}\not\equiv -1(\mathrm{mod}N)$, thenMinimality of the order also excludes $a^{r/2}\equiv 1(\mathrm{mod}N)$, so factor extraction from an even modular order gives nontrivial factors through $\gcd (a^{r/2}\pm 1,N)$. Unhelpful choices of $a$ or odd orders require another trial. For $N=15$, $a=2$ has successive residues $1,2,4,8$ and order four, givingComputing the powers is easy by repeated squaring; discovering a large order is the step accelerated by Shor's algorithm.^[ref]

Put $Q=2^L$ and suppose $Q\ge r$. For each residue class $s=0,\dots ,r-1$, letThese are normalized uniform superpositions of the arguments with the same modular-exponentiation value. Their amplitudes repeat at separation $r$ within the finite register window. Exact cyclic periodicity requires $r\mid Q$. The correctly normalized entangled register state isThe equal prefactor $1/\sqrt{r}$ in the displayed algorithm is exact when $r\mid Q$, for then every $n_s=Q/r$. It is not generally exact for an arbitrary unknown order. A physical implementation uses quantum modular exponentiation as a reversible map; its specified action on second-register input zero is extended to a unitary operator on the whole register space.

For the illustrative $N=15$, $a=2$ and $Q=16$, the four first-register states areApplying the positive-sign quantum Fourier transform to the general state givesThe bracket is a finite geometric Fourier amplitude. If $r\mid Q$, it vanishes unless $k=\ell Q/r$ for $\ell =0,\dots ,r-1$, when it equals $Q/r$. HenceThe second-register states are orthogonal, so their different phases do not change the marginal first-register probabilities. Measurement givesIn the $Q=16$ example the possible outcomes are $0,4,8,12$. A nonzero observed ratio $k/Q$ estimates $\ell /r$, not a prime factor directly. Reducing it gives denominator $r/\gcd (\ell ,r)$; repeating avoids uninformative outcomes or recovers missing order factors. For example, $k=4$ or $12$ gives denominator four, whereas $k=8$ alone gives only two.

When $r\nmid Q$, the Fourier probabilities have narrow peaks near $k/Q=\ell /r$ instead of support only on an exact reciprocal grid. The general marginal distribution isChoosing $Q\ge N^2$ supplies the usual precision for continued-fraction recovery in quantum order finding: a nearest grid sample differs from the target rational by at most $1/(2Q)<1/(2r^2)$. Candidate denominators and extracted divisors are checked classically, and repetitions provide useful samples. The small $Q=16$ example works exactly because its order divides the register size; it is not a general precision guarantee for factoring every four-bit integer.

A sufficiently large reliable quantum computer would undermine RSA by efficient factorization. The related discrete-logarithm algorithm also threatens Diffie-Hellman key exchange and elliptic-curve public-key schemes. This does not imply that every communication scheme or symmetric cipher is broken by the same algorithm; post-quantum cryptography studies alternatives based on other problems. The mathematical speedup assumes a scalable quantum computation with enough precision and error control, not merely a small demonstration of factoring fifteen.

An integer factorization algorithm that iterates a simple map such as $x\mapsto x^2+c\mathrm{mod}n$ and searches for a nontrivial greatest common divisor of $n$ and the difference of two iterates. A collision modulo an unknown prime factor can reveal that factor before a collision modulo $n$. A cycle detection schedule such as Floyd's cycle-finding algorithm limits the number of stored iterates. Unsuccessful choices of seed or map can be retried.

Peter W. Shor's quantum integer factorization and discrete logarithm algorithms. SIAM Journal on Computing 26, 1484–1509.

Cryptography intended to remain secure against adversaries with quantum computers. It includes classical algorithms based on problems other than the integer factorization and discrete logarithm problems efficiently treated by Shor's algorithm. A candidate's security still depends on its precise construction, parameters and known attacks; the label alone is not a proof. It is distinct from requiring quantum hardware for quantum key distribution.

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.

Repeatedly apply the public RSA cryptosystem encryption map to a ciphertext. A return to that ciphertext reveals its preceding iterate as the plaintext. A nontrivial greatest common divisor between an iterate-minus-start and the modulus instead enables integer factorization. Eventual return alone supplies no useful running-time bound.

Recover a plaintext from an RSA cryptosystem ciphertext and the public key, without a supplied private key. Integer factorization of the modulus suffices; the existence of an efficient general reduction in the reverse direction is not known.

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.