快速分解

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*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再次是微不足道的.

所以仍然需要决定你拥有哪种情况.当且仅当n/gcd(n,?(n))是一个素数时,你有案例2 .

为此,你需要一个体面的素性测试.或者你可以先假设你有案例1,如果这样做不成功,可以断定你有案例2.