O4 — Finding a prime in an arithmetic progression

Definitions and mathematical statement

Let $a,n$ be positive integers with $\gcd(a,n)=1$, supplied in binary. An integer $p$ lies in the prescribed arithmetic progression if $p\equiv a\pmod n$, equivalently if $n$ divides $p-a$. We seek a prime $p$ in this residue class; primes dividing $n$ cannot qualify when $n>1$.

Is there a deterministic classical algorithm which, on every such pair $(a,n)$, outputs a prime $p\equiv a\pmod n$ in a number of bit operations bounded by a fixed polynomial in $\ell(a)+\ell(n)$? Here $\ell(t)=\lfloor\log_2t\rfloor+1$, and output writing is charged to the running time. One may first reduce $a$ modulo $n$; for $n=1$ any prime qualifies. There is no requirement that the output be the least prime in the progression.

The question asks for a single uniform algorithm, with no randomness, auxiliary factorization, or unproved analytic assumption. The coprimality hypothesis supplies the natural domain on which a prime is guaranteed to exist. Existence of primes in the progression alone does not provide the required efficient construction: a search through every candidate up to a bound polynomial in $n$ may still take exponential time in the binary input length. Both locating a candidate and establishing that the reported integer is prime belong to the algorithmic task.

Short English statement

Can a prime in any prescribed coprime residue class be constructed deterministically in time polynomial in the binary input size?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400003 (AMR-083-0003), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Adleman & McCurley - Open Problems in Number Theory Complexity II (1994), O4, p6 / LNCS p296. Original source indexed by AMR-083-0003. https://mccurley.org/papers/open.ps.gz.