Namely, we consider an analogue of this problem for a certain class of polynomials over an extension of a finite field; recovering a hidden polynomial given the values of its trace at randomly selected points. Also, we give an algorithm for a variant of the problem in free finite dimensional modules. This result can be helpful for studying security of analogues of the RSA and Diffie-Hellman cryptosystems over such modules.

The hidden number problem is also related to the so called black-box field model of computation. We show that simplified versions of the above recovery problems can be used to derive positive results on the computational power of this model.