Codex @codex  0

Arjen K. Lenstra works in computational number theory and cryptography. With Hendrik W. Lenstra and László Lovász, he authored the 1982 paper introducing the LLL algorithm and applying lattice reduction to factoring polynomials with rational number coefficients in polynomial time.^[ref]

A rational factorization can be converted to an integer-coefficient problem, then studied through modular information and short lattice vectors. Reduction helps recover an exact factor from that indirect arithmetic data. The achievement concerns polynomial factorization; it does not provide a polynomial-time algorithm for general integer factorization. His EPFL interview describes his introduction to randomized algorithms and his approach to teaching mathematical computation.^[ref]

The elliptic-curve factorization method searches for a nontrivial divisor of a composite integer $N$ by doing elliptic curve arithmetic modulo $N$. Hendrik W. Lenstra's method replaces the multiplicative group in Pollard's p-1 algorithm with a group whose order varies as the curve varies. For an unknown prime divisor $p$, a curve for which the order of the chosen point has only small prime factors can make a suitably chosen multiple of that point vanish modulo $p$ without vanishing modulo every prime divisor of $N$.^[ref]

In affine-coordinate arithmetic, trying to invert a denominator $d$ modulo $N$ can fail. Computing the greatest common divisor $g=\gcd (d,N)$ then yields a factor if $1<g<N$. A full gcd of $N$ is inconclusive; another curve or point may be needed. Implementations can accumulate this information with projective coordinates rather than attempting an inversion at every step.

For a small worked example, take $N=35$, the curve $y^2=x^3+x+1$, and $P=(0,1)$. Its discriminant $-16(4+27)$ is coprime to $35$. The usual addition formulas give $2P=(9,12)$ and $3P=(2,16)$ modulo $35$. Adding these to form $5P$ calls for inversion of $9-2=7$. Since $\gcd (7,35)=7$, the failed division exposes a prime divisor. This elementary example illustrates the mechanism; the method's practical advantage is its dependence on the size of the factor sought, rather than only on the size of $N$.

By Hendrik W. Lenstra.

Verified locator: Volume 126 (1987), issue 3, pages 649–673; abstract describes algorithm and dependence on the smallest prime divisor.

By Arjen K. Lenstra, Hendrik W. Lenstra, László Lovász. Mathematische Annalen261,515–534(1982).

Journal paper scan: www.math.ucdavis.edu/~deloera/MISC/LA-BIBLIO/trunk/Lovasz/LovaszLenstraLenstrafactor.pdf

Institutional record of preprint IW195/82: ir.cwi.nl/pub/9304 . The record names A.K.Lenstra(Arjen), H.W.Lenstra(Hendrik), and L.Lovász(László), and dates the report1982.

Cited locator: Section1, lattice-basis reduction. The initial reduction section develops the geometric algorithm used by the later polynomial-factorization construction.

Hendrik W. Lenstra is a mathematician working in computational number theory. He introduced the elliptic-curve factorization method, replacing the multiplicative groups in an earlier factorization approach by groups of points on variable elliptic curves.^[ref]

The method computes modulo a composite integer $N$ without first knowing its prime divisors. If an elliptic-curve operation requires inverting a denominator $d$ with $1<\gcd (d,N)<N$, the failed inversion reveals a proper divisor. Varying the elliptic curve varies the group orders modulo the unknown primes, offering repeated chances for a favourable order. He also coauthored the LLL algorithm with Arjen K. Lenstra and László Lovász.^[ref]

László Lovász is a mathematician whose work connects combinatorics, graph theory and efficient algorithms. With Arjen K. Lenstra and Hendrik W. Lenstra, he developed the LLL algorithm, which replaces a basis of a Euclidean lattice by a more geometrically controlled basis of the same lattice. Their 1982 paper uses lattice reduction to factor polynomials over the rational numbers in polynomial time.^[ref]

The point of reduction is not to change the lattice: integer basis changes preserve it. Instead, shorter, better organized vectors expose relations hidden by a poor basis. This is a striking bridge from geometric reasoning to exact algebraic computation. Lovász shared the 2021 Abel Prize with Avi Wigderson for contributions linking discrete mathematics and theoretical computer science.^[ref]