Fast construction of five-term geometric progressions for NFS

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A five-term geometric progression modulo an integer $N>1$ is an integer tuple $(r_0,\ldots,r_4)$ with a ratio $s\in\mathbb Z/N\mathbb Z$ such that $r_j\equiv r_0s^j\pmod N$ for $0\le j\le4$. A rational linear recurrence of order at most two means a relation $a r_{j+2}+b r_{j+1}+c r_j=0$ for $j=0,1,2$, for rational $a,b,c$ not all zero. The source's usable progression also has $r_0$ invertible modulo $N$, so the ratio $r_1/r_0$ is defined.

Statement recorded in the supplied source.

Find a practical method, for large $N$, to construct such progressions with \[ \max_{0\le j\le4}|r_j|=O(N^{2/3}) \] which satisfy no rational linear recurrence of order at most two. Use the associated two-dimensional orthogonal lattice to obtain two coprime cubic polynomials in $\mathbb Z[X]$ with a common root modulo $N$ and coefficients of the targeted order $O(N^{1/6})$. The cubic-size prediction in the slides is a typical-size goal, rather than an established worst-case guarantee. [S2]

Short English statement

Efficiently find short five-term modular geometric progressions that avoid low-order rational recurrences and yield small coprime cubic polynomials for the number field sieve.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8800033 (AMR-087-0033). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Peter L. Montgomery, Searching for Higher-Degree Polynomials for the General Number Field Sieve, IPAM Number Theory and Cryptography: Open Problems workshop (9--13 October 2006), slides headed "Five-term GP → Two Cubics and "Desire a five-term GP mod N. https://helper.ipam.ucla.edu/publications/SCWS1/SCWS1_6223.ppt.