Question

算法导论上31章数论算法的证明题

31.7-2 证明：如果Alice的公开指数e等于3，并且对方获得Alice的秘密指数d，0<d<φ(n).则对方能够在关于n的位数的多项式时间内对Alice的模n进行分解。
解释一下条件：φ(n)=(p-1)(q-1);p,q是300位左右的大素数，n=pq
ed(modφ(n))=1;现在求p,q 期待高手！

Answer 1

由ed=1(mod φ(n))，可设 ed = k*φ(n)+1，k∈Z
由e = 3，0<d<φ(n)得：0<ed<3*φ(n)
因此 0 < k*φ(n)+1 < 3*φ(n)，0<k<3，k=1或2
即 ed = φ(n)+1 或 ed = 2φ(n)+1，φ(n) = ed-1或φ(n) = 2ed-1
现已知φ(n)=(p-1)(q-1)和n=pq
可求得 p+q=n+1-φ(n)
即 p,q 是方程 x² - (n+1-φ(n)) x + n = 0的两根
可解得：p,q = ((n+1-φ(n) ± √((n+1-φ(n))²-4n)) / 2

以上计算仅涉及n, d, e的有限次加减乘除和开方运算。
每种运算都能够在关于n的位数的多项式时间内完成。
（设n的位数是d，加减法和除2运算可在O(d)时间内完成，乘法可在O(d²)时间内完成，
开方模拟手算也可以在O(d²)时间内完成）
因此能够在关于n的位数的多项式时间内对Alice的模n进行分解。

追问

该不是同学吧？
这题是我这次作业，我写的方法跟你一样。算k有什么用？
看了个开头，我还以为还有很精妙的方法。
另外手算开平方是O(d²)时间的 怎么证明？？？
一次除法的复杂度就已经是O(d^2)了 能证明 常数次除法 可以求出结果？

追答

只需说明：
1. φ(n)的取值只有C种（C是与n,d,e无关的常数）
2. 已知n和φ(n)，则p,q有初等解析解
3. 每种基本运算都能够在关于n的位数的多项式时间内完成

关于手算开方，就是利用 (10a+b)² - 100a² = 20ab + b²
开方的每一步中：M是上一步的余数，a是到上一步为止已求出的部分结果。
1. 在M后面添上后2位，
2. 试商：取b=0..9，计算20ab + b²，得到满足20ab + b²<=M的最大b值
3. 求余：计算M = M - (20ab + b²)
4. 在a后添上一位b
注意到b是一位数，以上计算和比较都可以在O(d)时间内完成。