A polynomial-size prime field meets the soundness budget

Since $T,D\ge 1$ we have $N\ge \max \{2,13\}=13>1$, so [A1] with $n:=N$ yields a prime $p$ with $N<p<2N$. Writing $N=\max \{2,12TD+1\}$ gives $p>N\ge 12TD+1>12TD$ in both cases of the maximum, and $p<2N\le \max \{4,24TD+2\}$; since $T,D\ge 1$, also $24TD+2\le 26TD$, so $p=O(TD)$ and $\lceil {\log }_{2}p\rceil \le {\log }_{2}p+1=O(\log (TD))$. This is claim (1).

Let $m$ be an integer with $1<m<2N$ that is not prime, so $m$ is composite and has a positive divisor $d_0$ with $d_0\mathrm{\ne }1$ and $d_0\mathrm{\ne }m$ by [A2]. Write $m=d_0{m}_1$; the divisor $d:=d_0$ can be replaced by the smaller of the pair $\{d_0,m_1\}$, so we may take $2\le d\le \sqrt{m}$. From $m<2N\le N^2$, valid because $N\ge 2$, we get $\sqrt{m}<N$, hence $d\le N$. Therefore every non-prime $m$ with $1<m<2N$ is inadmissible: admissibility forces primality.

By [A3] the operations of $\mathbb{Z}\mathrm{/}p$ make it a field, and $p>N\ge 2$ is a positive integer, so by [A4] applied to $n:=p$ every class in $\mathbb{Z}\mathrm{/}p$ has exactly one representative in $\{0,1,\dots ,p-1\}$ and the field has exactly $p$ elements. Representatives are integers below $2N$, hence below $2^{1+\lceil {\log }_{2}N\rceil }$: each occupies at most $1+\lceil {\log }_{2}N\rceil =O(\log N)$ bits, and schoolbook add/subtract and multiply on such integers cost $O(\log N)$ and $O({\log }^{2}N)$ bit operations.

Let $a\in \{0,\dots ,p-1\}$ and count the strings of $\{0,1{\}}^k$ whose integer value $U$ satisfies $U\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$; these are exactly the integers in the arithmetic progression $a,a+p,a+2p,\dots$ below $2^k$, so there are at most $\lceil 2^k\mathrm{/}p\rceil \le 2^k\mathrm{/}p+1$ of them. Because $k=2\lceil {\log }_{2}p\rceil$ gives $2^k\ge p^2$, division by $2^k$ yields $\mathrm{Pr}[r=a]\le 1\mathrm{/}p+1\mathrm{/}{p}^2\le 2\mathrm{/}p$, the last step using $p\ge 2$.

Run the search of claim (2). By step 1.1 the prime $p$ of the interval $(N,2N)$ is one of the candidates $N+1,\dots ,2N-1$, and it is admissible: a divisor $d$ of $p$ with $2\le d\le N$ would satisfy $d\mathrm{\ne }p$ because $d\le N<p$, and $d\mathrm{\ne }1$, contradicting primality. So the scan halts, and by step 1.2 its first admissible candidate is prime. There are at most $N-1$ candidates and at most $N-1$ divisors tested for each, so at most $N^2$ trial divisions are performed, each on integers below $2N$ with $O(\log N)$ bits, for $O(N^2{\log }^{2}N)$ bit operations in total. This is claim (2).

By step 1.3 each class of $\mathbb{Z}\mathrm{/}p$ is represented by a unique integer in $\{0,\dots ,p-1\}$ of $O(\log N)=O(\log (TD))$ bits, so one field operation costs $O({\log }^{2}p)$ bit operations: $O(\log p)$ for addition or subtraction of representatives and $O({\log }^{2}p)$ for a schoolbook product followed by reduction modulo $p$. Horner's rule evaluates a polynomial of degree at most $D$ with $D$ multiplications and $D$ additions of representatives, that is $O(D)$ field operations or $O(D{\log }^{2}p)$ bit operations. Since $p<2N\le \max \{4,24TD+2\}$ by step 1.1, this is $O(D{\log }^2(TD))$ bit operations. This is claim (3).

For a set $S$ of residues, $\mathrm{Pr}[r\in S]={\sum }_{a\in S}\mathrm{Pr}[r=a]\le 2\mathrm{\mid }S\mathrm{\mid }\mathrm{/}p$ by step 1.4, the residues outside $\{0,\dots ,p-1\}$ being represented by their unique representative in that range. With $\mathrm{\mid }S\mathrm{\mid }=1$ this reduces to step 1.4, and with $S=\mathrm{\varnothing }$ the bound reads $0\le 0$. This is claim (4).

Claims (1)–(4) are steps 1.1, 2.1, 2.2 and 2.3, so for all integers $T,D\ge 1$ the interval $(N,2N)$ contains a prime $p$ above the budget $12TD$, findable deterministically in $O(N^2{\log }^{2}N)$ bit operations, whose residue field admits $O({\log }^{2}p)$-cost arithmetic and a $2\mathrm{/}p$-point-mass sampler. Every bound is polynomial in $T$ and $D$, which is the content of the statement. ∎