因式分解问题

Question

比如说，X= a\cdot b，其中(a, b) \in Z_q^*和q是一个大素数。如果给出了X，那么寻找a和b的复杂性(或硬度)是什么？

请注意，可以重用a或b来计算也是公共的另一个X'。

编辑：(更多细节)

假设Alice选择两个随机数a, b\in Z^∗_q并计算X=a\cdot b。Alice发布X。鲍勃从已知的a和Z^∗_q猜测(或计算) X和D15的复杂性是什么？

Answer 1

比如说，X= a\cdot b，其中(a, b) \in Z_q^*和q是一个大素数。如果给出了X，那么寻找a和b的复杂性(或硬度)是什么？

如果乘法是在Z_q^*内完成的，那么选择一个任意的非零a并计算b = a^{-1}X就很容易了；您完成了。您可以通过扩展的欧几里得方法或使用a^{-1}计算a^{-1} = a^{p-2}。

这将找到满足方程的(a, b)对。如果你在寻找其他人想到的唯一的，那么，你运气不好--有满足方程的q-1对，没有其他信息，就无法确定哪一个是正确的。