Extracting modulus from hidden function

Question

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)?

Answer 1

You've done the hard work by finding that you can obtain $m_i=a_i\,n$ for various (unknown but essentially random) values of $a_i$.

Now define $n_0=m_0$, and compute $n_i=\gcd(n_{i-1},m_i)$ for increasing $i>0$. Sooner rather than later, the $n_i$ will converge to $n$.

This can be proved rigorously (though we often skip rigorous proofs in a crypto context). Sketch: prove by induction that $n_i=k_i\,n$ for $k_i$ dividing all $a_j$ with $0\le j\le i$. Then consider any prime factor $p$ of $k_i$, and the probability that it survives up to $i$ under the assumption that the $a_i$ are random.

Note: This works in a wider context than integers, e.g. polynomials, by changing "prime" to "irreducible".

Answer 2

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<n$. Let $k$ be a natural number such that $2^k<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$.