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 there is an advice string of bits, depending only on , with which discrete logarithms in every group of order 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 -smooth integers in every interval with . With smoothness this small the saddle point of the counting integral lies just to the left of the line , and a zero-free strip of any fixed width absorbs the shift once 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 and in a cyclic group, compute . What cryptographers actually believe hard in the groups they deploy is the discrete logarithm problem: given , compute . 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 can be treated as an element of a field one can compute with but cannot read. Put into an auxiliary algebraic group over whose order has only small prime factors, solve the discrete logarithm there by Pohlig–Hellman, and read back. Everything works once such an auxiliary group exists. Maurer used elliptic curves, whose orders fill the interval , 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 [34, 26]. Under the Riemann Hypothesis, Koblitz, Menezes and Shparlinski [14] reached with the help of 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 .
The missing input. Genus-2 Jacobians widen the window. Their orders over fill , an interval of the form , and Lenstra, Pila and Pomerance [17] showed that all but at most integers there are such orders. Elliptic curves give only intervals of the form . What is needed is more than integers in that window whose prime factors are all at most . Unconditional methods give smooth numbers in only for smoothness bounds , because they rely on the Vinogradov–Korobov zero-free region. Younis recently reached under the Riemann Hypothesis [35].
A zero-free half-plane suffices. We prove that any half-plane free of zeros of is enough (Theorem 3): for every and every fixed above a threshold depending on and , the number of -smooth integers in , , is asymptotic to the count predicted by the density of -smooth integers near whenever . This range contains the genus-2 window, , but not the elliptic-curve window, . Such a half-plane, with , is now known [27], so our results are unconditional. The count is a contour integral of , which one shifts to the left of the saddle point . A zero of at distance from the line costs a factor , the half-plane guarantees , and the zero-density estimate of Guth and Maynard [11] bounds how many zeros there are. Polylogarithmic smoothness moves the saddle point only about from the line, and the strip absorbs this once is large in terms of . Earlier arguments placed the saddle point deep inside the zero-free region, which forced much larger [36]; what lets it leave that region is a local shift bound that holds for every (Lemma 15 in Appendix § 9).
Results. With this input, Maurer’s method goes through with genus-2 Jacobians.
Theorem 1. There are a constant and a probabilistic algorithm with the following property. For every prime there is an advice string of at most bits such that for every cyclic group of order , every generator and every , the algorithm given , , and a Diffie–Hellman oracle for outputs in expected time .
The advice depends only on : one string serves every group of order , 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 of inputs yields discrete logarithms in time (Corollary 12).
A complete characterisation. In cyclic groups of order , the generic non-uniform complexity of computing discrete logarithms from a Diffie–Hellman oracle lies between and , where is the largest prime with (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 yes/no queries instead of advice the reduction is still polynomial (Theorem 9); with a one-time precomputation of steps per prime it costs per instance (Corollary 10); with no help at all it takes (Theorem 11).
Contributions.
A theorem on smooth numbers. A zero-free half-plane for 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 .
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: represents , the group operation adds, the oracle multiplies, and inversion is exponentiation by . The advice names a genus-2 curve whose Jacobian has -smooth order, together with a basis of . The algorithm shifts by a random until is a square, takes an implicit square root, and so holds the point of the curve, hence the class , 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 in the basis; the explicit representation of then shows . § 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 with 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 . Our reduction is the classical one; what is new is the proof that the auxiliary groups exist.
Preliminaries
Groups and oracles. Throughout, is a prime and . A group of order with generator is given by encodings of its elements together with algorithms (or oracles) for the group operation, inversion and equality. The Diffie–Hellman oracle for maps to . The discrete logarithm problem asks for given . Running times count group operations, oracle calls and bit operations. An advice string for is a bit string that may depend on but not on the group, the generator or the instance. We write .
Black-box fields. Following Boneh and Lipton [3] and Maurer and Raub [19], a black-box field isomorphic to is an unknown injective encoding together with oracles that return , and (for ) from and ; the encodings and are given, and equality of field elements is equality of encodings. The extraction problem asks for given . For an explicit one computes from with additions.
Lemma 2 (Diffie–Hellman oracles implement black-box fields [18, 3, 19]). Let have order and put . Then addition, subtraction and equality are the group operation, inversion and equality of ; multiplication is one call to the Diffie–Hellman oracle; and inversion, , takes at most oracle calls. In particular, an algorithm that solves extraction for black-box fields isomorphic to with field operations solves the discrete logarithm problem in every group of order with group operations and oracle calls.
An -program with equality tests computes on field elements (explicit constants and one hidden input ) with , , , 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 is given only as : replace every datum by , 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 is -smooth if all its prime factors are at most , and . We write , and for the saddle point, the minimising with [13]. For fixed one has [8, 5].
Genus-2 Jacobians. For a squarefree quintic , the equation defines a curve of genus 2 with one point at infinity; denotes its Jacobian. Every class in has a unique reduced Mumford representation : , monic, , and [4]. An affine point gives the class with representation . Cantor’s algorithm adds two reduced representations with field operations, among them inversions. The group has order in and is a product of at most four cyclic groups, since for every prime the -torsion of has rank at most 4 [22]. If has leading coefficient , then is monic and is an isomorphism over , so we may take monic.
Smooth numbers in short intervals
Theorem 3. Let and suppose for . Let and
There are , and , depending only on , such that for all , and ,
and in particular .
Theorem 3 also gives the hyperelliptic curve method of Lenstra, Pila and Pomerance a proved running time for splitting an integer whose least prime factor is [37].
We apply Theorem 3 with the half-plane of [27]:
Theorem 4 ([27]). for .
Any fixed suffices for every result in this paper; only the smoothness exponent , and hence the degree of the polynomial in Theorem 1, depends on it.
How the proof goes. Perron’s formula writes as over a vertical segment through the saddle point , with height . As in Younis [35] and Zhang [36], the segment is moved onto a contour that stays on near the real axis, bends left along an exponential path, wraps around each zero of at a distance proportional to its distance from the line , and otherwise runs along for a small fixed . The integrand is holomorphic in . The central part gives the main term by the saddle-point method of Hildebrand and Tenenbaum [13]. Elsewhere one needs a saving over , and it comes from moving left: as long as no zero is near, drops by when drops from to (Lemma 15). This local shift holds for every . Earlier versions required or a saddle point within of the line ; without these conditions can be polylogarithmic, and then the saddle point sits about from the line. A zero at distance from the line costs , there are at most of them, and the sum over zeros is small once . The full proof is in Appendix § 9.
From smooth numbers to good curves.
Theorem 5 (Lenstra, Pila, Pomerance [17 Thm. 1.1]). Let be prime. For all but at most integers in there are at least quintic polynomials with non-zero discriminant such that .
Proposition 6. Let , fix , and put and . For all sufficiently large primes , the interval contains integers that are -smooth, and there is a monic quintic with non-zero discriminant such that is -smooth.
Proof. Apply Theorems 3 and 4 with , and ; then because , and . By the estimate of Section 2 and , Theorem 3 gives , which exceeds for large because . At most of these integers are exceptional in Theorem 5, so one of them is for some quintic , which can be made monic as in Section 2.
We call a quintic , and its coefficient vector, good if its discriminant is non-zero and is -smooth.
The reduction
This section proves Theorem 1 from Proposition 6. Fix and with as in Proposition 6; note . For the finitely many primes below the threshold of Proposition 6 the algorithm uses exhaustive search.
The advice
Let be a monic quintic with non-zero discriminant such that has -smooth order . Write with of order and (some may be 1), and let be a quadratic non-residue modulo . The advice is
where is the Mumford representation of . It has at most bits and depends only on . From it the algorithm computes and factors by trial division up to .
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 , pick at random, form with , and compute for and . If put ; if compute with by Tonelli–Shanks with the explicit ; otherwise pick a new . Now , held implicitly, is the reduced representation of .
The affine curve has points with by Weil’s bound, so the number of with a square or zero is at least for . Hence at most three trials are expected, each with field operations, followed by one square root with .
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 be a finite abelian -group with of order , and . Given the explicitly and implicitly, one finds with using operations on implicit elements, operations on explicit elements, and at most comparisons between an implicit and an explicit element.
Proof. Compute for . We find, for , integers with ; for all are zero. Given the , put . Then and . The -torsion of the cyclic group is , so for a unique , which we find by comparing with the at most explicit candidates. Put for . Then and . The candidate sets depend only on , so at most of them are built.
Comparisons between an implicit and an explicit class are sound because reduced representations are unique.
For each prime with , put , compute implicitly and explicitly. Since is prime to , has order and the -Sylow subgroup of is . Lemma 7 gives with .
Step 3: reading off the answer
By the Chinese remainder theorem take with for every , and compute explicitly. For every we have , so the order of divides and . By uniqueness, ; the algorithm reads off and outputs .
Running time
Step 1 costs field operations in expectation. In Step 2, , so all implicit Jacobian arithmetic takes group operations in , hence field operations; the comparisons number at most , each needing explicit constants. Step 3 is explicit. Through Lemma 2 the total is group operations and oracle calls, that is . 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 and as in Proposition 6. For large , a uniformly random coefficient vector defines a quintic with non-zero discriminant and -smooth with probability at least .
Proof. At least of the -smooth integers in the window avoid the exceptional set of Theorem 5, and each is the order of at least quintics; distinct orders give disjoint sets of quintics. Divide by and use .
Without advice the algorithm computes by Pila’s algorithm [28, 1] in time , and a basis of in time from random elements (Appendix B).
Theorem 9 (Polynomial time with yes/no queries). For every there is such that, with at most queries to an oracle answering arbitrary yes/no questions, discrete logarithms in groups of prime order are computed from a Diffie–Hellman oracle in expected time with failure probability at most .
Proof. Take , so that a random coefficient vector is good with probability by Lemma 8. Following [14 §7] and Chor and Goldreich [6], identify with , order it as , draw and consider the pairwise independent samples , . By Chebyshev’s inequality none is good with probability at most for large . The oracle supplies the bits of the least good index. The algorithm then computes and a basis as above, and runs Steps 1–3 of Section 4 in time .
Koblitz, Menezes and Shparlinski proved Theorem 9 under a conjecture on smooth numbers in short intervals [14 Thm. 5], and with time instead of polynomial under the Riemann Hypothesis [14 Thm. 4].
Corollary 10 (One precomputation per prime). For every there is a uniform probabilistic algorithm in two phases. The first phase gets only , uses no group and no oracle, runs in expected time and outputs a string of bits, which anyone can check in time . The second phase, given , any group of order , a Diffie–Hellman oracle for it and , returns in expected time .
Proof. Put . By Lemma 8 a random coefficient vector is good with probability at least . The first phase draws vectors, computes by Pila’s algorithm and tests -smoothness by trial division, both in time since , until it succeeds; after 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 . The second phase is Steps 1–3 of Section 4, in time .
Theorem 11 (No advice). A probabilistic algorithm with a Diffie–Hellman oracle computes discrete logarithms in groups of prime order with unique element encodings in expected time , and in time with batch smoothness testing.
Proof. Take . Then , and Theorem 3 together with Hildebrand’s [12] gives , so a random coefficient vector is good with probability . Draw vectors until one is good, testing smoothness of by trial division in time per draw. Then compute and a basis in time as above. Steps 1–3 with baby-step giant-step on each layer of Lemma 7 cost operations per layer, in all. With the total is . A batch smoothness test [2] makes each draw cost amortised; then the total is , which is at .
Consequences
All reductions in this section are generic: in they use only the group operation, equality tests and the oracle, and their other computations do not depend on how 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 an -Diffie–Hellman oracle for if its output distribution on a given input does not depend on earlier calls (it is time-invariant) and, on uniformly random input , it returns with probability at least , 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 have prime order and let be an -Diffie–Hellman oracle for . Given and , discrete logarithms in are computed with an expected calls to and further operations.
Proof. For every cyclic group of known order and every , Maurer and Wolf [23 Thm. 1] build from a Diffie–Hellman oracle that makes calls to per query and answers each query correctly with probability at least $1-\beta$. The reduction of Theorem 1 makes oracle calls in expectation; by Markov’s inequality it makes at most calls with probability at least , and each round is stopped after calls. With all answers in a round are correct with probability at least , so a round succeeds with probability at least $2/3; the output is checked by computing , and the round is repeated on failure, at most times in expectation.
A characterisation for cyclic groups
Let and let be the largest prime with , or if is squarefree. Write 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 , in the sense of Wolf [34 §10.1].
Theorem 13. . In particular discrete logarithm and Diffie–Hellman are non-uniformly generically polynomial-time equivalent in cyclic groups of order if and only if .
Proof. Upper bound. The advice is the factorisation of and the strings for the primes , bits in all. Pohlig–Hellman reduces discrete logarithms in to the subgroups of prime-power order. For put ; then , and raising to gives a Diffie–Hellman oracle for , to which Theorem 1 applies with . For with , each of the base- digits costs 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 has expected running time at least , where is the largest prime with .
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 -programs run on encodings (Section 2), so they solve extraction for black-box fields isomorphic to 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 and every black-box field of characteristic and degree over , the representation, extraction and isomorphism problems are solvable in time with bits of advice depending only on . 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 , which for generated by 1 is extraction; the black-box field form of Theorem 1 above solves extraction with . 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 trials, or subexponential time after optimising (Theorem 11). A uniform polynomial-time reduction would need an efficient construction of algebraic groups over 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 the smoothness exponent is and the polynomial has degree about , 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 bits that depend only on . 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. , , , , the saddle point, , , , and .
Inputs from the literature.
(I1) for [35 (1.3)].
(I2) for [13 Lemma 2], [35 (1.5)]. Hence there are absolute constants with and , and for large.
(I3) For fixed , with , and ,
[13 Lemma 8], [35 (1.6)]; we use .
(I4) For [35 (1.9)],
(I5) With the segment from to [13 Lemma 12], [35 Lemma 3.6],
and the same bound holds for . (I6) Let , , , and suppose has no zeros in . Then for with ,
with and constants uniform in the other parameters [35 Lemma 2.3].
(I7) For every , for $1/2\le \sigma\le 1$, [11 (1.4)]$.
Parameters. Fix , and . For small put , , and . At zero small parameters, , which is , and because . Fix and with , and put . Then . Let be large, , , and set , , , with , and . For large :
(P1) ( increases with , and (I2) at );
(P2) , , ;
(P3) and ;
(P4) ;
(P5) , hence .
Lemma 15 (local shift for every ). Fix and . For , every and : let and , suppose has no zeros in and . Then
Proof. For apply (I6) with . The first term is at most . The second is . The third is with , at most for every . In the fourth, , and , so it is . As , the total is at most for large . Since with for , we get , and integrating from to gives the claim. □
The contour. Let be the zeros with and ; by hypothesis . For let for , for and beyond; and for let for , for and beyond. Put , , and let be the horizontal segments from to . By (P5), , so with equality exactly for ; and by (P4).
Lemma 16. For and :
Proof. Let . No zero lies in : for this is the hypothesis; otherwise such a zero would be in and would force . Next, forces , and then from the definition of (using beyond ), so
Lemma 15 with , , , gives the first inequality, and the second.
For one has and ; on , .
Lemma 17 (zeros). , where is the part of the contour defined by .
Proof. Let . On the vertical piece (length ), Lemma 16 gives at most . On the curved pieces, parametrised by with , the integral is at most . Group the zeros by . By (I7) and (P2) there are at most zeros with this , each contributing at most . Since , the sum over is by (P1); finally .
Lemma 18 (remainder line and connectors). The part of on contributes at most , and .
Proof. On , Lemma 16 gives with , over length ; the exponent is . On , , and by (I1).
Lemma 19 (central tails and curves). Let be the exponential paths . Then
Proof. For , (I3) applies and by (I2), so with (P4) and (I1) the tail is at most . On , gives and (I3) gives ; combining this with the first inequality of Lemma 16 and the curves contribute at most .
Assembly. Let . By (I4) and Cauchy’s theorem,
By (I5) in both forms and on the central segment, the central part is with . Lemmas 17–19 bound the rest of by ; the connectors give since ; and by (P1), (P3). Dividing by (with and ),
which gives (1) since . For the lower bound, , so the right side is at most once , which holds after decreasing ; and .
Constants. For and one gets , the value of Proposition 6. The half-planes [15] and [7] give and . With a zero-density exponent in place of Guth and Maynard’s , the threshold is .
Under the Riemann Hypothesis. All zeros then lie on , every lies on the remainder line, Lemma 17 is void, and only , (P5) and the Perron step are used: suffices, that is for , which makes the constant of Younis [35 Thm. 1.3] explicit in this range.
Computing the group without advice
Let be a monic quintic with non-zero discriminant such that is -smooth, and factor by trial division up to . Draw a monic quadratic uniformly, let be the number of with and (computed with square roots in or ), accept with probability and output a uniform one of these . Every class with is output with the same probability, and the remaining classes, at most of them, form an fraction of . Six such samples generate with probability at least , 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 -group of rank it costs group operations, so in all; the algorithm checks that the basis has order , and draws again otherwise.
References
- [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]Daniel J. Bernstein. How to find smooth parts of integers, 2004. Preprint.
- [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]David G. Cantor. Computing in the Jacobian of a hyperelliptic curve. Mathematics of Computation, 48(177):95–101, 1987.DOI
- [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]Benny Chor and Oded Goldreich. On the power of two-point based sampling. Journal of Complexity, 5(1):96–106, 1989.DOI
- [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]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]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]Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976.
- [11]Larry Guth and James Maynard. New large value estimates for Dirichlet polynomials, 2024. arXiv:2405.20552.arxiv.org/abs/2405.20552
- [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]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]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]Alex Kontorovich. Lean formalisation and exposition of the zero-free half-plane Re s > 11/12, 2026. GitHub repository AlexKontorovich/quasi-rh.
- [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]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]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]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.
- [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
- [22][Mum70] David Mumford. Abelian Varieties, volume 5 of Tata Institute of Fundamental Research Studies in Mathematics. Oxford University Press, 1970.
- [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
- [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.
- [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
- [26][MW00] Ueli M. Maurer and Stefan Wolf. The Diffie–Hellman protocol. Designs, Codes and Cryptography, 19:147–171, 2000.
- [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.
- [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
- [29][Pom01] Carl Pomerance. The expected number of random elements to generate a finite abelian group. Periodica Mathematica Hungarica, 43:191–198, 2001.DOI
- [30][Sha73] Daniel Shanks. Five number-theoretic algorithms. In Proceedings of the Second Manitoba Conference on Numerical Mathematics, pages 51–70, 1973.
- [31][Sou10] Kannan Soundararajan. Smooth numbers in short intervals, 2010. arXiv:1009.1591.arxiv.org/abs/1009.1591
- [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
- [33][Tes99] Edlyn Teske. The Pohlig–Hellman method generalized for group structure computation. Journal of Symbolic Computation, 27(6):521–534, 1999.DOI
- [34][Wol99] Stefan Wolf. Information-Theoretically and Computationally Secure Key Agreement in Cryptography. PhD thesis, ETH Zürich, 1999. Diss. ETH No. 13138.DOI
- [35][You24] Khalid Younis. Asymptotics for smooth numbers in short intervals, 2024. arXiv:2409.05761.arxiv.org/abs/2409.05761
- [36][Zha26] Liang Zhang. Square-root logarithmic bounds for the arithmetic complexity of factorial multiples, 2026. arXiv:2610.36588.arxiv.org/abs/2610.36588
- [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.