Reconstructing points of superelliptic curves over a prime finite field
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.
- A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants
- A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers
- Additive energy and a large sieve inequality for sparse sequences
- Bilinear forms in Weyl sums for modular square roots and applications
- Factoring polynomials with rational coefficients
- Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach
- Geometric algorithms and combinatorial optimization
- How to predict congruential generators
- scientific article; zbMATH DE number 1643920 (Why is no real title available?)
- scientific article; zbMATH DE number 1182510 (Why is no real title available?)
- scientific article; zbMATH DE number 2081057 (Why is no real title available?)
- scientific article; zbMATH DE number 1852134 (Why is no real title available?)
- scientific article; zbMATH DE number 2120513 (Why is no real title available?)
- Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits
- Inferring sequences produced by pseudo-random number generators
- Lattice reduction: a toolbox for the cryptoanalyst
- Minkowski's Convex Body Theorem and Integer Programming
- On Lovász' lattice reduction and the nearest lattice point problem
- Points on curves in small boxes and applications
- Predicting nonlinear pseudorandom number generators
- Reconstructing noisy polynomial evaluation in residue rings
- Reconstructing Truncated Integer Variables Satisfying Linear Congruences
- Recovering zeros of polynomials modulo a prime
- Small solutions to polynomial equations, and low exponent RSA vulnerabilities
- Sparsity of curves and additive and multiplicative expansion of rational maps over finite fields
This page was built for publication: Reconstructing points of superelliptic curves over a prime finite field
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6089463)
