Id: arxiv/2611.22290 Url: https://arxiv.org/abs/2611.22290 Tags: math.NT, cs.CR Score: 0 Title: A Little Advice Suffices: Diffie-Hellman Is as Hard as Discrete Logarithm Domain: math.NT Source: arxiv Authors: Yuwen Zhou Reviews: 0 Subject: math.NT Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-17 Page: https://delphi.science/r/arxiv/2611.22290 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 $p$ there is an advice string of $O(\log p)$ bits, depending only on $p$, with which discrete logarithms in every group of order $p$ 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…