快速因式分解

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，则为p。

在第一个例子中，我们有n/gcd(n,φ(n)) = p*q和φ(n)/gcd(n,φ(n)) = (p-1)*(q-1) = p*q + 1 - (p+q)，因此有x = p*q = n/gcd(n,φ(n))和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同样是微不足道的。

所以还是要决定你有哪一个案子。你有案例2当且仅当n/gcd(n,φ(n))是素数。

为此，你需要一个像样的原始性测试。或者你可以先假设你有案例1，如果不成功，你可以得出结论，你有案例2。

Answer 2

试着找出n/ (n -φ(n))是什么。

后续行动：

N/ (n -φ(n)) = pq。你就一直用pq除以n。