$$ p = a ^ 2 + b ^ 2，\ qquad q = 2ab + 1 $$
我正在寻找一种有效的算法来分解这样的模数。
例如：
p = 3905103830521375109989981821052358603060411974175739135178032413678045353995521841398265207464935019588673586293494986686589282006584612622774357122916381
和
q = 1591646908070155847916963586885757663611980465519823631755037539680092095045862090726135581178157761817489455092117167782391955226530969795393239461418421
具有这种性质。
/>
#1 楼
令$ N = p \，q $为RSA模数，使得$ p> N ^ \ beta $和$ \ displaystyle p = \ sum_ {i = 0} ^ k a_i \，x ^ i $使得$ \ max （a_i）$$ \ delta <\ frac {1} {k + 1} \ bigl（1-（1- \ beta）^ \ frac {k + 1} {k}-（k + 1）（1-（1- \ beta）^ \ frac {1} {k}）（1- \ beta）\ bigr）。$$
然后可以将$ N $乘以多项式时间（请参见此处）。
您的问题$ a \ ne b $。设$ b = a + c $。所以
$$ p = 2a ^ 2 + 2ca + c ^ 2，\ q = 2a ^ 2 + 2c + 1。$$
在这种情况下（$ q> N ^ {0.499} $，$ k = 2 $）我们有$ a_0 = 2c + 1，a_1 = 0 $和$ a_2 = 2 $，这意味着如果$ 2c + 1 < N ^ \ delta $，那么我们可以将$ N $计入多项式时间。
评论
$ \ begingroup $
因此，我对此进行了数学运算，结果得出$ \ delta <0.069 $的价格为$ \ beta = 1/2 $。
$ \ endgroup $
– SEJPM♦
18年6月22日在9:39
$ \ begingroup $
在我看来，该方法没有利用p和q相关的事实
$ \ endgroup $
–user27950
18年6月23日在14:55
$ \ begingroup $
对OP的$ p，q $进行测试，条件$ 2c + 1
$ \ endgroup $
– 111
18年6月25日在14:39
#2 楼
尽管这是蛮力https://crypto.stackexchange.com/a/60190/59847
，否则我们可以从$ p = \ sqrt {n} $开始。
评论
$ \ begingroup $
您的答案非常不清楚，您如何应用链接的答案中的方法？ “从$ p = \ sqrt {n} $开始”是什么意思？您是否意识到$ \ sqrt n $和$ p $或$ q $之间可能存在许多数字，因此仅递增直到您命中一个数字就可能行不通？
$ \ endgroup $
– SEJPM♦
18年6月23日在18:24
评论
这是作业吗？我只是想判断这个问题在我的一生中是否可能太难解决了。如果$ p，q $具有$ \ ell- $位，您是否对时间复杂度为$ O（2 ^ {\ ell / 2}）$的算法感到满意？我想，“有效”是指多项式。您确定存在这样的算法吗？
@ 111复杂度$ O \ left（2 ^ \ frac {\ ell} {2} \ right）$根本没有效率。
一个小观察：因为$ p $是两个平方的和，所以我们必须通过两个平方定理的总和或更具体地由Fermat的结果得出$ p \ equiv 1 \ pmod 4 $。
第二个观察结果：$ \ phi（n）= n-（a + b）^ 2 $，但是我看不到如何利用它来分解n。