algorithm - 快速分解

Question

对于给定的数字 n（我们知道 n = p^a * q^b，对于一些素数 p,q 和一些整数 a,b）和给定的数字 φ(n)（http://en.wikipedia. org/wiki/Euler%27s_totient_function）找到 p、q、a 和 b。

问题是 n 和 φ(n) 大约有 200 位数字，因此算法必须非常快。这似乎是一个非常困难的问题，我完全不知道如何使用 φ(n)。

如何解决这个问题？

Answer 1

因为n = p^a * q^b，全部是φ(n) = (p-1)*p^(a-1) * (q-1)*q^(b-1)。不失一般性，p < q.

所以gcd(n,φ(n)) = p^(a-1) * q^(b-1)如果p不分q-1，gcd(n,φ(n)) = p^a * q^(b-1)如果p分q-1。

在第一种情况下，我们有n/gcd(n,φ(n)) = p*qand φ(n)/gcd(n,φ(n)) = (p-1)*(q-1) = p*q + 1 - (p+q)，因此您有x = p*q = n/gcd(n,φ(n))and y = p+q = n/gcd(n,φ(n)) + 1 - φ(n)/gcd(n,φ(n))。然后找到p和q很简单：y^2 - 4*x = (q-p)^2、 所以q = (y + sqrt(y^2 - 4*x))/2和p = y-q。然后找到指数a并且b是微不足道的。

在第二种情况下，n/gcd(n,φ(n)) = q。然后你可以很容易地找到指数b，除以，q直到除法留下余数，从而得到p^a。分φ(n)给(q-1)*q^(b-1)你z = (p-1)*p^(a-1)。然后p^a - z = p^(a-1)和p = p^a/(p^a-z)。找到指数a又是微不足道的。

因此，仍有待决定您拥有哪种情况。当且仅当n/gcd(n,φ(n))是素数时，您有案例 2。

为此，您需要一个体面的素性测试。或者您可以首先假设您有案例 1，如果这不起作用，则得出结论您有案例 2。

Answer 2

尝试计算 n / (n - φ(n)) 是什么。

跟进：

n / (n - φ(n)) = pq。您只需将 n 除以 pq。