Multi-target hyperbolic sieves and elliptic trace obstructions

Abstract

Let N=pq be a product of two primes, and let ℓ be an odd prime not dividing N. For a∈𝔽_ℓ^*, the set H_a(N;ℓ)={ax+Nx⁻¹:x∈𝔽_ℓ^*} contains the residue of ap+q modulo ℓ. 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 (ℓ+χ(aN))/2, where χ is the Legendre symbol modulo ℓ. 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;ℓ)∪ H_b(N;ℓ)| in terms of K(A,B)=∑_{z∈𝔽_ℓ}χ((z²−A)(z²−B)), A=4aN, B=4bN. The Hasse-Weil bound gives an error of O(√ℓ) from 3ℓ/4. For fixed c≠0,1, we prove the elementary identity K(A,cA)=−1−χ(A)t_c, where t_c=−1−K(1,c). Hence the union for a primitive-root pair (a,b)=(γ,γ²) has at most two sizes as N varies. We give an exact condition on t_γ for the bound 3ℓ/4+1 to hold for every nonzero N modulo ℓ, and compute the first and second moments. For k distinct coefficients, we prove ||⋃_j=1^k H_{a_j}(N;ℓ)| −ℓ(1−2^−k)| ≤ (k−1+2^−k)√ℓ+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^rv.

Notes on Obstructions in the Hyperbolic Clifford Algebra Bundle Structure
Julio Marny Hoff da Silva, Eduardo Notte-Cuello
Axioms2 Nov 2026Peer-reviewedCC BY 4.0General mathematicsCrossref
Notes on obstructions in the hyperbolic Clifford algebra bundle structure
J. M. Hoff da Silva, E. Notte-Cuello
arXiv3 Nov 2026PreprintarXiv licenceFull textMathematical physics High-energy & particle physicsarXiv
A Mixed Elliptic--Hyperbolic Monge--Ampère Problem: Modeling and a Least-Squares Solver
G. V. Carvalho, M. J. H. Anthonissen, J. H. M. ten Thije Boonkkamp +3
arXiv19 Oct 2026PreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv
Existence and non-existence of nonradial solutions to an elliptic equation on hyperbolic space with critical and subcritical nonlinearities
Atanu Manna, Bhakti Bhusan Manna
arXiv8 Sep 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv
Hyperbolic Area Methods in Meromorphic Dynamics and Elliptic Polynomial Skew Products
Zihao Ye
arXiv24 Sep 2026PreprintCC BY 4.0Full textAnalysis & PDEs Dynamical systemsarXiv

Cite

BibTeX RIS

BibTeX

@misc{stanica2026multitarget,
  title = {{Multi-target hyperbolic sieves and elliptic trace obstructions}},
  author = {Pantelimon Stănică and Erik Mulder and Markus Hittmeir},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2606.13018},
  eprint = {2606.13018},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.13018},
}

RIS

TY  - UNPB
TI  - Multi-target hyperbolic sieves and elliptic trace obstructions
AU  - Pantelimon Stănică
AU  - Erik Mulder
AU  - Markus Hittmeir
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2606.13018
UR  - https://arxiv.org/abs/2606.13018
AB  - Let N=pq be a product of two primes, and let ℓ be an odd prime not dividing N. For a∈𝔽_ℓ^*, the set H_a(N;ℓ)={ax+Nx^−1:x∈𝔽_ℓ^*} contains the residue of ap+q modulo ℓ. 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 (ℓ+χ(aN))/2, where χ is the Legendre symbol modulo ℓ. 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;ℓ)∪ H_b(N;ℓ)| in terms of K(A,B)=∑_z∈𝔽_ℓχ((z^2−A)(z^2−B)), A=4aN, B=4bN. The Hasse-Weil bound gives an error of O(√ℓ) from 3ℓ/4. For fixed c≠0,1, we prove the elementary identity K(A,cA)=−1−χ(A)t_c, where t_c=−1−K(1,c). Hence the union for a primitive-root pair (a,b)=(γ,γ^2) has at most two sizes as N varies. We give an exact condition on t_γ for the bound 3ℓ/4+1 to hold for every nonzero N modulo ℓ, and compute the first and second moments. For k distinct coefficients, we prove ||⋃_j=1^k H_a_j(N;ℓ)| −ℓ(1−2^−k)| ≤ (k−1+2^−k)√ℓ+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^rv.
ER  -

Abstract

Related

Cite