从隐函数中提取模数

Question

我有一个隐藏函数f(x) = x \pmod{n}，并想要解决n基于一组输入和输出对，可以自由选择。

我想在没有暴力的情况下这样做(即从x_0=1开始，然后迭代x_{i+1}=x_i+1直到f(x_i)=0)。

到目前为止，我已经观察到，如果我展开x=an+b，那么通过从输入中减去f(x)=b，就会留下x-f(x)=an。

我可以对不同的输入重复这个操作，并获得一个n的不同倍数的列表，但是我无法解决如何使用它们来解决n本身的问题。

如果我使用上面的过程来获得不同的a_0n和a_1n，我可以计算gcd(a_0n,\,a_1n) = kn，但是不能保证k=1，不管以这种方式处理了多少a_in，情况都是一样的。

这甚至是一个可解的问题，还是需要在函数上包含额外的约束，比如对域的显式，也许是f := \mathbb{F_2}[x] \to \mathbb{F_2}[x] (二元系数多项式)？

Answer 1

通过发现可以获得m_i=a_i\,n的各种(未知但本质上是随机的) a_i值，您已经完成了艰苦的工作。

现在定义n_0=m_0，并计算n_i=\gcd(n_{i-1},m_i)以增加i>0。n_i迟早会收敛到n。

这可以得到严格的证明(尽管我们经常跳过密码上下文中的严格证明)。草图:通过归纳证明n_i=k_i\,n用于k_i将所有a_j除以0\le j\le i。然后考虑任何素数因子p of k_i，以及在假定a_i是随机的情况下，它存活到i的概率。

注:通过将“素数”改为“不可约”，这在比整数(例如多项式)更广泛的背景下起作用。

Answer 2

这闻起来像是一个HW问题，所以OP应该尝试使用更多的提示。

通过在x上查询这个函数，可以很容易地判断x\geq n还是x<n。如果k是一个自然数，比如2^k<n\leq 2^{k+1}，您需要多少个查询才能找到这个k？知道这个k，你怎么能算出n呢？

如果模块操作是多项式除法的一部分，则可以使用二进制搜索找到n的程度。一旦你知道了这个程度，你就可以查询另一个多项式来找到n。