Removing the Riemann hypothesis from the equivalence of integer factoring and elliptic-curve point counting modulo N

Factoring an RSA modulus $N=pq$ and counting points on elliptic curves modulo $N$ are polynomial-time equivalent only under Riemann-hypothesis-type assumptions. Counting reduces to factoring unconditionally, via Schoof's algorithm and the Chinese remainder theorem; the converse reduction of Dieulefait and Urroz (2020) — deterministic, for RSA moduli, using affine point counts and quadratic twists — needs the Extended Riemann Hypothesis (ERH) solely to guarantee a polylogarithmic-size twisting parameter whose Legendre symbols at $p$ and $q$ differ, via Ankeny's bound on the least quadratic nonresidue. Later work sharpened but did not remove the hypothesis: Urroz and Pomykała (2024) proved a probabilistic reduction valid for every squarefree $N$, still under GRH; Dąbrowski, Pomykała and Shparlinski (2023) proved an unconditional deterministic reduction that fails on a sparse exceptional set of moduli — precisely those whose least Jacobi nonresidue is not polylogarithmic. The open question is to establish, without any unproved hypothesis, whether factoring is polynomial-time reducible to point counting modulo $N$ for squarefree $N$. The companion efficiency question — computing the number of points modulo $N$ in polynomial time without factoring, where the best known generic method costs $O(N^{1/4+ε})$ — is a distinct open direction, not part of the completion boundary. The problem remains open.

Background

An RSA modulus is an integer $N=pq$ that is the product of two large distinct primes; recovering $p$ and $q$ from $N$ alone is the integer factorization problem on which the security of the RSA cryptosystem rests. A classical line of work in computational number theory asks which other natural computational problems are polynomial-time equivalent to factoring, that is, reducible to it and from it in time polynomial in the bit length of $N$. The prototype is Miller's theorem relating factoring and primality testing to Euler's totient function under the Generalized Riemann Hypothesis (GRH). For factoring-based cryptography the stakes are structural: knowing exactly which oracles and algebraic problems carry the full difficulty of factoring delimits what security reductions can and cannot assume.

Fix $N$ coprime to 6. An elliptic curve modulo $N$ is given by a Weierstrass equation $y^2=x^3+ax+b$ whose discriminant is invertible modulo $N$; its solutions, together with a point at infinity serving as the group identity, form the points of the curve. Over the finite field $F_p$ the projective point count is $|E(F_p)|=p+1-a_p$, where $a_p$ is the trace of the Frobenius endomorphism, an integer attached to the reduction of the curve modulo $p$ that satisfies the Hasse bound $|a_p|≤2√p$; the curve is called supersingular at $p$ when $a_p=0$. The affine count, excluding the point at infinity, is $p−a_p$. For $N=pq$ the Chinese remainder theorem decomposes the point set as a product over the two primes, so the projective count is

$$|E(Z/NZ)|=(p+1−a_p)(q+1−a_q)$$

and the affine count is $(p−a_p)(q−a_q)$. For an integer $d$ coprime to $N$, the quadratic twist $E_d:dy^2=x^3+ax+b$ satisfies $|E_d(F_p)|=p+1−(d/p)a_p$, where $(d/p)=±1$ is the Legendre symbol, equal to $+1$ when $d$ is a quadratic residue modulo $p$ (a nonzero square) and $−1$ when $d$ is a quadratic nonresidue; the Jacobi symbol $(d/N)=(d/p)(d/q)$ equals $−1$ exactly when $d$ is a nonresidue modulo precisely one of the two primes.

One direction of the equivalence is unconditional: given the factorization of $N$, Schoof's algorithm computes $|E(F_p)|$ in deterministic time polynomial in the bit length of $p$, and the Chinese remainder theorem combines the prime-level counts, so point counting is reducible to factoring. Without the factorization no polynomial-time method is known: the generic baby-step/giant-step technique, a meet-in-the-middle search over the group of points, costs $O(N^{1/4+ε})$ operations, which is exponential in the bit length of $N$.

The interesting direction — reducing factoring to a point-counting oracle — is where a hypothesis enters. Kunihiro and Koyama (1998) gave a probabilistic reduction from factoring to counting projective points, assuming an unproved hypothesis on the distribution of point counts across the Hasse interval that later authors judged inaccurate; Martín, Morillo and Villar (2001) proved the analogous statement for computing the order of a single point. Dieulefait and Urroz (2020) gave an identity-based argument for affine counts: if the twist parameter satisfies $(d/p)=−1$ and $(d/q)=+1$, then

$$|E^0(Z/NZ)|+|E_d^0(Z/NZ)|=2p(q−a_q),$$

