特殊素數的 RSA 分解ppp和qqq

我想分解模數 $ n = pq $ 知道 $ p $ 和 $ q $ 不是隨機的，而是基於整數構造的 $ a $ 和 $ b $ 如下（ $ a $ 和 $ b $ 沒有給出）：

$$ p = a^2 + b^2, \qquad q = 2ab + 1 $$ 我正在尋找一種有效的算法來分解這種模數。例如：

p = 3905103830521375109989981821052358603060411974175739135178032413678045353995521841398265207464935019588673586293494986686589282006584612622774357122916381

和

q = 1591646908070155847916963586885757663611980465519823631755037539680092095045862090726135581178157761817489455092117167782391955226530969795393239461418421

有這樣的財產。

讓 $ N=p,q $ 是一個 RSA 模數，使得 $ p>N^\beta $ 和 $ \displaystyle p=\sum_{i=0}^k a_i,x^i $ 這樣 $ \max(a_i)<N^\delta $ 和

$$ \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 $ 在多項式時間內。

雖然這是蠻力 https://crypto.stackexchange.com/a/60190/59847

或者我們可以從 $ p =\sqrt{n} $ 向上。

引用自：https://crypto.stackexchange.com/questions/59921