如果有算法A可以计算输入n的模平方根，那么如何利用它得到素因子？

Question

假设给出了一个算法A，该算法以y \in \{0, 1, \ldots , N − 1\}作为输入，并输出x \in \{0,1,\ldots,N − 1\}，从而使x^2 \equiv y \pmod{N}。设计一种有效的随机化的方法，使用A来获得素因子。

这是研究生算法课程的作业题。

它类似于这个问题。区别在于我们没有一个特定的数字51733469。我的想法是，我们可以随机选择一个数字a之间的[1,n-1]，使用A来计算它的模块平方根，并做完全相同的解决方案这里？或者随机挑选的数字a应该满足任何条件？

Answer 1

方程x^2\equiv y\pmod N有多少个解？

当N是奇数和\gcd(y,N)=1时，这个问题就更容易解决了(注意，当两者都不成立时，我们有一个N因子)：有0或2^k解决方案，其中k是不同素数p_i除法N的数目。证明以N素数开始(参见勒让德符号)，然后是素数的幂，然后是不同素数的幂的乘积(使用中国剩余定理)。

为什么算法A总是返回相同的输出？

回答这个问题的证明思想应该有效，包括算法A总是为输入(y,N)返回相同的输出x，因为问题的假设“假设.”中没有任何内容。表示A将返回所有解决方案，或最终在反复调用时返回所有解决方案。许多算法都是确定性的，对于给定的输入总是执行相同的操作，包括产生相同的结果。实际上，在密码学中，考虑到随机行为必须来自显式的额外随机输入，我们通常会隐式地限制这样的确定性算法。

提示:你想要有两个解决方案:一个是你事先知道的，另一个是算法给你的。算法无法读取您的思维，因此有可能返回另一个解决方案，这可能会有所帮助。