RSA factorization for special primes $p$ and $q$ I want to factorize the modulus $n = pq$ knowing that $p$ and $q$ are not random, but constructed based on integer numbers $a$ and $b$ as following ($a$ and $b$ are not given):

$$p = a^2 + b^2, \qquad q = 2ab + 1$$

I'm looking for an efficient algorithm for factorizing such modulus.
For example:

p = 3905103830521375109989981821052358603060411974175739135178032413678045353995521841398265207464935019588673586293494986686589282006584612622774357122916381


and

q = 1591646908070155847916963586885757663611980465519823631755037539680092095045862090726135581178157761817489455092117167782391955226530969795393239461418421


have such property.
Let $N=p\,q$ be an RSA modulus such that $p&gt;N^\beta$ and $\displaystyle p=\sum_{i=0}^k a_i\,x^i$ such that $\max(a_i)&lt;N^\delta$ and


  $$\delta &lt;\frac{1}{k+1}\bigl(1-(1-\beta)^\frac{k+1}{k}-(k+1)(1-(1-\beta)^\frac{1}{k})(1-\beta)\bigr).$$


Then one can factor $N$ in polynomial time (see here).

In your question $a\ne b$. Let $b=a+c$. So 


  $$p=2a^2+2ca+c^2,\ q=2a^2+2c+1.$$


In this case ($q&gt;N^{0.499}$, $k=2$)  we have $a_0=2c+1, a_1=0$ and $a_2=2$ which means that if $2c+1&lt;N^\delta$ then we can factor $N$ in polynomial time.