Improved deterministic integer factorization by quadratic-image sieving
Abstract
Let N=pq be a semiprime and let ℓnmid N be an odd prime. For a≠0 modulo ℓ, put Ha(N;ℓ)={ax+Nx−1:x∈Fℓ*}. For a primitive root γ, the size of Hγ(N;ℓ)∪ Hγ2(N;ℓ) is determined by the Frobenius trace of Y2=(X2−1)(X2−γ). We study the resulting trace-selection problem through finite certificates, a congruence modulo $8$, and a GRH-conditional positive-density family from the CM specialization γ=2. Independently of this conditional result, we obtain a deterministic factorization algorithm from the residue-known coefficient lattice of Harvey and Hittmeir (\emph{Math. Comp.}, 2022). The actual babystep index is a nondegenerate quadratic image modulo each selected prime divisor of the auxiliary modulus. After a computable translation, every such image avoids a fixed set of (ℓ−χ(−1))/4 residues. This forbidden set is optimal among translated sets that must handle both square classes of the leading coefficient. Gauss reduction, a nearby lattice-vector selection, arbitrary-point multipoint evaluation, and the unrestricted large-order algorithm of Harvey and Hittmeir (arXiv, 2026) give the bit-complexity bound N1/5exp(−(log(4/3)/50+o(1))log N/loglog N). Its secondary factor is asymptotically smaller than every fixed negative power of log N, improving the general bound of Harvey and Hittmeir (\emph{Math. Comp.}, 2022) and the balanced-semiprime bound of Gao et al.\ (arXiv, 2025).
Related
- Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization
- Faster Deterministic Integer Root Finding for Integer Polynomials
- Non-convex integer programming: a deterministic solution method of the large block sale problem
- A sequential quadratic programming method for optimization with expectation objective functions, deterministic inequality constraints and robust subproblems
- A single LU~factorization approach to model reduction for linear system families with a quadratic matrix pencil
BibTeX
@misc{stanica2026improved,
title = {{Improved deterministic integer factorization by quadratic-image sieving}},
author = {Pantelimon Stănică},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06580},
eprint = {2611.06580},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06580},
}
RIS
TY - UNPB
TI - Improved deterministic integer factorization by quadratic-image sieving
AU - Pantelimon Stănică
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06580
UR - https://arxiv.org/abs/2611.06580
AB - Let N=pq be a semiprime and let ℓnmid N be an odd prime. For a≠0 modulo ℓ, put H_a(N;ℓ)={ax+Nx^−1:x∈F_ℓ^*}. For a primitive root γ, the size of H_γ(N;ℓ)∪ H_γ^2(N;ℓ) is determined by the Frobenius trace of Y^2=(X^2−1)(X^2−γ). We study the resulting trace-selection problem through finite certificates, a congruence modulo $8$, and a GRH-conditional positive-density family from the CM specialization γ=2. Independently of this conditional result, we obtain a deterministic factorization algorithm from the residue-known coefficient lattice of Harvey and Hittmeir (\emph{Math. Comp.}, 2022). The actual babystep index is a nondegenerate quadratic image modulo each selected prime divisor of the auxiliary modulus. After a computable translation, every such image avoids a fixed set of (ℓ−χ(−1))/4 residues. This forbidden set is optimal among translated sets that must handle both square classes of the leading coefficient. Gauss reduction, a nearby lattice-vector selection, arbitrary-point multipoint evaluation, and the unrestricted large-order algorithm of Harvey and Hittmeir (arXiv, 2026) give the bit-complexity bound N^1/5exp(−(log(4/3)/50+o(1))log N/loglog N). Its secondary factor is asymptotically smaller than every fixed negative power of log N, improving the general bound of Harvey and Hittmeir (\emph{Math. Comp.}, 2022) and the balanced-semiprime bound of Gao et al.\ (arXiv, 2025).
ER -