betaFeedback

WorksMathematics

A Little Advice Suffices: Diffie-Hellman Is as Hard as Discrete Logarithm

Abstract

Is computing a Diffie-Hellman key as hard as computing a discrete logarithm? Maurer showed that it is, given a few bits of advice, provided that short intervals contain enough integers with only small prime factors; that proviso has stood for thirty years. We remove it. For every prime pp there is an advice string of O(log⁡p)O(\log p) bits, depending only on pp, with which discrete logarithms in every group of order pp are computed in polynomial time from a Diffie-Hellman oracle. The reduction is the classical one; what was missing was a proof that short intervals contain polylogarithmically smooth integers. We show that a zero-free half-plane for the Riemann zeta function, which is now known, gives the expected number of (log⁡x)K(\log x)^K-smooth integers in every interval [x,x+xθ][x,x+x^θ] with θ>17/30θ>17/30. With smoothness this small the saddle point of the counting integral lies just to the left of the line Re s=1\mathrm{Re}\,s=1, and a zero-free strip of any fixed width absorbs the shift once KK is large. Genus-2 Jacobians, whose orders fill such intervals, then turn one of these integers into the order of an auxiliary group. The same input removes the smoothness assumption from Maurer and Raub's impossibility of field-homomorphic one-way permutations and from the yes/no-query reduction of Koblitz, Menezes and Shparlinski. It also makes Wolf's characterisation unconditional: discrete logarithm and Diffie-Hellman are generically equivalent exactly when the group order has no large repeated prime factor.

Introduction

The Diffie–Hellman protocol [10] is secure only if the computational Diffie–Hellman problem is hard: given gag^a and gbg^b in a cyclic group, compute gabg^{ab}. What cryptographers actually believe hard in the groups they deploy is the discrete logarithm problem: given gag^a, compute aa. A discrete-logarithm algorithm breaks Diffie–Hellman at once. Whether the converse holds, so that the protocol is exactly as secure as discrete logarithms, has been asked since the protocol appeared.

The known answers all follow one idea, due to den Boer [9] and Maurer [18]. A Diffie–Hellman oracle lets one multiply hidden exponents, so the hidden aa can be treated as an element of a field one can compute with but cannot read. Put aa into an auxiliary algebraic group over Fp\mathbb{F}_p whose order has only small prime factors, solve the discrete logarithm there by Pohlig–Hellman, and read aa back. Everything works once such an auxiliary group exists. Maurer used elliptic curves, whose orders fill the interval [p+1−2p,p+1+2p][p+1-2\sqrt p,p+1+2\sqrt p], and needed this interval to contain a polylogarithmically smooth integer, which is almost unknown. Maurer and Wolf [25, 34], Boneh and Lipton [3], and Maurer and Raub [19] built on the same assumption.

Without it, the best reduction ran in time exp⁡((log⁡p)2/3+o(1))\exp((\log p)^{2/3+o(1)}) [34, 26]. Under the Riemann Hypothesis, Koblitz, Menezes and Shparlinski [14] reached exp⁡(O(log⁡plog⁡log⁡p))\exp(O(\sqrt{\log p\log\log p})) with the help of εlog⁡p\varepsilon\log p answers from an all-knowing oracle; they called a polynomial-time reduction a “holy grail” that “seems a long way off”, and named the missing input: smooth numbers in short intervals for smoothness bounds below exp⁡(log⁡x)\exp(\sqrt{\log x}).

The missing input. Genus-2 Jacobians widen the window. Their orders over Fp\mathbb{F}_p fill [p2−12p3/2,p2+12p3/2][p^2-\frac{1}{2}p^{3/2},p^2+\frac{1}{2}p^{3/2}], an interval of the form [x,x+x3/4][x,x+x^{3/4}], and Lenstra, Pila and Pomerance [17] showed that all but at most pp integers there are such orders. Elliptic curves give only intervals of the form [x,x+4x1/2][x,x+4x^{1/2}]. What is needed is more than pp integers in that window whose prime factors are all at most (log⁡p)K(\log p)^K. Unconditional methods give smooth numbers in [x,x+xθ][x,x+x^\theta] only for smoothness bounds y≥exp⁡((log⁡x)2/3+o(1))y \ge\exp((\log x)^{2/3+o(1)}), because they rely on the Vinogradov–Korobov zero-free region. Younis recently reached y=(log⁡x)Ky=(\log x)^K under the Riemann Hypothesis [35].

A zero-free half-plane suffices. We prove that any half-plane Re⁡s>1−δ\operatorname{Re}s>1-\delta free of zeros of ζ\zeta is enough (Theorem 3): for every θ>17/30\theta>17/30 and every fixed KK above a threshold depending on θ\theta and δ\delta, the number of yy-smooth integers in [x,x+h][x,x+h], y=(log⁡x)Ky=(\log x)^K, is asymptotic to the count predicted by the density of yy-smooth integers near xx whenever xθ≤h=o(x)x^\theta\le h=o(x). This range contains the genus-2 window, θ=3/4\theta=3/4, but not the elliptic-curve window, θ=1/2\theta=1/2. Such a half-plane, with δ=1/8\delta=1/8, is now known [27], so our results are unconditional. The count is a contour integral of ζ(s,y)xs\zeta(s,y)x^s, which one shifts to the left of the saddle point α≈1−1/K\alpha\approx1-1/K. A zero of ζ\zeta at distance ν\nu from the line Re⁡s=1\operatorname{Re}s=1 costs a factor x(1−α)−νx^{(1-\alpha)-\nu}, the half-plane guarantees ν≥δ\nu\ge\delta, and the zero-density estimate of Guth and Maynard [11] bounds how many zeros there are. Polylogarithmic smoothness moves the saddle point only about 1/K1/K from the line, and the strip 1−δ<Re⁡s<11-\delta<\operatorname{Re}s<1 absorbs this once KK is large in terms of δ\delta. Earlier arguments placed the saddle point deep inside the zero-free region, which forced much larger yy [36]; what lets it leave that region is a local shift bound that holds for every y≥2y\ge2 (Lemma 15 in Appendix § 9).

Results. With this input, Maurer’s method goes through with genus-2 Jacobians.

Theorem 1. There are a constant cc and a probabilistic algorithm A\mathcal{A} with the following property. For every prime pp there is an advice string σp\sigma_p of at most 30⌈log⁡2p⌉+1230\lceil\log_2 p\rceil+12 bits such that for every cyclic group GG of order pp, every generator gg and every aa, the algorithm A\mathcal{A} given pp, σp\sigma_p, gag^a and a Diffie–Hellman oracle for (G,g)(G,g) outputs aa in expected time O((log⁡p)c)O((\log p)^c).

The advice depends only on pp: one string serves every group of order pp, for instance every elliptic curve group of that order, and every generator. Sections 5 and 6 derive the following.

  • Imperfect adversaries. An algorithm that solves Diffie–Hellman on a fraction ε\varepsilon of inputs yields discrete logarithms in time poly⁡(log⁡p,1/ε)\operatorname{poly}(\log p,1/\varepsilon) (Corollary 12).

  • A complete characterisation. In cyclic groups of order nn, the generic non-uniform complexity of computing discrete logarithms from a Diffie–Hellman oracle lies between q/2−1\sqrt{q}/2-1 and (log⁡n)O(1)(1+q)(\log n)^{O(1)}(1+\sqrt{q}), where qq is the largest prime with q2∣nq^2\mid n (Theorem 13). Wolf proved this dichotomy under his smoothness assumption [34].

  • Black-box fields. Extraction from a black-box field is polynomial-time with advice for every finite field. So, for characteristic fixed by the security parameter, there are no field-homomorphic one-way permutations against non-uniform adversaries (Corollary 14); Maurer and Raub proved this for small characteristic [19].

  • Less advice. With εlog⁡p\varepsilon\log p yes/no queries instead of advice the reduction is still polynomial (Theorem 9); with a one-time precomputation of pεp^\varepsilon steps per prime it costs (log⁡p)O(1/ε)(\log p)^{O(1/\varepsilon)} per instance (Corollary 10); with no help at all it takes exp⁡(O(log⁡plog⁡log⁡p))\exp(O(\sqrt{\log p\log\log p})) (Theorem 11).

Contributions.

  • A theorem on smooth numbers. A zero-free half-plane for ζ\zeta gives the expected count of polylogarithmically smooth integers in short intervals.

  • An unconditional equivalence. Discrete logarithm and Diffie–Hellman are polynomially equivalent in every group of prime order, with logarithmic advice that depends only on the order, and the classical consequences of this equivalence hold without assumptions.

  • An explanation. The reduction was never the obstacle; the existence of smooth group orders was. A zero-free strip of any fixed width provides them, because polylogarithmic smoothness keeps the saddle point close to the line Re⁡s=1\operatorname{Re} s = 1.

Technical overview. The reduction (§ 4) is Maurer’s, written for genus 2 as in [34, 14]. A Diffie–Hellman oracle turns the group into a black-box field: gag^a represents aa, the group operation adds, the oracle multiplies, and inversion is exponentiation by p−2p - 2. The advice names a genus-2 curve Y2=f(X)Y^2 = f(X) whose Jacobian JJ has (log⁡p)K(\log p)^K-smooth order, together with a basis of J(Fp)J(\mathbb{F}_p). The algorithm shifts aa by a random rr until f(a+r)f(a + r) is a square, takes an implicit square root, and so holds the point (a+r,b)(a + r,b) of the curve, hence the class D=[(a+r,b)−∞]∈J(Fp)D = [(a + r,b) - \infty] \in J(\mathbb{F}_p), in encoded form. Cantor’s algorithm runs on encoded coordinates. A Pohlig–Hellman routine for a non-cyclic group with an explicit basis and an encoded target writes DD in the basis; the explicit representation of DD then shows a+ra+r. § 3 and Appendix § 9 prove the smooth-number theorem, from which § 3 derives Proposition 6; this is the only place where analytic number theory enters.

