A hidden number problem in small subgroups
Igor E. Shparlinski, Arne Winterhof · Mathematics of Computation · 2005
Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a hidden element α ∈ F p \alpha \in \mathbb {F}_p , where p p is prime, from rather short strings of the most significant bits of the residue of α t \alpha t modulo p p for several randomly chosen t ∈ F p t\in \mathbb {F}_p . González Vasco and the first author have recently extended this result to subgroups of F p ∗ \mathbb {F}_p^* of order at least p 1 / 3 + ε p^{1/3+\varepsilon } for all p p and to subgroups of order at least p ε p^\varepsilon for almost all p p . Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the multipliers t t and thus extend this result to subgroups of order at least ( log p ) / ( log log