algorithm - 使用 N 求 D(因式分解)

Question

我试图通过分解 N 来找到 D。

我的 N 是 265291078722948385089717069136983657793

我发现 P & Q 使用

 n = p.q 

P - 14716976826788780483 
Q -18026193955816294571

同样，我发现 ɸ 使用

ɸ = (p - 1).(q - 1)

下一步说

Select e; such that, e is relatively prime to ɸ and e < ɸ, gcd (e, ɸ) = 1

现在我卡在了这一步，无法继续。我不确定这是否是分解 N 以找到 D 的正确方法。

P.S - 最后一步是 Select d;这样，d.e mod ɸ = 1 或 e = 1 mod ɸ使用这一步我应该找到 D。但我卡在了倒数第二步。

感谢任何帮助。 :)

编辑(答案):E =65537 (2^16 + 1)，是最常见的加密形式，应用广泛。

The query boils down to 
D*E mod ɸ = 1
which implies that D*E = Xɸ + 1, where X=1,2,3,4....
D = (Xɸ + 1)/E

现在简单地使用上面的逻辑来获取 D 的可能值 :)

Answer 1

我建议从 e=3 开始，然后尝试 e=5、7、11 等等。满足的条件是

(d * e) % φ(n) = 1

在你的例子中 φ(n) = 265291078722948385056973898354378582740

所以，为了找到d，我会做一个表

For e=3, d = (φ(n)+1) / e
           =  265291078722948385056973898354378582741 / 3
           = 88430359574316128352324632784792860913

现在求 e=5、7 等等