New bounds limit polynomial approximations of the discrete logarithm
Original title: Bounds on polynomial approximations of the discrete logarithm function
The degree-at-most-D agreement set is at most (1+o(1)) times the square root of Dp, and linear polynomials fall to O(p to the 2/5).
A paper improves Coppersmith and Shparlinski bounds on how well polynomials approximate the discrete logarithm over a finite field. For every degree bound D, the number of agreements is at most (1+o(1)) times the square root of Dp, including nontrivial bounds when D exceeds p/2. For degree 1, the bound improves from O of the square root of p to O(p to the 2/5) via sum-product estimates. Related vanishing bounds for bivariate polynomials are tightened toward a Johnson-bound analogue.
- The prior univariate bound was at most the square root of 2Dp.
- The new bound remains nontrivial even for D greater than p/2.
- The degree-1 improvement uses the sum-product phenomenon.
- Proofs connect the problem to list-decoding and the Johnson bound.
From the original article
1 min read at arxiv.orgWe revisit a classical result of Coppersmith and Shparlinski showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $deg(f) \leq D$, we have: $$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 D p}.
By Swastik Kopparty · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.