where the superscript $0$ marks affine counts, so a single greatest-common-divisor computation with $N$ yields $p$ whenever $a_q≠0$ — hence the restriction to curves non-supersingular at both primes. What the argument needs is a small $d$ with Jacobi symbol $(d/N)=−1$: querying all twists $E_d$ for $d$ up to a bound $B$ is polynomial time only when $B$ is polylogarithmic in $N$. Under the Extended Riemann Hypothesis (ERH) — the Riemann hypothesis for Dirichlet $L$-functions, the $L$-functions attached to Dirichlet characters — Ankeny's bound on the least quadratic nonresidue supplies such a $d$ of size $O((log N)^2)$, yielding the theorem of Dieulefait and Urroz: under ERH, factoring an RSA modulus is polynomial-time equivalent to counting points, affine or projective, of elliptic curves modulo $N$ that are non-supersingular at both primes. The hypothesis enters nowhere else in the reduction.

Subsequent work sharpened the equivalence while leaving its hypothesis untouched. Dryło and Pomykała (2020) extended it to all integers outside an exceptional set, under a heuristic assumption on the distribution of Frobenius traces. Dąbrowski, Pomykała and Shparlinski (2023) proved the strongest unconditional statement to date: with an oracle that returns suitable small multiples of the numbers of points of certain elliptic curves modulo $n$, a deterministic polynomial-time algorithm factors all integers $n≤B$ with at most $B(log B)^{−C/log log log B}$ exceptions, the exceptions being precisely the moduli whose least Jacobi nonresidue is not polylogarithmic. Jiménez Urroz and Pomykała (2024) removed all heuristic distribution assumptions, giving a probabilistic reduction of the complete factorization of any squarefree $n$ to point counting with success probability $1−ε$ — but still under GRH, via the conditional bounds of Lamzouri, Li and Soundararajan for the least quadratic nonresidue. In every route the same obstruction appears: unconditionally, the best known bounds for the least quadratic nonresidue are powers of $p$, exponential in the bit length, and polylogarithmic bounds constitute Vinogradov's conjecture, a major open problem in analytic number theory.

Dieulefait and Urroz arrived at the equivalence through the malleability of factoring — whether an algorithm for factoring $N$ may use an auxiliary factorization of a coprime integer — a notion introduced by Paillier and Villar in their study of trade-offs between one-wayness and chosen-ciphertext security (security against adversaries allowed to obtain decryptions of ciphertexts of their choice) for factoring-based encryption; that cryptographic motivation is separable from the equivalence considered here.

Problem Statement

For a squarefree integer $N$ coprime to 6, so that the short Weierstrass model and the quadratic twists above are defined — in the first instance an RSA modulus $N=pq$ — consider the point-counting oracle which, given a Weierstrass equation $E$ with discriminant invertible modulo $N$ and an integer $d$ coprime to $N$ (including $d=1$), returns the number of affine points of the quadratic twist $E_d$ modulo $N$; a second version of the oracle returns projective counts. Say that factoring is polynomial-time reducible to point counting modulo $N$ if some algorithm, given $N$ and access to this oracle with each query counted as one step, outputs the complete factorization of $N$ in time polynomial in the bit length of $N$. This reduction is known under ERH (deterministically, for RSA moduli, via affine counts) and under GRH (probabilistically, for all squarefree $N$, rigorously); the problem is to settle the relationship with no unproved hypothesis.

A positive resolution is an unconditional reduction: an algorithm as above that factors every squarefree $N$ coprime to 6 — deterministically, or probabilistically with success probability at least $1−ε$ for every $ε>0$ supplied as an input — together with a correctness proof in which every invoked result is used strictly within its unconditional scope; in particular no ERH or GRH, and no conjectural bound on least quadratic nonresidues. A negative resolution must settle the general question as stated, not merely rule out one formalized class of reduction schemes. An unconditional point-counting algorithm without factoring — an improvement of the generic $O(N^{1/4+ε})$ baby-step/giant-step bound — would be major progress on the companion efficiency question recorded in the background, but would not by itself settle the present problem: in every known reduction the Riemann-hypothesis-type assumption is invoked to guarantee a polylogarithmic-size twist parameter with Jacobi symbol $−1$ before the counting oracle is queried, so composing such an algorithm with the known reductions leaves that requirement in place and yields at most the conditional equivalence.

References

