Reconstructing points of superelliptic curves over a prime finite field (Q6089463)

Let \(p\) be a prime and \(\Delta\) an integer with \(p > \Delta \geq 1\). If \((v_0, v_1) \in \mathbb{F}_p^2\), then we call a pair \((w_0, w_1)\in \mathbb{Z}^2\) a \(\Delta\)-approximation to \((v_0, v_1)\) if there exist integers \(\varepsilon_0\), \(\varepsilon_1\) satisfying: \[ |\varepsilon_0|, |\varepsilon_1| \leq \Delta,\ \ \ w_0 + \varepsilon_0 = v_0, \ \ \ w_1 + \varepsilon_1 = v_1. \] Let \(H_{(n,m,f)}(X,Y) = Y^n-f(X)\), where \(f(x)\in \mathbb{F}_p[x]\) is a monic univariate polynomial of degree \(m\), and \(mn> 1\). In this paper, it is proved that there exists a set \(\mathcal{V}(\Delta; f) \subseteq \mathbb{F}_p\) with \[ \#V(\Delta; f) = O(A(n, m)\Delta^{\lambda_{n,m}}), \] where \[ A(n, m) = m^2(2m + 2n)^{(m+n-1)/2}\text{ and } \lambda_{n,m} =\frac{ m(m + 1) + n(n - 1)}{2}, \] if \(m \geq n\), and \[ A(n, m) = n^2(2n + 2m)^{(m+n-1)/2}\text{ and } \lambda_{n,m} =\frac{n(n + 1) + m(m - 1)}{2}, \] otherwise, having the following property: whenever \(v_0 \not \in \mathcal{V}(\Delta; f)\) then, given a \(\Delta\)-approximation \((w_0, w_1)\) to a point \((v_0, v_1) \in \mathbb{F}_p^2\) with \(H(n,m,f)(v_0, v_1 )=0\), one can recovers \((v_0, v_1)\) in deterministic polynomial time in \(m\), \(n\) and \(\log p\). As a consequence of this result an upper bound on the number of roots of such bivariate polynomials where the roots have certain restrictions is given.