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 fourth power mean of the generalized quadratic Gauss sums
- Polynomial interpolation and identity testing from high powers over finite fields
- One kind of character sum modulo a prime \(p\) and its recurrence formula
- Identity testing and interpolation from high powers of polynomials of large degree over finite fields
- On the power of the shift instruction
- Modular hyperbolas
- A four-order linear recurrence formula involving the quartic Gauss sums and one kind two-term exponential sums
- On the two-term exponential sums and character sums of polynomials
- The primitive roots and a problem related to the golomb conjecture
- On the primitive roots and the generalized Golomb's conjecture
- On the hybrid power mean involving the character sums and Dedekind sums
- Multiplicative congruences with variables from short intervals
- Subgroups generated by rational functions in finite fields
- On the character sum of polynomials and the two-term exponential sums
- Shifted character sums with multiplicative coefficients
- Double character sums with intervals and arbitrary sets
- Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields
- On congruences with products of variables from short intervals and applications
- Elements of large order on varieties over prime finite fields
- Shifted character sums with multiplicative coefficients. II.
- On Pythagorean triples and the primitive roots modulo a prime
- A note on the primitive roots and the Golomb conjecture
- The hybrid power mean of some special character sums of polynomials and two-term exponential sums modulo \(p\)
- Systems of congruences with products of variables from short intervals
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Solutions to polynomial congruences in well-shaped sets
- Double character sums over subgroups and intervals
- Sums of inverses in thin sets of finite fields
- Product of subsets of small intervals and points on exponential curves modulo a prime
- Concentration of points on curves in finite fields
- Some character sums of the polynomials
- Polynomial values in small subgroups of finite fields
- Values of rational functions in small subgroups of finite fields and the identity testing problem from powers
- The congruence \(ax_1x_2\cdots x_k + bx_{k+1}x_{k+2}\cdots x_{2k} \equiv c \pmod p\)
- Character sums and deterministic polynomial root finding in finite fields
- Generalized polynomial exponential sums and their fourth power mean
- On a girth-free variant of the Bourgain-Gamburd machine
- An effective local-global principle and additive combinatorics in finite fields
- Estimates for trilinear and quadrilinear character sums
- Lattices in function fields and applications
- Congruences with intervals and subgroups modulo a prime
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)