1. Luis V. Dieulefait and Jorge Urroz, 'Factorization and Malleability of RSA Moduli, and Counting Points on Elliptic Curves Modulo N', Mathematics 8(12):2126, 2020. DOI: 10.3390/math8122126, https://doi.org/10.3390/math8122126.
2. Jorge Jiménez Urroz and Jacek Pomykała, 'Factoring numbers with elliptic curves', The Ramanujan Journal 64(1):265–273, 2024. DOI: 10.1007/s11139-023-00822-1, https://doi.org/10.1007/s11139-023-00822-1; arXiv:2210.04835, https://arxiv.org/abs/2210.04835.
3. Andrzej Dąbrowski, Jacek Pomykała and Igor E. Shparlinski, 'On oracle factoring of integers', Journal of Complexity 76:101741, 2023. DOI: 10.1016/j.jco.2023.101741, https://doi.org/10.1016/j.jco.2023.101741; arXiv:1912.00345, https://arxiv.org/abs/1912.00345.
4. N. Kunihiro and K. Koyama, 'Equivalence of counting the number of points on elliptic curve over the ring Zn and factoring n', in: Advances in Cryptology — EUROCRYPT'98, 1998, pp. 47–58. DOI: 10.1007/bfb0054116, https://doi.org/10.1007/bfb0054116.
5. S. Martín, P. Morillo and J. L. Villar, 'Computing the order of points on an elliptic curve modulo N is as difficult as factoring N', Applied Mathematics Letters 14:341–346, 2001. DOI: 10.1016/S0893-9659(00)00159-2, https://doi.org/10.1016/S0893-9659(00)00159-2.
6. Robert Dryło and Jacek Pomykała, 'Integer factoring problem and elliptic curves over the ring Z_n', Colloquium Mathematicum 159:259–284, 2020. DOI: 10.4064/cm7661-2-2019, https://doi.org/10.4064/cm7661-2-2019.
7. Robert Dryło, 'Factoring integers and oracles for elliptic and hyperelliptic curves', Banach Center Publications 126:27–40, 2023. DOI: 10.4064/bc126-2, https://doi.org/10.4064/bc126-2.
8. N. C. Ankeny, 'The Least Quadratic Non Residue', Annals of Mathematics 55:65–72, 1952. DOI: 10.2307/1969420, https://doi.org/10.2307/1969420.
9. Youness Lamzouri, Xiannan Li and Kannan Soundararajan, 'Conditional bounds for the least quadratic non-residue and related problems', Mathematics of Computation 84:2391–2412, 2015. DOI: 10.1090/S0025-5718-2015-02925-1, https://doi.org/10.1090/S0025-5718-2015-02925-1; arXiv:1309.3595, https://arxiv.org/abs/1309.3595.
10. R. Schoof, 'Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p', Mathematics of Computation 44:483–494, 1985. DOI: 10.1090/S0025-5718-1985-0777280-6, https://doi.org/10.1090/S0025-5718-1985-0777280-6.
11. H. W. Lenstra, Jr., 'Factoring Integers with Elliptic Curves', Annals of Mathematics 126:649–673, 1987. DOI: 10.2307/1971363, https://doi.org/10.2307/1971363.
12. P. Paillier and J. L. Villar, 'Trading One-Wayness Against Chosen-Ciphertext Security in Factoring-Based Encryption', in: Advances in Cryptology — ASIACRYPT 2006, Lecture Notes in Computer Science 4284, 2006, pp. 252–266. DOI: 10.1007/11935230_17, https://doi.org/10.1007/11935230_17.
13. G. L. Miller, 'Riemann's hypothesis and tests for primality', Journal of Computer and System Sciences 13:300–317, 1976. DOI: 10.1016/S0022-0000(76)80043-8, https://doi.org/10.1016/S0022-0000(76)80043-8.
14. Florian Luca, Dimbinaina Ralaivaosaona and Jorge Jiménez Urroz, 'On pseudoprime RSA moduli', Afrika Matematika 36(3):118, 2025. DOI: 10.1007/s13370-025-01338-1, https://doi.org/10.1007/s13370-025-01338-1.
15. Jacek Pomykała and Mariusz Jurkiewicz, 'Decomposition of RSA modulus applying even order elliptic curves', arXiv:2503.00950, 2025, https://arxiv.org/abs/2503.00950.
16. Przemysław Koprowski, 'Isotropic vectors over global fields', Mathematics of Computation 95(359):1541–1567, 2025. DOI: 10.1090/mcom/4165, https://doi.org/10.1090/mcom/4165; arXiv:2111.08569, https://arxiv.org/abs/2111.08569.
17. Jacek Pomykała and Olgierd Żołnierczyk, 'Elliptic-Curve Factorization and Witnesses', in: International Conference on Computational Science (ICCS 2024), Springer, 2024. DOI: 10.1007/978-3-031-63749-0_20, https://doi.org/10.1007/978-3-031-63749-0_20.
18. N. A. Carella, 'Upper Bound of the Least Quadratic Nonresidues', arXiv:2106.00544, 2021, https://arxiv.org/abs/2106.00544. (Unrefereed preprint.)