bibkey: lenstra1982factorization
authors: A. K. Lenstra; H. W. Lenstra Jr.; L. Lovász
year: 1982
title: "Factoring polynomials with rational coefficients"
doi: 10.1007/BF01457454
url: https://pub.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1982d/art.pdf
claim: Under the standard binary encoding of a univariate rational polynomial, factoring into irreducibles is a deterministic polynomial-time task.
strata_touched: []
license: citation-only
triage: anchor

Factoring rational polynomials

The source is A. K. Lenstra, H. W. Lenstra Jr. and L. Lovász, “Factoring polynomials with rational coefficients”, Mathematische Annalen 261 (1982), 515–534, DOI 10.1007/BF01457454, author-hosted scan.

The result is used only as a boundary example: a compact polynomial expansion does not by itself identify an NP-hard inverse problem. Factoring is a separate task with its own input encoding and output contract; it does not recover an arbitrary generation history, and it supplies no FIB readout or observer-growth interface.