Extracting modulus from hidden function I have a hidden function $f(x) = x \pmod{n}$ and would like to solve for $n$ based on a set of input and output pairs which can be chosen freely.

I would like to do this without brute force (i.e. start at $x_0=1$ and iterate $x_{i+1}=x_i+1$ until $f(x_i)=0$).

So far I have observed that if I expand $x=an+b$, then by subtracting $f(x)=b$ from the input, I am left with $x-f(x)=an$.

I can repeat this operation for various inputs and obtain a list of different multiples of $n$, but I cannot work out how to use them to solve for $n$ itself.

If I use the above procedure to obtain distinct $a_0n$ and $a_1n$, I could compute $gcd(a_0n,\,a_1n) = kn$, but there is no guarantee that $k=1$, and the situation remains the same no matter how many $a_in$ are processed in this way.

Is this even a solvable problem or do I need to include extra constraints on the function, like being explicit about the domain, perhaps $f := \mathbb{F_2}[x] \to \mathbb{F_2}[x]$ (polynomials with binary coefficients)?
This smells like a HW question, so the OP should try it with more hints.

By querying this function at $x$, it is easy to tell whether $x\geq n$ or $x&lt;n$. Let $k$ be a natural number such that $2^k&lt;n\leq 2^{k+1}$, how many queries do you need to find this $k$? Knowing this $k$, how can you figure out $n$?



If the modulo operation is part of polynomial division with remainder, you could find the degree of $n$ using binary search. Once you know the degree, you can query another polynomial to find $n$.