Multi-target hyperbolic sieves and elliptic trace obstructions

Abstract

Let $N=pq$ be a product of two primes, and let $\ell$ be an odd prime not dividing $N$. For $a\in {\mathbb{F}}_{\ell }^{\ast }$, the set \[ H_a(N;\ell)=\{ax+Nx^{-1}:x\in\mathbb F_\ell^*\} \] contains the residue of $ap+q$ modulo $\ell$. Since residues outside this set can be excluded when searching for that linear form, it has been applied as a sieve for linear combinations of $p$ and $q$ in recent deterministic integer factorization methods. Its size is $(\ell +\chi (aN))/2$, where $\chi$ is the Legendre symbol modulo $\ell$. We study unions of these sets, which give a common set of candidate residues for several linear forms and thus allow to sieve for multiple target forms at once. For distinct $a,b$, we obtain an exact formula for $|H_a(N;\ell )\cup H_b(N;\ell )|$ in terms of \[ K(A,B)=\sum_{z\in\mathbb F_\ell}χ((z^2-A)(z^2-B)), \qquad A=4aN,\quad B=4bN. \] The Hasse-Weil bound gives an error of $O(\sqrt{\ell })$ from $3\ell /4$. For fixed $c\ne 0,1$, we prove the elementary identity $K(A,cA)=-1-\chi (A)t_c$, where $t_c=-1-K(1,c)$. Hence the union for a primitive-root pair $(a,b)=(\gamma ,{\gamma }^2)$ has at most two sizes as $N$ varies. We give an exact condition on $t_{\gamma }$ for the bound $3\ell /4+1$ to hold for every nonzero $N$ modulo $\ell$, and compute the first and second moments. For $k$ distinct coefficients, we prove \[ \left|\left|\bigcup_{j=1}^k H_{a_j}(N;\ell)\right| -\ell(1-2^{-k})\right| \le (k-1+2^{-k})\sqrt\ell+k. \] We derive the corresponding bounds modulo products of distinct primes using the Chinese remainder theorem. We also determine the exact size of the image obtained by restricting $x$ to the nonzero $r$-th powers, which applies when searching for a divisor of the form $u^r$ in $N=u^{r}v$.

arXiv comment23 pages