Problem-Definition. Assume you have a sufficient long integer interval $I=[0,n]$ and a set $Z$ that consists of tuples $(x,s(x))$, with $x \in_R I$ and $s(x) = \mathsf{sign}(\sin(2x\pi/p))$. Formulated in words, the set $Z$ contains the randomly distributed integers from $I$ enriched with the information if a certain (but fixed) sinus wave travels above or below that point (i.e., the sign value). Find the secret parameter $p$.
# Heuristic argument #
It can be heuristically proved, that even as few as $m =\log p$ points should be enough to find a unique value for $p$. Imagine a random sine wave that is plotted along the interval $I$. Since the points $x_i$ are randomly chosen from $I$, the chance that a point $x_i$ is traversed by the sine wave equal to its assigned sign value is $1/2$. Hence, the chances that a random curves traverses all $m$ points correct is $(1/2)^m$.But it seems one can not do better than $\mathcal{O}(p)$, that is exponential in $m$.