On the hidden shifted power problem
From MaRDI portal
Abstract: We consider the problem of recovering a hidden element of a finite field of elements from queries to an oracle that for a given returns for a given divisor . We use some techniques from additive combinatorics and analytic number theory that lead to more efficient algorithms than the naive interpolation algorithm, for example, they use substantially fewer queries to the oracle.
Recommendations
- Polynomial interpolation and identity testing from high powers over finite fields
- scientific article; zbMATH DE number 2086222
- Identity testing and interpolation from high powers of polynomials of large degree over finite fields
- Solving Hidden Number Problem with One Bit Oracle and Advice
- Sparse polynomial approximation in finite fields
Cited in
(41)- On the hybrid power mean involving the character sums and Dedekind sums
- Character sums and deterministic polynomial root finding in finite fields
- Elements of large order on varieties over prime finite fields
- Values of rational functions in small subgroups of finite fields and the identity testing problem from powers
- Subgroups generated by rational functions in finite fields
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- On the two-term exponential sums and character sums of polynomials
- An effective local-global principle and additive combinatorics in finite fields
- Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields
- One kind of character sum modulo a prime \(p\) and its recurrence formula
- Generalized polynomial exponential sums and their fourth power mean
- Lattices in function fields and applications
- Double character sums with intervals and arbitrary sets
- Systems of congruences with products of variables from short intervals
- Product of subsets of small intervals and points on exponential curves modulo a prime
- On a girth-free variant of the Bourgain-Gamburd machine
- On the primitive roots and the generalized Golomb's conjecture
- Some character sums of the polynomials
- The primitive roots and a problem related to the golomb conjecture
- On congruences with products of variables from short intervals and applications
- On the character sum of polynomials and the two-term exponential sums
- Shifted character sums with multiplicative coefficients
- A four-order linear recurrence formula involving the quartic Gauss sums and one kind two-term exponential sums
- On the fourth power mean of the generalized quadratic Gauss sums
- Multiplicative congruences with variables from short intervals
- Shifted character sums with multiplicative coefficients. II.
- The congruence \(ax_1x_2\cdots x_k + bx_{k+1}x_{k+2}\cdots x_{2k} \equiv c \pmod p\)
- Identity testing and interpolation from high powers of polynomials of large degree over finite fields
- A note on the primitive roots and the Golomb conjecture
- On Pythagorean triples and the primitive roots modulo a prime
- The hybrid power mean of some special character sums of polynomials and two-term exponential sums modulo \(p\)
- Double character sums over subgroups and intervals
- Congruences with intervals and subgroups modulo a prime
- Estimates for trilinear and quadrilinear character sums
- Concentration of points on curves in finite fields
- Polynomial values in small subgroups of finite fields
- On the power of the shift instruction
- Modular hyperbolas
- Polynomial interpolation and identity testing from high powers over finite fields
- Solutions to polynomial congruences in well-shaped sets
- Sums of inverses in thin sets of finite fields
This page was built for publication: On the hidden shifted power problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4910574)