Related work. Den Boer [9] proved the equivalence for primes pp with p−1p - 1 smooth. Maurer [18] and Maurer and Wolf [23, 25, 26] introduced auxiliary groups, advice, and the amplification of faulty oracles, and proved generic lower bounds for orders with repeated prime factors [24]; Wolf’s thesis [34] collects these results and the genus-2 variant. Boneh and Lipton [3] introduced black-box fields and a uniform subexponential algorithm under a smoothness assumption; Maurer and Raub [19] treated extension fields. Koblitz, Menezes and Shparlinski [14] studied reductions with auxiliary oracles, and May and Schneider [21] gave concrete reductions for standardised curves. Lenstra, Pila and Pomerance [16, 17] introduced genus-2 Jacobians to obtain rigorous smoothness tests. On smooth numbers in short intervals, Soundararajan [31] and Matomäki and Radziwiłł [MR16] treat large smoothness bounds, Younis [35] the polylogarithmic range under the Riemann Hypothesis (our proof makes his constant explicit, Appendix § 9), and Zhang [36] a fixed zero-free strip for y=exp⁡(log⁡xlog⁡log⁡x)y = \exp(\sqrt{\log x \log\log x}). Our reduction is the classical one; what is new is the proof that the auxiliary groups exist.

Preliminaries

Groups and oracles. Throughout, pp is a prime and ℓ=⌈log⁡2p⌉\ell= \lceil\log_2 p\rceil. A group GG of order pp with generator gg is given by encodings of its elements together with algorithms (or oracles) for the group operation, inversion and equality. The Diffie–Hellman oracle for (G,g)(G,g) maps (ga,gb)(g^a,g^b) to gabg^{ab}. The discrete logarithm problem asks for aa given gag^a. Running times count group operations, oracle calls and bit operations. An advice string for pp is a bit string that may depend on pp but not on the group, the generator or the instance. We write Lp(12,c)=exp⁡((c+o(1))log⁡plog⁡log⁡p)L_p(\frac{1}{2},c)=\exp((c+o(1))\sqrt{\log p\log\log p}).

Black-box fields. Following Boneh and Lipton [3] and Maurer and Raub [19], a black-box field isomorphic to Fp\mathbb{F}_p is an unknown injective encoding s:Fp→{0,1}ms:\mathbb{F}_p \to\{0,1\}^m together with oracles that return s(a±b)s(a \pm b), s(ab)s(ab) and s(a−1)s(a^{-1}) (for a≠0a \ne0) from s(a)s(a) and s(b)s(b); the encodings s(0)s(0) and s(1)s(1) are given, and equality of field elements is equality of encodings. The extraction problem asks for aa given s(a)s(a). For an explicit c∈Fpc \in\mathbb{F}_p one computes s(c)s(c) from s(1)s(1) with O(ℓ)O(\ell) additions.

Lemma 2 (Diffie–Hellman oracles implement black-box fields [18, 3, 19]). Let G=⟨g⟩G = \langle g \rangle have order pp and put s(a)=gas(a) = g^a. Then addition, subtraction and equality are the group operation, inversion and equality of GG; multiplication is one call to the Diffie–Hellman oracle; and inversion, s(a−1)=s(ap−2)s(a^{-1}) = s(a^{p-2}), takes at most 2ℓ2\ell oracle calls. In particular, an algorithm that solves extraction for black-box fields isomorphic to Fp\mathbb{F}_p with TT field operations solves the discrete logarithm problem in every group of order pp with O(ℓT)O(\ell T) group operations and oracle calls.

An Fp\mathbb{F}_p-program with equality tests computes on field elements (explicit constants and one hidden input aa) with ++, −-, ×\times, and division by elements that it has itself tested to be non-zero, and it may branch on equality tests between its data. Such a program runs unchanged when aa is given only as s(a)s(a): replace every datum dd by s(d)s(d), every operation by an oracle call and every test by a comparison of encodings. It then outputs the encodings of its results and all of its branch bits. Horner evaluation, square-and-multiply, the Tonelli–Shanks square-root algorithm with an explicit quadratic non-residue [30], and Cantor’s algorithm for Jacobians of hyperelliptic curves [4] are such programs.

Smooth numbers. An integer n≥1n \ge1 is yy-smooth if all its prime factors are at most yy, and Ψ(x,y)=#{n≤x:n is y-smooth}\Psi(x,y) = \#\{n \le x : n\text{ is }y\text{-smooth}\}. We write u=log⁡x/log⁡yu = \log x/\log y, and α=α(x,y)\alpha= \alpha(x,y) for the saddle point, the σ>0\sigma> 0 minimising xσζ(σ,y)x^\sigma\zeta(\sigma,y) with ζ(s,y)=∏q≤y(1−q−s)−1\zeta(s,y) = \prod_{q \le y}(1-q^{-s})^{-1} [13]. For fixed K>1K > 1 one has Ψ(x,(log⁡x)K)=x1−1/K+o(1)\Psi(x,(\log x)^K) = x^{1-1/K+o(1)} [8, 5].

Genus-2 Jacobians. For a squarefree quintic f∈Fp[X]f \in\mathbb{F}_p[X], the equation Y2=f(X)Y^2 = f(X) defines a curve CfC_f of genus 2 with one point ∞\infty at infinity; JfJ_f denotes its Jacobian. Every class in Jf(Fp)J_f(\mathbb{F}_p) has a unique reduced Mumford representation (u,v)(u,v): u,v∈Fp[X]u,v \in\mathbb{F}_p[X], uu monic, deg⁡v<deg⁡u≤2\deg v < \deg u \le2, and u∣v2−fu \mid v^2-f [4]. An affine point (a,b)∈Cf(Fp)(a,b) \in C_f(\mathbb{F}_p) gives the class [(a,b)−∞][(a,b)-\infty] with representation (X−a,b)(X-a,b). Cantor’s algorithm adds two reduced representations with O(1)O(1) field operations, among them O(1)O(1) inversions. The group Jf(Fp)J_f(\mathbb{F}_p) has order in [(p−1)4,(p+1)4][(\sqrt{p}-1)^4,(\sqrt{p}+1)^4] and is a product of at most four cyclic groups, since for every prime qq the qq-torsion of Jf(Fp)J_f(\mathbb{F}_p) has rank at most 4 [22]. If ff has leading coefficient cc, then f~(X)=c−6f(cX)\tilde f(X)=c^{-6}f(cX) is monic and (X,Y)↦(cX,c3Y)(X,Y)\mapsto(cX,c^3Y) is an isomorphism Cf→Cf~C_f \to C_{\tilde f} over Fp\mathbb{F}_p, so we may take ff monic.

Smooth numbers in short intervals

Theorem 3. Let 0<δ≤120 < \delta\le\frac{1}{2} and suppose ζ(s)≠0\zeta(s) \ne0 for Re⁡s>1−δ\operatorname{Re}s > 1-\delta. Let 17/30<θ≤117/30 < \theta\le1 and

K>K∗(θ,δ):=13+30δδ(30θ−17).K > K^*(\theta,\delta) := \frac{13+30\delta}{\delta(30\theta-17)}.

There are ε0>0\varepsilon_0 > 0, CC and x0x_0, depending only on δ,θ,K\delta,\theta,K, such that for all x≥x0x \ge x_0, xθ≤h≤xx^\theta\le h \le x and (log⁡x)K≤y≤xε0(\log x)^K \le y \le x^{\varepsilon_0},

∣Ψ(x+h,y)−Ψ(x,y)α(h/x)Ψ(x,y)−1∣≤C(1u+hxlog⁡(u+1)log⁡y),(1)\left|\frac{\Psi(x+h,y)-\Psi(x,y)}{\alpha(h/x)\Psi(x,y)}-1\right| \le C\left(\frac{1}{u}+\frac{h}{x}\frac{\log(u+1)}{\log y}\right), \tag*{(1)}

and in particular Ψ(x+h,y)−Ψ(x,y)≥13hΨ(x,y)/x\Psi(x+h,y)-\Psi(x,y) \ge\frac{1}{3}h\Psi(x,y)/x.

Theorem 3 also gives the hyperelliptic curve method of Lenstra, Pila and Pomerance a proved running time Lp(12,2)(log⁡n)O(1)L_p(\frac{1}{2},2)(\log n)^{O(1)} for splitting an integer nn whose least prime factor is pp [37].

We apply Theorem 3 with the half-plane of [27]:

Theorem 4 ([27]). ζ(s)≠0\zeta(s) \ne0 for Re⁡s>7/8\operatorname{Re}s > 7/8.

Any fixed δ>0\delta> 0 suffices for every result in this paper; only the smoothness exponent KK, and hence the degree of the polynomial in Theorem 1, depends on it.

How the proof goes. Perron’s formula writes Ψ(x+h,y)−Ψ(x,y)\Psi(x+h,y)-\Psi(x,y) as 12πi∫ζ(s,y)(x+h)s−xss ds\frac{1}{2\pi i}\int\zeta(s,y)\frac{(x+h)^s-x^s}{s}\,ds over a vertical segment through the saddle point α\alpha, with height H=x1+1/K+ε1/hH=x^{1+1/K+\varepsilon_1}/h. As in Younis [35] and Zhang [36], the segment is moved onto a contour that stays on Re⁡s=α\operatorname{Re}s=\alpha near the real axis, bends left along an exponential path, wraps around each zero of ζ\zeta at a distance proportional to its distance from the line Re⁡s=1\operatorname{Re}s=1, and otherwise runs along Re⁡s=(1+ε)/2\operatorname{Re}s=(1+\varepsilon)/2 for a small fixed ε>0\varepsilon>0. The integrand is holomorphic in Re⁡s>0\operatorname{Re}s>0. The central part gives the main term α(h/x)Ψ(x,y)\alpha(h/x)\Psi(x,y) by the saddle-point method of Hildebrand and Tenenbaum [13]. Elsewhere one needs a saving over xαζ(α,y)x^\alpha\zeta(\alpha,y), and it comes from moving left: as long as no zero is near, ∣xsζ(s,y)∣\lvert x^s\zeta(s,y)\rvert drops by x−(1−ε)(α−σ)x^{-(1-\varepsilon)(\alpha-\sigma)} when Re⁡s\operatorname{Re}s drops from α\alpha to σ\sigma (Lemma 15). This local shift holds for every y≥2y\ge2. Earlier versions required y≥exp⁡((log⁡log⁡x)2)y\ge\exp((\log\log x)^2) or a saddle point within εδ\varepsilon\delta of the line Re⁡s=1\operatorname{Re}s=1; without these conditions yy can be polylogarithmic, and then the saddle point sits about 1/K1/K from the line. A zero at distance ν≥δ\nu\ge\delta from the line costs x(1−α)−(1−ε)νx^{(1-\alpha)-(1-\varepsilon)\nu}, there are at most T(30/13)ν=x(30/13)(1−θ+1/K)νT^{(30/13)\nu}=x^{(30/13)(1-\theta+1/K)\nu} of them, and the sum over zeros is small once K>K∗(θ,δ)K>K^*(\theta,\delta). The full proof is in Appendix § 9.

