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

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".

• Thanks, the proof sketch is useful – conchild Dec 29 '19 at 12:12

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

• I cannot depend on these inequalities because $f$ could be defined on a finite-field with no ordering. – conchild Dec 27 '19 at 8:57
• @conchild does that mean the $\text{mod }n$ is remainder of polynomial division (the divisor is $n$)? – Gee Law Dec 28 '19 at 1:45
• Yes, that could be the case – conchild Dec 29 '19 at 12:11