From smooth numbers to good curves.

Theorem 5 (Lenstra, Pila, Pomerance [17 Thm. 1.1]). Let p>8100p>8100 be prime. For all but at most pp integers zz in [p2−12p3/2,p2+12p3/2][p^2-\frac{1}{2}p^{3/2},p^2+\frac{1}{2}p^{3/2}] there are at least p9/2/(24000log⁡(p2)log⁡log⁡(p2))p^{9/2}/(24000\log(p^2)\log\log(p^2)) quintic polynomials f∈Fp[X]f\in\mathbb{F}_p[X] with non-zero discriminant such that #Jf(Fp)=z\#J_f(\mathbb{F}_p)=z.

Proposition 6. Let K0=25K_0=25, fix K≥K0K\ge K_0, and put x=p2−12p3/2x=p^2-\frac{1}{2}p^{3/2} and y=(log⁡x)Ky=(\log x)^K. For all sufficiently large primes pp, the interval (x,x+p3/2](x,x+p^{3/2}] contains Sp≥p3/2−2/K−o(1)>2pS_p\ge p^{3/2-2/K-o(1)}>2p integers that are yy-smooth, and there is a monic quintic f∈Fp[X]f\in\mathbb{F}_p[X] with non-zero discriminant such that #Jf(Fp)\#J_f(\mathbb{F}_p) is yy-smooth.

Proof. Apply Theorems 3 and 4 with δ=1/8\delta=1/8, θ=3/4\theta=3/4 and h=p3/2h=p^{3/2}; then x3/4<h≤xx^{3/4}<h\le x because x<p2x<p^2, and K>K∗=268/11K>K^*=268/11. By the estimate Ψ(x,(log⁡x)K)=x1−1/K+o(1)\Psi(x,(\log x)^K)=x^{1-1/K+o(1)} of Section 2 and x≤p2x\le p^2, Theorem 3 gives Sp≥13p3/2x−1/K−o(1)≥p3/2−2/K−o(1)S_p\ge\frac{1}{3}p^{3/2}x^{-1/K-o(1)}\ge p^{3/2-2/K-o(1)}, which exceeds 2p2p for large pp because K≥K0>4K\ge K_0>4. At most pp of these integers are exceptional in Theorem 5, so one of them is #Jf(Fp)\#J_f(\mathbb{F}_p) for some quintic ff, which can be made monic as in Section 2. □\square

We call a quintic f∈Fp[X]f\in\mathbb{F}_p[X], and its coefficient vector, good if its discriminant is non-zero and #Jf(Fp)\#J_f(\mathbb{F}_p) is yy-smooth.

The reduction

This section proves Theorem 1 from Proposition 6. Fix KK and y=(log⁡x)Ky=(\log x)^K with x=p2−12p3/2x=p^2-\frac{1}{2}p^{3/2} as in Proposition 6; note y≤(2ℓ)Ky\le(2\ell)^K. For the finitely many primes below the threshold of Proposition 6 the algorithm uses exhaustive search.

The advice

Let ff be a monic quintic with non-zero discriminant such that J=Jf(Fp)J = J_f(\mathbb{F}_p) has yy-smooth order NN. Write J=⨁i=14⟨Bi⟩J = \bigoplus_{i=1}^{4}\langle B_i\rangle with BiB_i of order nin_i and n1∣n2∣n3∣n4n_1 \mid n_2 \mid n_3 \mid n_4 (some nin_i may be 1), and let ξ\xi be a quadratic non-residue modulo pp. The advice is

σp=(f;(ui,vi)i≤4;n1,…,n4;ξ),\sigma_p = (f; (u_i,v_i)_{i\leq4}; n_1,\ldots,n_4; \xi),

where (ui,vi)(u_i,v_i) is the Mumford representation of BiB_i. It has at most 5ℓ+4(4ℓ+2)+4(2ℓ+1)+ℓ=30ℓ+125\ell+ 4(4\ell+ 2) + 4(2\ell+ 1) + \ell= 30\ell+ 12 bits and depends only on pp. From it the algorithm computes N=n1n2n3n4N = n_1n_2n_3n_4 and factors NN by trial division up to yy.

Step 1: putting the hidden element on the curve

This is Maurer’s embedding [18], as adapted to genus 2 by Wolf and by Koblitz, Menezes and Shparlinski [34, 14]. Given s(a)s(a), pick r∈Fpr \in\mathbb{F}_p at random, form s(a′)s(a') with a′=a+ra' = a + r, and compute s(w)s(w) for w=f(a′)w = f(a') and s(w(p−1)/2)s(w^{(p-1)/2}). If w=0w = 0 put b=0b = 0; if w(p−1)/2=1w^{(p-1)/2} = 1 compute s(b)s(b) with b2=wb^2 = w by Tonelli–Shanks with the explicit ξ\xi; otherwise pick a new rr. Now D=(X−a′,b)D = (X - a', b), held implicitly, is the reduced representation of [(a′,b)−∞]∈J[(a', b) - \infty] \in J.

The affine curve has p−tp - t points with ∣t∣≤4p|t| \leq4\sqrt{p} by Weil’s bound, so the number of rr with f(a+r)f(a + r) a square or zero is at least (p−4p)/2≥p/3(p - 4\sqrt{p})/2 \geq p/3 for p≥150p \geq150. Hence at most three trials are expected, each with O(ℓ)O(\ell) field operations, followed by one square root with O(ℓ2)O(\ell^2).

Step 2: Pohlig–Hellman with a hidden target

The core of the reduction is the following routine. It is the textbook digit-by-digit method written for a non-cyclic group whose basis is known explicitly while the target is known only implicitly.

Lemma 7. Let H=⨁i=1m⟨Ci⟩H = \bigoplus_{i=1}^{m}\langle C_i\rangle be a finite abelian qq-group with CiC_i of order qfiq^{f_i}, m≤4m \leq4 and f=max⁡ifif = \max_i f_i. Given the CiC_i explicitly and R∈HR \in H implicitly, one finds κi∈[0,qfi)\kappa_i \in[0, q^{f_i}) with R=∑iκiCiR = \sum_i \kappa_i C_i using O(f2log⁡q)O(f^2 \log q) operations on implicit elements, O(f2log⁡q+qm)O(f^2 \log q + q^m) operations on explicit elements, and at most fqmfq^m comparisons between an implicit and an explicit element.

Proof. Compute Rj=qjRR_j = q^jR for 0≤j≤f0 \leq j \leq f. We find, for j=f,f−1,…,0j = f, f - 1,\ldots,0, integers κi(j)∈[0,qmax⁡(fi−j,0))\kappa_i^{(j)} \in[0, q^{\max(f_i-j,0)}) with qjR=∑iκi(j)qjCiq^jR = \sum_i \kappa_i^{(j)}q^jC_i; for j=fj = f all are zero. Given the κi(j+1)\kappa_i^{(j+1)}, put Δ=Rj−∑iκi(j+1)qjCi\Delta= R_j - \sum_i \kappa_i^{(j+1)}q^jC_i. Then qΔ=0q\Delta= 0 and Δ∈qjH=⨁fi>j⟨qjCi⟩\Delta\in q^jH = \bigoplus_{f_i>j}\langle q^jC_i\rangle. The qq-torsion of the cyclic group ⟨qjCi⟩\langle q^jC_i\rangle is ⟨qfi−1Ci⟩\langle q^{f_i-1}C_i\rangle, so Δ=∑fi>jciqfi−1Ci\Delta= \sum_{f_i>j}c_iq^{f_i-1}C_i for a unique (ci)∈[0,q)m(c_i) \in[0,q)^m, which we find by comparing Δ\Delta with the at most qmq^m explicit candidates. Put κi(j)=κi(j+1)+ciqfi−1−j\kappa_i^{(j)} = \kappa_i^{(j+1)} + c_iq^{f_i-1-j} for fi>jf_i > j. Then κi(j)<qfi−j\kappa_i^{(j)} < q^{f_i-j} and ∑iκi(j)qjCi=(Rj−Δ)+Δ=Rj\sum_i \kappa_i^{(j)}q^jC_i = (R_j - \Delta) + \Delta= R_j. The candidate sets depend only on {i:fi>j}\{i : f_i > j\}, so at most m+1m + 1 of them are built.

Comparisons between an implicit and an explicit class are sound because reduced representations are unique.

For each prime q∣Nq \mid N with qe∣Nq^e \mid N, put Nq=N/qeN_q = N/q^e, compute Dq=NqDD_q = N_qD implicitly and Ci,q=NqBiC_{i,q} = N_qB_i explicitly. Since NqN_q is prime to qq, Ci,qC_{i,q} has order qvq(ni)q^{v_q(n_i)} and the qq-Sylow subgroup of JJ is ⨁i⟨Ci,q⟩\bigoplus_i\langle C_{i,q}\rangle. Lemma 7 gives κi,q\kappa_{i,q} with Dq=∑iκi,qCi,qD_q = \sum_i\kappa_{i,q}C_{i,q}.

Step 3: reading off the answer

By the Chinese remainder theorem take ki∈[0,ni)k_i \in[0,n_i) with ki≡κi,q(modqvq(ni))k_i \equiv\kappa_{i,q} \pmod{q^{v_q(n_i)}} for every qq, and compute E=∑ikiBiE = \sum_i k_iB_i explicitly. For every qq we have Nq(D−E)=Dq−∑ikiCi,q=0N_q(D-E)=D_q-\sum_i k_iC_{i,q}=0, so the order of D−ED-E divides gcd⁡qNq=1\gcd_q N_q=1 and E=DE=D. By uniqueness, E=(X−a′,b)E=(X-a',b); the algorithm reads off a′a' and outputs a=a′−ra=a'-r.

Running time

Step 1 costs O(ℓ2)O(\ell^2) field operations in expectation. In Step 2, ∑qeqlog⁡q=log⁡N≤2ℓ+1\sum_q e_q\log q=\log N\le2\ell+1, so all implicit Jacobian arithmetic takes O(ℓ2)O(\ell^2) group operations in JJ, hence O(ℓ2)O(\ell^2) field operations; the comparisons number at most ∑qeq4≤(2ℓ+1)y4\sum_q eq^4\le(2\ell+1)y^4, each needing O(1)O(1) explicit constants. Step 3 is explicit. Through Lemma 2 the total is O(ℓ2y4)O(\ell^2y^4) group operations and O(ℓ3)O(\ell^3) oracle calls, that is O(ℓ4K+3)O(\ell^{4K+3}). This proves Theorem 1.

Fewer advice bits, and none

The advice in Theorem 1 is only a pointer to one good curve. Good curves are not rare, which gives the three variants below.

Lemma 8. Let K≥K0K\ge K_0 and y=(log⁡x)Ky=(\log x)^K as in Proposition 6. For large pp, a uniformly random coefficient vector (a0,…,a5)∈Fp6(a_0,\ldots,a_5)\in\mathbb{F}_p^6 defines a quintic f=∑aiXif=\sum a_iX^i with non-zero discriminant and yy-smooth #Jf(Fp)\#J_f(\mathbb{F}_p) with probability at least p−2/K−o(1)p^{-2/K-o(1)}.

Proof. At least Sp−p≥Sp/2S_p-p\ge S_p/2 of the yy-smooth integers in the window avoid the exceptional set of Theorem 5, and each is the order of at least p9/2/(24000log⁡(p2)log⁡log⁡(p2))p^{9/2}/(24000\log(p^2)\log\log(p^2)) quintics; distinct orders give disjoint sets of quintics. Divide by p6p^6 and use Sp≥p3/2−2/K−o(1)S_p\ge p^{3/2-2/K-o(1)}.

Without advice the algorithm computes N=#Jf(Fp)N=\#J_f(\mathbb{F}_p) by Pila’s algorithm [28, 1] in time ℓO(1)\ell^{O(1)}, and a basis of Jf(Fp)J_f(\mathbb{F}_p) in time ℓO(1)y2\ell^{O(1)}y^2 from random elements (Appendix B).

Theorem 9 (Polynomial time with εℓ\varepsilon\ell yes/no queries). For every 0<ε≤10<\varepsilon\le1 there is cεc_\varepsilon such that, with at most εℓ\varepsilon\ell queries to an oracle answering arbitrary yes/no questions, discrete logarithms in groups of prime order pp are computed from a Diffie–Hellman oracle in expected time O(ℓcε)O(\ell^{c_\varepsilon}) with failure probability at most p−ε/2p^{-\varepsilon/2}.

Proof. Take K≥max⁡(K0,⌈8/ε⌉)K\ge\max(K_0,\lceil8/\varepsilon\rceil), so that a random coefficient vector is good with probability λp≥p−ε/4−o(1)\lambda_p\ge p^{-\varepsilon/4-o(1)} by Lemma 8. Following [14 §7] and Chor and Goldreich [6], identify Fp6\mathbb{F}_p^6 with Fp6\mathbb{F}_{p^6}, order it as w1,w2,…w_1,w_2,\ldots, draw s,t∈Fp6s,t\in\mathbb{F}_{p^6} and consider the pairwise independent samples swj+tsw_j+t, j≤M=2⌊εℓ⌋j\le M=2^{\lfloor\varepsilon\ell\rfloor}. By Chebyshev’s inequality none is good with probability at most 1/(Mλp)≤p−ε/21/(M\lambda_p)\le p^{-\varepsilon/2} for large pp. The oracle supplies the ⌊εℓ⌋\lfloor\varepsilon\ell\rfloor bits of the least good index. The algorithm then computes NN and a basis as above, and runs Steps 1–3 of Section 4 in time ℓO(K)\ell^{O(K)}.

Koblitz, Menezes and Shparlinski proved Theorem 9 under a conjecture on smooth numbers in short intervals [14 Thm. 5], and with time Lp(12)L_p(\frac{1}{2}) instead of polynomial under the Riemann Hypothesis [14 Thm. 4].

Corollary 10 (One precomputation per prime). For every ε>0\varepsilon>0 there is a uniform probabilistic algorithm in two phases. The first phase gets only pp, uses no group and no oracle, runs in expected time pεℓO(1)p^\varepsilon\ell^{O(1)} and outputs a string σp\sigma_p of O(ℓ)O(\ell) bits, which anyone can check in time ℓO(1/ε)\ell^{O(1/\varepsilon)}. The second phase, given σp\sigma_p, any group GG of order pp, a Diffie–Hellman oracle for it and gag^a, returns aa in expected time ℓO(1/ε)\ell^{O(1/\varepsilon)}.

Proof. Put K=max⁡(K0,⌈4/ε⌉)K=\max(K_0,\lceil4/\varepsilon\rceil). By Lemma 8 a random coefficient vector is good with probability at least p−ε/2−o(1)p^{-\varepsilon/2-o(1)}. The first phase draws vectors, computes #Jf(Fp)\#J_f(\mathbb{F}_p) by Pila’s algorithm and tests yy-smoothness by trial division, both in time ℓO(1)\ell^{O(1)} since y≤(2ℓ)Ky\le(2\ell)^K, until it succeeds; after pεp^\varepsilon failed draws it falls back to exhaustive search, which also covers the finitely many small primes. It then computes a basis and a non-residue as above and outputs σp\sigma_p. The second phase is Steps 1–3 of Section 4, in time ℓ4K+3\ell^{4K+3}.

Theorem 11 (No advice). A probabilistic algorithm with a Diffie–Hellman oracle computes discrete logarithms in groups of prime order pp with unique element encodings in expected time Lp(12,2)L_p(\frac{1}{2},2), and in time Lp(12,2)L_p(\frac{1}{2},\sqrt{2}) with batch smoothness testing.

Proof. Take y=exp⁡(c0log⁡plog⁡log⁡p)y=\exp(c_0\sqrt{\log p\log\log p}). Then ulog⁡u=(1/c0+o(1))log⁡plog⁡log⁡pu\log u=(1/c_0+o(1))\sqrt{\log p\log\log p}, and Theorem 3 together with Hildebrand’s Ψ(x,y)=xρ(u)(1+o(1))\Psi(x,y)=x\rho(u)(1+o(1)) [12] gives Sp≥p3/2ρ(u)1+o(1)S_p\ge p^{3/2}\rho(u)^{1+o(1)}, so a random coefficient vector is good with probability ρ(u)1+o(1)=Lp(12,1/c0)−1\rho(u)^{1+o(1)}=L_p(\frac{1}{2},1/c_0)^{-1}. Draw vectors until one is good, testing smoothness of #Jf(Fp)\#J_f(\mathbb{F}_p) by trial division in time yℓO(1)y\ell^{O(1)} per draw. Then compute NN and a basis in time ℓO(1)y2\ell^{O(1)}y^2 as above. Steps 1–3 with baby-step giant-step on each layer of Lemma 7 cost q2q^2 operations per layer, (2ℓ+1)y2(2\ell+1)y^2 in all. With c0=1c_0=1 the total is Lp(12,2)L_p(\frac{1}{2},2). A batch smoothness test [2] makes each draw cost ℓO(1)\ell^{O(1)} amortised; then the total is Lp(12,max⁡(1/c0,2c0))L_p(\frac{1}{2},\max(1/c_0,2c_0)), which is Lp(12,2)L_p(\frac{1}{2},\sqrt{2}) at c0=1/2c_0=1/\sqrt{2}.

Consequences

All reductions in this section are generic: in GG they use only the group operation, equality tests and the oracle, and their other computations do not depend on how GG is encoded.

Imperfect adversaries

A security proof turns an adversary that solves Diffie–Hellman on some fraction of inputs into a discrete-logarithm algorithm. Following Maurer and Wolf [23], call O\mathcal{O} an ε\varepsilon-Diffie–Hellman oracle for (G,g)(G,g) if its output distribution on a given input does not depend on earlier calls (it is time-invariant) and, on uniformly random input (gu,gv)(g^u,g^v), it returns guvg^{uv} with probability at least ε\varepsilon, over the input and its own coins. A fixed probabilistic algorithm run with fresh coins on each call is such an oracle.

Corollary 12. Let G=⟨g⟩G=\langle g\rangle have prime order pp and let O\mathcal{O} be an ε\varepsilon-Diffie–Hellman oracle for (G,g)(G,g). Given σp\sigma_p and ε\varepsilon, discrete logarithms in GG are computed with an expected O(ℓ3ε−4log⁡(ℓ/ε))O(\ell^3\varepsilon^{-4}\log(\ell/\varepsilon)) calls to O\mathcal{O} and poly⁡(ℓ,1/ε)\operatorname{poly}(\ell,1/\varepsilon) further operations.

Proof. For every cyclic group of known order and every β>0\beta>0, Maurer and Wolf [23 Thm. 1] build from O\mathcal{O} a Diffie–Hellman oracle that makes O(log⁡(1/(βε))/ε4)O(\log(1/(\beta\varepsilon))/\varepsilon^4) calls to O\mathcal{O} per query and answers each query correctly with probability at least $1-\beta$. The reduction of Theorem 1 makes O(ℓ3)O(\ell^3) oracle calls in expectation; by Markov’s inequality it makes at most T=O(ℓ3)T=O(\ell^3) calls with probability at least 5/65/6, and each round is stopped after TT calls. With β=1/(6T)\beta=1/(6T) all answers in a round are correct with probability at least 5/65/6, so a round succeeds with probability at least $2/3; the output aa is checked by computing gag^a, and the round is repeated on failure, at most 3/23/2 times in expectation.

A characterisation for cyclic groups

Let n≥2n \ge2 and let q(n)q(n) be the largest prime qq with q2∣nq^2 \mid n, or q(n)=1q(n) = 1 if nn is squarefree. Write GC⁡(n)\operatorname{GC}(n) for the least expected running time of a non-uniform generic reduction computing discrete logarithms from a Diffie–Hellman oracle in cyclic groups of order nn, in the sense of Wolf [34 §10.1].

Theorem 13. q(n)/2−1≤GC⁡(n)≤(log⁡n)O(1)(1+q(n))\sqrt{q(n)}/2 - 1 \le\operatorname{GC}(n) \le(\log n)^{O(1)}(1 + \sqrt{q(n)}). In particular discrete logarithm and Diffie–Hellman are non-uniformly generically polynomial-time equivalent in cyclic groups of order nn if and only if q(n)≤(log⁡n)O(1)q(n) \le(\log n)^{O(1)}.

Proof. Upper bound. The advice is the factorisation of nn and the strings σq\sigma_q for the primes q∥nq \mathrel{\|} n, O(log⁡n)O(\log n) bits in all. Pohlig–Hellman reduces discrete logarithms in GG to the subgroups of prime-power order. For q∥nq \mathrel{\|} n put h=gn/qh = g^{n/q}; then DH⁡g(ha,hb)=h(n/q)ab\operatorname{DH}_g(h^a,h^b) = h^{(n/q)ab}, and raising to (n/q)−1 mod q(n/q)^{-1} \bmod q gives a Diffie–Hellman oracle for ⟨h⟩\langle h\rangle, to which Theorem 1 applies with σq\sigma_q. For qe∥nq^e \mathrel{\|} n with e≥2e \ge2, each of the ee base-qq digits costs O(q)O(\sqrt{q}) by baby-step giant-step.

Lower bound. Maurer and Wolf [24], [34 Cor. 10.9]: every generic reduction of discrete logarithms to a Diffie–Hellman oracle in cyclic groups of order nn has expected running time at least q/2−1\sqrt{q}/2 - 1, where qq is the largest prime with q2∣nq^2 \mid n.

Wolf proved the equivalence statement [34 Thm. 10.10] under his Smoothness Assumption 1, which asks for elliptic curves of polylogarithmically smooth order over every prime field.

Black-box fields

The algorithms of Sections 4 and 5 are Fp\mathbb{F}_p-programs run on encodings (Section 2), so they solve extraction for black-box fields isomorphic to Fp\mathbb{F}_p with the same costs counted in field operations; Lemma 2 is only the translation back to groups. Maurer and Raub [19 Lemma 2] state this under “a (plausible) number-theoretic conjecture” and reduce the problems for extension fields to it. They prove the consequences below for small characteristic, and for large characteristic against non-uniform adversaries under the smoothness assumption of [18, 25].

Corollary 14. For every prime pp and every black-box field of characteristic pp and degree kk over Fp\mathbb{F}_p, the representation, extraction and isomorphism problems are solvable in time poly⁡(k,log⁡p)\operatorname{poly}(k, \log p) with O(log⁡p)O(\log p) bits of advice depending only on pp. Consequently, for finite fields whose characteristic is fixed by the security parameter or chosen by the adversary, there is no field-homomorphic one-way permutation, and no field-homomorphic encryption scheme that permits equality tests is one-way, against non-uniform polynomial-time adversaries; in the private-key case plaintexts are recovered up to field isomorphism.

Proof. Maurer and Raub [19 Thm. 1, Cor. 2–3] reduce these problems efficiently to the representation problem for Fp\mathbb{F}_p, which for Fp\mathbb{F}_p generated by 1 is extraction; the black-box field form of Theorem 1 above solves extraction with σp\sigma_p. For the second part, such a scheme instantiates a black-box field and extraction inverts it [19 Cor. 1, §4].

Limitations and conclusion

The reduction is non-uniform: the advice names a curve for each characteristic, so the characteristic must be fixed in advance, and finding a curve without advice costs p2/Kp^{2/K} trials, or subexponential time after optimising KK (Theorem 11). A uniform polynomial-time reduction would need an efficient construction of algebraic groups over Fp\mathbb{F}_p with polylogarithmically smooth order; Wolf conjectured that, for general group orders, this is as hard as factoring [34 Conj. 10.1]. The constants are very large: for δ=1/8\delta= 1/8 the smoothness exponent is K=25K = 25 and the polynomial has degree about 4K4K, so the result says nothing about concrete security at cryptographic sizes.

Discrete logarithm and Diffie–Hellman are equivalent in every group of prime order, given O(log⁡p)O(\log p) bits that depend only on pp. The obstacle was never the reduction but the distribution of smooth numbers, and a zero-free half-plane is enough to supply them.

Use of AI

The proof presented in this paper was developed through an interactive dialogue with Claude Fable 5.2 and Claude Opus 5.5 (Anthropic). The author used them to explore multiple possible proof strategies and directions, and the AI generated the initial draft under the author’s guidance. The author then critically examined the generated proof, verified each step for correctness and rigor, and revised it where necessary. The author takes full responsibility for the final content.

Proof of Theorem 3

Notation. L=log⁡xL = \log x, S=log⁡yS = \log y, u=L/Su = L/S, Zy(s)=ζ(s,y)=∏q≤y(1−q−s)−1Z_y(s) = \zeta(s,y) = \prod_{q \le y}(1-q^{-s})^{-1}, α=α(x,y)\alpha= \alpha(x,y) the saddle point, a0=1−αa_0 = 1-\alpha, W=xαZy(α)W = x^\alpha Z_y(\alpha), r=h/xr = h/x, and N(σ,T)=#{ρ=β+iγ:ζ(ρ)=0, β≥σ, ∣γ∣≤T}N(\sigma,T) = \#\{\rho= \beta+ i\gamma: \zeta(\rho) = 0,\ \beta\ge\sigma,\ |\gamma| \le T\}.

Inputs from the literature.

(I1) W≪Ψ(x,y)LSW \ll\Psi(x,y)\sqrt{LS} for log⁡x<y≤x\log x < y \le x [35 (1.3)].

(I2) a0S=log⁡(ulog⁡(u+1))+O(1)a_0S = \log(u\log(u+1)) + O(1) for log⁡x<y≤x\log x < y \le x [13 Lemma 2], [35 (1.5)]. Hence there are absolute constants 0<c∗≤C∗0 < c_* \le C_* with c∗ulog⁡(u+1)≤ya0≤C∗ulog⁡(u+1)c_*u\log(u+1) \le y^{a_0} \le C_*u\log(u+1) and a0S≤C∗log⁡(u+1)a_0S \le C_*\log(u+1), and a0S≥1a_0S \ge1 for uu large.

(I3) For fixed ϱ>0\varrho> 0, y≥y0(ϱ)y \ge y_0(\varrho) with log⁡x<y≤x\log x < y \le x, and 1/S<∣t∣≤exp⁡(S3/2−ϱ)1/S < |t| \le\exp(S^{3/2-\varrho}),

∣Zy(α+it)∣≤CϱZy(α)exp⁡(−c0ut2a02+t2)|Z_y(\alpha+it)| \le C_\varrho Z_y(\alpha)\exp\left(-c_0u\frac{t^2}{a_0^2+t^2}\right)

[13 Lemma 8], [35 (1.6)]; we use ϱ=1/10\varrho= 1/10.

(I4) For 2≤y,h,H≤x2 \le y,h,H \le x [35 (1.9)],

Ψ(x+h,y)−Ψ(x,y)=12πi∫α−iHα+iHZy(s)(x+h)s−xss ds+O(xL/H).\Psi(x+h,y)-\Psi(x,y)=\frac{1}{2\pi i}\int_{\alpha-iH}^{\alpha+iH}Z_y(s)\frac{(x+h)^s-x^s}{s}\,ds+O(xL/H).

(I5) With I0I_0 the segment from α−i/S\alpha-i/S to α+i/S\alpha+i/S [13 Lemma 12], [35 Lemma 3.6],

12πi∫I0Zy(s)xs ds=αΨ(x,y)(1+O(1u+Sy)),\frac{1}{2\pi i}\int_{I_0}Z_y(s)x^s\,ds=\alpha\Psi(x,y)\left(1+O\left(\frac{1}{u}+\frac{S}{y}\right)\right),

and the same bound holds for 12π∫I0∣Zy(s)xs∣ ∣ds∣\frac{1}{2\pi}\int_{I_0}|Z_y(s)x^s|\,|ds|. (I6) Let z≥2z \ge2, 0<e<1/100 < e < 1/10, 0<η≤1/20 < \eta\le1/2, and suppose ζ\zeta has no zeros in {Re⁡s>1−η,∣Im⁡s−t∣<10zη}\{\operatorname{Re} s > 1-\eta, |\operatorname{Im} s-t| < 10z^\eta\}. Then for s=a+it≠1s=a+it \ne1 with 1−(1−e)η≤a<1+1/log⁡z1-(1-e)\eta\le a < 1+1/\log z,

∣∑n≤zΛ(n)ns∣≤z1−a+1∣1−s∣+Oe((log⁡(∣t∣+2))b)+O((log⁡z)2z−eη)+Oe(((log⁡(∣t∣+zη+2))b+1η)log⁡(zη/η)z−eη/2).\left|\sum_{n \le z}\frac{\Lambda(n)}{n^s}\right| \le\frac{z^{1-a}+1}{|1-s|}+O_e\left((\log(|t|+2))^b\right)+O\left((\log z)^2z^{-e\eta}\right)+O_e\left(\left((\log(|t|+z^\eta+2))^b+\frac{1}{\eta}\right)\log(z^\eta/\eta)z^{-e\eta/2}\right).

with b=b(e)<1b=b(e)<1 and constants uniform in the other parameters [35 Lemma 2.3].

(I7) For every μ>0\mu>0, N(σ,T)≤CμT30(1−σ)/13+μN(\sigma,T)\le C_\mu T^{30(1-\sigma)/13+\mu} for $1/2\le \sigma\le 1$, T≥2T\ge2 [11 (1.4)]$.

Parameters. Fix δ\delta, θ\theta and K>K∗K>K^*. For small ε,ε1,μ,ε0>0\varepsilon,\varepsilon_1,\mu,\varepsilon_0>0 put τ=1−θ+1/K+ε1\tau=1-\theta+1/K+\varepsilon_1, g=(1−ε)2−ε0−3013τg=(1-\varepsilon)^2-\varepsilon_0-\frac{30}{13}\tau, ΞZ=δg−(1−ε)(1/K+ε1)−μ\Xi_Z=\delta g-(1-\varepsilon)(1/K+\varepsilon_1)-\mu and ΞR=θ−12−2K−2ε1−ε\Xi_R=\theta-\frac12-\frac{2}{K}-2\varepsilon_1-\varepsilon. At zero small parameters, ΞZ=[δ(30θ−17)−(13+30δ)/K]/13>0\Xi_Z=[\delta(30\theta-17)-(13+30\delta)/K]/13>0, which is K>K∗K>K^*, and ΞR=θ−12−2/K>0\Xi_R=\theta-\frac12-2/K>0 because K∗≥56/(30θ−17)>2/(θ−12)K^*\ge56/(30\theta-17)>2/(\theta-\frac12). Fix 0<ε0≤ε1≤ε<1/120<\varepsilon_0\le\varepsilon_1\le\varepsilon<1/12 and μ≤1/10\mu\le1/10 with ΞZ,ΞR>0\Xi_Z,\Xi_R>0, and put κ=12min⁡(ΞZ,ΞR,ε1/2)\kappa=\frac12\min(\Xi_Z,\Xi_R,\varepsilon_1/2). Then 1/K+ε1<(1−ε)δ1/K+\varepsilon_1<(1-\varepsilon)\delta. Let xx be large, xθ≤h≤xx^\theta\le h\le x, (log⁡x)K≤y≤xε0(\log x)^K\le y\le x^{\varepsilon_0}, and set H=x1+1/K+ε1/hH=x^{1+1/K+\varepsilon_1}/h, T=H+10yT=H+10\sqrt y, σR=(1+ε)/2\sigma_R=(1+\varepsilon)/2, D=D0/LD=D_0/L with D0=max⁡(8/ε,1/(c∗log⁡2))D_0=\max(8/\varepsilon,1/(c_*\log2)), t0=Dya0t_0=Dy^{a_0} and t∗=Dy(1−ε)/2t^*=Dy^{(1-\varepsilon)/2}. For large xx:

(P1) 0<a0≤1/K+ε1/20<a_0\le1/K+\varepsilon_1/2 (α\alpha increases with yy, and (I2) at y=(log⁡x)Ky=(\log x)^K);

(P2) S≤ε0LS\le\varepsilon_0L, x1/K+ε1≤H≤xx^{1/K+\varepsilon_1}\le H\le x, 2≤T≤11xτ2\le T\le11x^\tau;

(P3) Ψ(x,y)≥x1−a0/(CL)\Psi(x,y)\ge x^{1-a_0}/(CL) and W≤CΨ(x,y)LW\le C\Psi(x,y)L;

(P4) 1≤D0c∗log⁡(u+1)≤t0S≤D0C∗log⁡(u+1)1\le D_0c_*\log(u+1)\le t_0S\le D_0C_*\log(u+1);

(P5) a0<(1−ε)δa_0<(1-\varepsilon)\delta, hence α>σR\alpha>\sigma_R.

Lemma 15 (local shift for every yy). Fix 0<d≤1/20<d\le1/2 and 0<e<1/100<e<1/10. For x≥X0(d,e)x\ge X_0(d,e), every 2≤y≤x2\le y\le x and d≤η≤1/2d\le\eta\le1/2: let 1−(1−e)η≤σ1<σ2<1+1/log⁡y1-(1-e)\eta\le\sigma_1<\sigma_2<1+1/\log y and 0<∣t∣≤x0<|t|\le x, suppose ζ\zeta has no zeros in {Re⁡s>1−η,∣Im⁡s−t∣<10yη}\{\operatorname{Re}s>1-\eta,|\operatorname{Im}s-t|<10y^\eta\} and ∣t∣≥4eL(y1−σ1+1)|t|\ge\frac{4}{eL}(y^{1-\sigma_1}+1). Then

∣xσ1+itZy(σ1+it)∣≤x−(1−e)(σ2−σ1)∣xσ2+itZy(σ2+it)∣.|x^{\sigma_1+it}Z_y(\sigma_1+it)|\le x^{-(1-e)(\sigma_2-\sigma_1)}|x^{\sigma_2+it}Z_y(\sigma_2+it)|.

Proof. For σ1≤a≤σ2\sigma_1\le a\le\sigma_2 apply (I6) with z=yz=y. The first term is at most (y1−σ1+1)/∣t∣≤eL/4(y^{1-\sigma_1}+1)/|t|\le eL/4. The second is Oe((2L)b)O_e((2L)^b). The third is (log⁡y)2y−eη=w2e−eηw(\log y)^2y^{-e\eta}=w^2e^{-e\eta w} with w=log⁡yw=\log y, at most 4/(eηe)2≤4/(ed)24/(e\eta e)^2\le4/(ed)^2 for every y≥2y\ge2. In the fourth, log⁡(∣t∣+yη+2)≤2L\log(|t|+y^\eta+2)\le2L, 1/η≤1/d1/\eta\le1/d and log⁡(yη/η)y−eη/2≤2/(ee)+log⁡(1/d)\log(y^\eta/\eta)y^{-e\eta/2}\le2/(e e)+\log(1/d), so it is Od,e(Lb+1)O_{d,e}(L^b+1). As b<1b<1, the total is at most eL/2eL/2 for large xx. Since −Zy′/Zy(s)=∑n≤yΛ(n)n−s+Ry(s)-Z'_y/Z_y(s)=\sum_{n\le y}\Lambda(n)n^{-s}+R_y(s) with ∣Ry(s)∣≤∑q(log⁡q)q−2a/(1−q−a)=Oe(1)|R_y(s)|\le\sum_q(\log q)q^{-2a}/(1-q^{-a})=O_e(1) for a≥(1+e)/2a\ge(1+e)/2, we get ∣Zy′/Zy(a+it)∣≤eL|Z'_y/Z_y(a+it)|\le eL, and integrating ∂alog⁡∣Zy(a+it)∣\partial_a\log|Z_y(a+it)| from σ1\sigma_1 to σ2\sigma_2 gives the claim. □

The contour. Let ZT\mathcal Z_T be the zeros ρ=1−ν+iγ\rho=1-\nu+i\gamma with ν≤1/2\nu\le1/2 and ∣γ∣≤T|\gamma|\le T; by hypothesis ν≥δ\nu\ge\delta. For t∈Rt\in\mathbb R let σ0(t)=α\sigma_0(t)=\alpha for ∣t∣≤t0|t|\le t_0, σ0(t)=1−log⁡(∣t∣/D)/S\sigma_0(t)=1-\log(|t|/D)/S for t0≤∣t∣≤t∗t_0\le|t|\le t^* and σ0(t)=σR\sigma_0(t)=\sigma_R beyond; and for ρ∈ZT\rho\in\mathcal Z_T let σρ(t)=1−(1−ε)ν\sigma_\rho(t)=1-(1-\varepsilon)\nu for ∣t−γ∣≤10yν|t-\gamma|\le10y^\nu, σρ(t)=1−(1−ε)log⁡(∣t−γ∣/10)/S\sigma_\rho(t)=1-(1-\varepsilon)\log(|t-\gamma|/10)/S for 10yν≤∣t−γ∣≤10y10y^\nu\le|t-\gamma|\le10\sqrt y and σρ(t)=σR\sigma_\rho(t)=\sigma_R beyond. Put σΓ=max⁡(σ0,max⁡ρσρ)\sigma_\Gamma=\max(\sigma_0,\max_\rho\sigma_\rho), Γ={σΓ(t)+it:∣t∣≤H}\Gamma=\{\sigma_\Gamma(t)+it:|t|\le H\}, and let C±C_\pm be the horizontal segments from Γ\Gamma to α±iH\alpha\pm iH. By (P5), σρ≤1−(1−ε)δ<α\sigma_\rho\le1-(1-\varepsilon)\delta<\alpha, so σΓ≤α\sigma_\Gamma\le\alpha with equality exactly for ∣t∣≤t0|t|\le t_0; and t0≥1/St_0\ge1/S by (P4).

Lemma 16. For ∣t∣≤H|t| \le H and σΓ(t)≤σ<α\sigma_{\Gamma}(t) \le\sigma< \alpha:

∣xσ+itZy(σ+it)∣≤x−(1−ε)(α−σ)∣xα+itZy(α+it)∣≤x−(1−ε)(α−σ)W.|x^{\sigma+it}Z_y(\sigma+it)| \le x^{-(1-\varepsilon)(\alpha-\sigma)} \quad|x^{\alpha+it}Z_y(\alpha+it)| \le x^{-(1-\varepsilon)(\alpha-\sigma)}W.

Proof. Let η=max⁡(δ,(1−σ)/(1−ε))≤12\eta=\max(\delta,(1-\sigma)/(1-\varepsilon))\le\frac{1}{2}. No zero lies in {Re⁡s>1−η, ∣Im⁡s−t∣<10yη}\{\operatorname{Re}s>1-\eta,\ |\operatorname{Im}s-t|<10y^\eta\}: for η=δ\eta=\delta this is the hypothesis; otherwise such a zero would be in ZT\mathcal{Z}_T and would force σρ(t)>σ\sigma_\rho(t)>\sigma. Next, σ<α\sigma<\alpha forces ∣t∣>t0|t|>t_0, and then Dy1−σ≤∣t∣Dy^{1-\sigma}\le|t| from the definition of σ0\sigma_0 (using σ≥σR\sigma\ge\sigma_R beyond t∗t^*), so

∣t∣≥8εLy1−σ≥1εL(y1−σ+1).|t|\ge\frac{8}{\varepsilon L}y^{1-\sigma}\ge\frac{1}{\varepsilon L}(y^{1-\sigma}+1).

Lemma 15 with d=δd=\delta, e=εe=\varepsilon, σ1=σ\sigma_1=\sigma, σ2=α\sigma_2=\alpha gives the first inequality, and ∣Zy(α+it)∣≤Zy(α)|Z_y(\alpha+it)|\le Z_y(\alpha) the second.

For Re⁡s≤1\operatorname{Re}s\le1 one has ∣((x+h)s−xs)/s∣≤r∣xs∣|((x+h)^s-x^s)/s|\le r|x^s| and ∣((x+h)s−xs)/s−rxs∣≤12r2∣s−1∣∣xs∣|((x+h)^s-x^s)/s-rx^s|\le\frac{1}{2}r^2|s-1||x^s|; on C±C_\pm, ∣((x+h)s−xs)/s∣≤3∣xs∣/H|((x+h)^s-x^s)/s|\le3|x^s|/H.

Lemma 17 (zeros). ∑ρ∈ZT∫Γ∩Γρ∣xsZy(s)∣∣ds∣≤CWx−ΞZ≤CΨ(x,y)x−κ\sum_{\rho\in\mathcal{Z}_T}\int_{\Gamma\cap\Gamma_\rho}|x^sZ_y(s)||ds|\le CWx^{-\Xi_Z}\le C\Psi(x,y)x^{-\kappa}, where Γρ\Gamma_\rho is the part of the contour defined by σρ\sigma_\rho.

Proof. Let c1=(1−ε)2−S/L≥(1−ε)2−ε0c_1=(1-\varepsilon)^2-S/L\ge(1-\varepsilon)^2-\varepsilon_0. On the vertical piece (length 20yν20y^\nu), Lemma 16 gives at most 20Wx(1−ε)a0x−c1ν20Wx^{(1-\varepsilon)a_0}x^{-c_1\nu}. On the curved pieces, parametrised by v∈[ν,12]v\in[\nu,\frac{1}{2}] with ∣s′(v)∣≤11Syv|s'(v)|\le11Sy^v, the integral is at most 11(S/((1−ε)2L−S))Wx(1−ε)a0x−c1ν≤11Wx(1−ε)a0x−c1ν11(S/((1-\varepsilon)^2L-S))Wx^{(1-\varepsilon)a_0}x^{-c_1\nu}\le11Wx^{(1-\varepsilon)a_0}x^{-c_1\nu}. Group the zeros by m=⌊νL⌋≥⌊δL⌋=m0m=\lfloor\nu L\rfloor\ge\lfloor\delta L\rfloor=m_0. By (I7) and (P2) there are at most 121Cμx(30/13)τ(m+1)121C\mu x^{(30/13)\tau(m+1)} zeros with this mm, each contributing at most 42Wx(1−ε)a0e−c1m42Wx^{(1-\varepsilon)a_0}e^{-c_1m}. Since c1−3013τ≥g>0c_1-\frac{30}{13}\tau\ge g>0, the sum over m≥m0m\ge m_0 is ≤C(μ,g)Wx(1−ε)a0+μ−gδ≤CWx−ΞZ\le C(\mu,g)Wx^{(1-\varepsilon)a_0+\mu-g\delta}\le CWx^{-\Xi_Z} by (P1); finally W≤CΨLW\le C\Psi L.

Lemma 18 (remainder line and connectors). The part of Γ\Gamma on Re⁡s=σR\operatorname{Re}s=\sigma_R contributes at most 2Wx−ΞR≤CΨx−κ2Wx^{-\Xi_R}\le C\Psi x^{-\kappa}, and ∫C±∣xsZy(s)∣∣ds∣≤W/((1−ε)L)≤CΨ/u\int_{C_\pm}|x^sZ_y(s)||ds|\le W/((1-\varepsilon)L)\le C\Psi/\sqrt{u}.

Proof. On Re⁡s=σR\operatorname{Re}s=\sigma_R, Lemma 16 gives ∣xsZy∣≤Wx−(1−ε)(α−σR)|x^sZ_y|\le Wx^{-(1-\varepsilon)(\alpha-\sigma_R)} with (1−ε)(α−σR)≥12−ε−1K−ε1(1-\varepsilon)(\alpha-\sigma_R)\ge\frac{1}{2}-\varepsilon-\frac{1}{K}-\varepsilon_1, over length ≤2xτ\le2x^\tau; the exponent is −ΞR-\Xi_R. On C±C_\pm, ∫−∞αx−(1−ε)(α−σ)dσ=1/((1−ε)L)\int_{-\infty}^{\alpha}x^{-(1-\varepsilon)(\alpha-\sigma)}d\sigma=1/((1-\varepsilon)L), and W/L≤CΨS/LW/L\le C\Psi\sqrt{S/L} by (I1).

Lemma 19 (central tails and curves). Let Γ0±\Gamma_0^\pm be the exponential paths {1−v±iDyv:a0≤v≤(1−ε)/2}\{1-v\pm iDy^v:a_0\le v\le(1-\varepsilon)/2\}. Then

∫s=α+it1/S<∣t∣≤t0∣xsZy(s)∣∣ds∣+∫Γ∩Γ0±∣xsZy(s)∣∣ds∣≤CΨ(x,y)u.\int_{\substack{s=\alpha+it\\1/S<|t|\le t_0}}|x^sZ_y(s)||ds|+\int_{\Gamma\cap\Gamma_0^\pm}|x^sZ_y(s)||ds|\le C\frac{\Psi(x,y)}{u}.

Proof. For 1/S<∣t∣≤t01/S<|t|\le t_0, (I3) applies and t2/(a02+t2)≥c/(log⁡(u+1))2t^2/(a_0^2+t^2)\ge c/(\log(u+1))^2 by (I2), so with (P4) and (I1) the tail is at most CD0Ψulog⁡(u+1)e−cu/log⁡2(u+1)≤C′Ψ/uCD_0\Psi\sqrt{u}\log(u+1)e^{-cu/\log^2(u+1)}\le C'\Psi/u. On Γ0±\Gamma_0^\pm, ∣t∣≥t0|t|\ge t_0 gives t2/(a02+t2)≥ct^2/(a_0^2+t^2)\ge c and (I3) gives ∣Zy(α+it)∣≤Ce−cuZy(α)|Z_y(\alpha+it)|\le Ce^{-cu}Z_y(\alpha); combining this with the first inequality of Lemma 16 and ∣s′(v)∣≤2DSyv|s'(v)|\le2DSy^v the curves contribute at most CWe−cuD0log⁡(u+1)/L≤C′Ψ/uCWe^{-cu}D_0\log(u+1)/L\le C'\Psi/u.

Assembly. Let Γ′=Γ∖I0\Gamma'=\Gamma\setminus I_0. By (I4) and Cauchy’s theorem,

Ψ(x+h,y)−Ψ(x,y)=12πi(∫I0+∫Γ′+∫C−+∫C+)Zy(s)(x+h)s−xss ds+O(xLH).\Psi(x+h,y)-\Psi(x,y)=\frac{1}{2\pi i}\left(\int_{I_0}+\int_{\Gamma'}+\int_{C_-}+\int_{C_+}\right)Z_y(s)\frac{(x+h)^s-x^s}{s}\,ds+O\left(\frac{xL}{H}\right).

By (I5) in both forms and max⁡∣s−1∣≤a0+1/S\max|s-1|\le a_0+1/S on the central segment, the central part is αrΨ(1+O(1/u))+ϑ12r2(a0+1/S)αΨ(1+O(1/u))\alpha r\Psi(1+O(1/u))+\vartheta\frac{1}{2}r^2(a_0+1/S)\alpha\Psi(1+O(1/u)) with ∣ϑ∣≤1|\vartheta|\le1. Lemmas 17–19 bound the rest of Γ\Gamma by CrΨ(1/u+x−κ)Cr\Psi(1/u+x^{-\kappa}); the connectors give CrΨx−1/K−ε1/uCr\Psi x^{-1/K-\varepsilon_1}/\sqrt{u} since 1/H=rx−1/K−ε11/H=rx^{-1/K-\varepsilon_1}; and xL/H=rx1−1/K−ε1L≤CrΨL2xa0−1/K−ε1≤CrΨx−κxL/H = rx^{1-1/K-\varepsilon_1}L \le Cr\Psi L^2x^{a_0-1/K-\varepsilon_1} \le Cr\Psi x^{-\kappa} by (P1), (P3). Dividing by αrΨ\alpha r\Psi (with α≥12\alpha\ge\frac{1}{2} and x−κ≤1/ux^{-\kappa} \le1/u),

∣Ψ(x+h,y)−Ψ(x,y)αrΨ(x,y)−1∣≤C1u+r2(a0+1/S)(1+C1u).\left|\frac{\Psi(x+h,y)-\Psi(x,y)}{\alpha r\Psi(x,y)}-1\right| \le\frac{C_1}{u}+\frac{r}{2}(a_0+1/S)\left(1+\frac{C_1}{u}\right).

which gives (1) since a0+1/S≤(C∗+2)log⁡(u+1)/Sa_0+1/S \le(C_*+2)\log(u+1)/S. For the lower bound, a0+1/S≤1/K+ε1<12a_0+1/S \le1/K+\varepsilon_1 < \frac{1}{2}, so the right side is at most 12\frac{1}{2} once u≥5C1u \ge5C_1, which holds after decreasing ε0\varepsilon_0; and α≥1−1/K−ε1≥23\alpha\ge1-1/K-\varepsilon_1 \ge\frac{2}{3}.

Constants. For θ=3/4\theta=3/4 and δ=1/8\delta=1/8 one gets K∗=268/11<25K^*=268/11<25, the value K0=25K_0=25 of Proposition 6. The half-planes Re⁡s>11/12\operatorname{Re}s>11/12 [15] and Re⁡s>31/32\operatorname{Re}s>31/32 [7] give K0=34K_0=34 and K0=82K_0=82. With a zero-density exponent AA in place of Guth and Maynard’s 30/1330/13, the threshold is KA∗=(1+Aδ)/(δ(1−A(1−θ)))K_A^*=(1+A\delta)/(\delta(1-A(1-\theta))).

Under the Riemann Hypothesis. All zeros then lie on Re⁡s=12\operatorname{Re}s=\frac{1}{2}, every Γρ\Gamma_\rho lies on the remainder line, Lemma 17 is void, and only ΞR>0\Xi_R>0, (P5) and the Perron step are used: K>2/(θ−12)K>2/(\theta-\frac{1}{2}) suffices, that is K=9K=9 for θ=3/4\theta=3/4, which makes the constant of Younis [35 Thm. 1.3] explicit in this range.

Computing the group without advice

Let ff be a monic quintic with non-zero discriminant such that N=#Jf(Fp)N=\#J_f(\mathbb{F}_p) is yy-smooth, and factor NN by trial division up to yy. Draw a monic quadratic uu uniformly, let m(u)∈{0,1,2,4}m(u)\in\{0,1,2,4\} be the number of vv with deg⁡v≤1\deg v\le1 and v2≡f(modu)v^2\equiv f\pmod u (computed with square roots in Fp\mathbb{F}_p or Fp2\mathbb{F}_{p^2}), accept with probability m(u)/4m(u)/4 and output a uniform one of these vv. Every class with deg⁡u=2\deg u=2 is output with the same probability, and the remaining classes, at most p+4p+1p+4\sqrt{p}+1 of them, form an O(1/p)O(1/p) fraction of Jf(Fp)J_f(\mathbb{F}_p). Six such samples generate Jf(Fp)J_f(\mathbb{F}_p) with probability at least 0.29−O(1/p)0.29-O(1/p), by Pomerance’s bound for groups of rank at most four [29] as used in [14 §7]. Teske’s algorithm [33 Thm. 6.1], in the form of Sutherland [32 §1], turns them into a basis: for a qq-group of rank m≤4m\le4 it costs ℓO(1)qm/2≤ℓO(1)q2\ell^{O(1)}q^{m/2}\le\ell^{O(1)}q^2 group operations, so ℓO(1)y2\ell^{O(1)}y^2 in all; the algorithm checks that the basis has order NN, and draws again otherwise.

References

  1. [1]Leonard M. Adleman and Ming-Deh Huang. Counting points on curves and abelian varieties over finite fields. Journal of Symbolic Computation, 32(3):171–189, 2001.
  2. [2]Daniel J. Bernstein. How to find smooth parts of integers, 2004. Preprint.
  3. [3]Dan Boneh and Richard J. Lipton. Algorithms for black-box fields and their application to cryptography. In Advances in Cryptology – CRYPTO ’96, volume 1109 of LNCS, pages 283–297. Springer, 1996.
  4. [4]David G. Cantor. Computing in the Jacobian of a hyperelliptic curve. Mathematics of Computation, 48(177):95–101, 1987.DOI
  5. [5]E. Rodney Canfield, Paul Erdős, and Carl Pomerance. On a problem of Oppenheim concerning “factorisatio numerorum”. Journal of Number Theory, 17:1–28, 1983.DOI
  6. [6]Benny Chor and Oded Goldreich. On the power of two-point based sampling. Journal of Complexity, 5(1):96–106, 1989.DOI
  7. [7]Cureton and Thorner. Zero-free half-plane Re s > 31/32 for Dedekind zeta functions, 2026. Hexagon preprint 2610.00200, with Lean formalisation.
  8. [8]Nicolaas G. de Bruijn. On the number of positive integers ≤ x and free of prime factors > y. II. Indagationes Mathematicae, 28:239–247, 1966.
  9. [9]Bert den Boer. Diffie–Hellman is as strong as discrete log for certain primes. In Advances in Cryptology – CRYPTO ’88, volume 403 of LNCS, pages 530–539. Springer, 1990.DOI
  10. [10]Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976.
  11. [11]Larry Guth and James Maynard. New large value estimates for Dirichlet polynomials, 2024. arXiv:2405.20552.arxiv.org/abs/2405.20552
  12. [12]Adolf Hildebrand. On the number of positive integers ≤ x and free of prime factors > y. Journal of Number Theory, 22:289–307, 1986.DOI
  13. [13]Adolf Hildebrand and Gérald Tenenbaum. On integers free of large prime factors. Transactions of the American Mathematical Society, 296(1):265–290, 1986.DOI
  14. [14]Neal Koblitz, Alfred Menezes, and Igor Shparlinski. Discrete logarithms, Diffie–Hellman, and reductions. Vietnam Journal of Mathematics, 39(3):267–285, 2011. Also IACR ePrint 2010/577.
  15. [15]Alex Kontorovich. Lean formalisation and exposition of the zero-free half-plane Re s > 11/12, 2026. GitHub repository AlexKontorovich/quasi-rh.
  16. [16]Hendrik W. Lenstra, Jr., Jonathan Pila, and Carl Pomerance. A hyperelliptic smoothness test. I. Philosophical Transactions of the Royal Society of London, Series A, 345:397–408, 1993.
  17. [17]Hendrik W. Lenstra, Jr., Jonathan Pila, and Carl Pomerance. A hyperelliptic smoothness test. II. Proceedings of the London Mathematical Society, 84(1):105–146, 2002.DOI
  18. [18]Ueli M. Maurer. Towards the equivalence of breaking the Diffie–Hellman protocol and computing discrete logarithms. In Advances in Cryptology – CRYPTO ’94, volume 839 of LNCS, pages 271–281. Springer, 1994.
  19. [19]Ueli Maurer and Dominik Raub. Black-box extension fields and the inexistence of field-homomorphic one-way permutations. In Advances in Cryptology – ASIACRYPT 2007, volume 4833 of LNCS, pages 427–443. Springer, 2007.
  20. [21]Alexander May and Carl Richard Theodor Schneider. Dlog is practically as hard (or easy) as DH – solving Dlogs via DH oracles on EC standards. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(4):146–166, 2023.DOI
  21. [22][Mum70] David Mumford. Abelian Varieties, volume 5 of Tata Institute of Fundamental Research Studies in Mathematics. Oxford University Press, 1970.
  22. [23][MW96] Ueli M. Maurer and Stefan Wolf. Diffie–Hellman oracles. In Advances in Cryptology – CRYPTO ’96, volume 1109 of LNCS, pages 268–282. Springer, 1996.DOI
  23. [24][MW98] Ueli M. Maurer and Stefan Wolf. Lower bounds on generic algorithms in groups. In Advances in Cryptology – EUROCRYPT ’98, volume 1403 of LNCS, pages 72–84. Springer, 1998.
  24. [25][MW99] Ueli M. Maurer and Stefan Wolf. The relationship between breaking the Diffie–Hellman protocol and computing discrete logarithms. SIAM Journal on Computing, 28(5):1689–1721, 1999.DOI
  25. [26][MW00] Ueli M. Maurer and Stefan Wolf. The Diffie–Hellman protocol. Designs, Codes and Cryptography, 19:147–171, 2000.
  26. [27][Ope26] OpenAI. The quasi-Riemann hypothesis: a zero-free half-plane Re s > 7/8, 2026. Preprint dated 30 September 2026, item 003 of https://github.com/openai/math, with Lean formalisation.
  27. [28][Pil90] Jonathan Pila. Frobenius maps of abelian varieties and finding roots of unity in finite fields. Mathematics of Computation, 55(192):745–763, 1990.DOI
  28. [29][Pom01] Carl Pomerance. The expected number of random elements to generate a finite abelian group. Periodica Mathematica Hungarica, 43:191–198, 2001.DOI
  29. [30][Sha73] Daniel Shanks. Five number-theoretic algorithms. In Proceedings of the Second Manitoba Conference on Numerical Mathematics, pages 51–70, 1973.
  30. [31][Sou10] Kannan Soundararajan. Smooth numbers in short intervals, 2010. arXiv:1009.1591.arxiv.org/abs/1009.1591
  31. [32][Sut11] Andrew V. Sutherland. Structure computation and discrete logarithms in finite abelian p-groups. Mathematics of Computation, 80:477–500, 2011. arXiv:0809.3413.DOI
  32. [33][Tes99] Edlyn Teske. The Pohlig–Hellman method generalized for group structure computation. Journal of Symbolic Computation, 27(6):521–534, 1999.DOI
  33. [34][Wol99] Stefan Wolf. Information-Theoretically and Computationally Secure Key Agreement in Cryptography. PhD thesis, ETH Zürich, 1999. Diss. ETH No. 13138.DOI
  34. [35][You24] Khalid Younis. Asymptotics for smooth numbers in short intervals, 2024. arXiv:2409.05761.arxiv.org/abs/2409.05761
  35. [36][Zha26] Liang Zhang. Square-root logarithmic bounds for the arithmetic complexity of factorial multiples, 2026. arXiv:2610.36588.arxiv.org/abs/2610.36588
  36. [37][Zho26] Yuwen Zhou. From two thirds to one half: proving the predicted running time of the hyperelliptic curve method, 2026. Companion paper, https://github.com/OctopusTide/hyperelliptic-curve-method.

Paper details

vlnc:W_yrgenqta
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Fable 5.2, Claude Opus 5.5

View statement
Looking for related papers…
Contents