# 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.

• Is this homework? I am only asking to judge if that problem is probably too hard to solve in my lifetime. – user27950 Jun 11 '18 at 19:40
• if $p,q$ have $\ell-$ bits, are you satisfied with an algorithm having time complexity $O(2^{\ell/2})$? I suppose, that with "efficient" you mean polynomial. Are you sure that such an algorithm exists? – 111 Jun 13 '18 at 12:20
• @111 Complexity $O\left(2^\frac{\ell}{2}\right)$ is not efficient at all. – Lisbeth Jun 13 '18 at 12:29
• A small observation: because $p$ is the sum of two squares, we must have $p \equiv 1 \pmod 4$ by the sum of two squares theorem, or more specifically by a result of Fermat. – David R Jun 15 '18 at 21:10
• A second observation: $\phi(n) = n - (a+b)^2$, but I cannot see how to exploit this to factor n. – user27950 Jun 16 '18 at 20:46

Let $$N=p\,q$$ be an RSA modulus such that $$p>N^\beta$$ and $$\displaystyle p=\sum_{i=0}^k a_i\,x^i$$ such that $$\max(a_i) and

$$\delta <\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>N^{0.499}$$, $$k=2$$) we have $$a_0=2c+1, a_1=0$$ and $$a_2=2$$ which means that if $$2c+1 then we can factor $$N$$ in polynomial time.

• So I just ran the math on this and it yielded $\delta<0.069$ for $\beta=1/2$. – SEJPM Jun 22 '18 at 9:39
• It seems to me that the method does not exploit the fact that p and q are correlated – user27950 Jun 23 '18 at 14:55
• Testing this idea to the $p,q$ of OP, the condition $2c+1<N^{\delta}$ is not valid. In more details the $a= 61119241924783390726301942398045672185132693478002768557017046192073503484315$ $b = 13020833193815801032279210387066917968731643768617767845772080552260585759534$ and I used $\delta<0.069$ of SEJPM. Then $c=a-b>N^{\delta}.$ Although, it is a nice idea. – 111 Jun 25 '18 at 14:39

though this is a brute force https://crypto.stackexchange.com/a/60190/59847

or we can start from $p =\sqrt{n}$ up.

• Your answer is highly unclear, how do you want to apply the method from the linked answer? What do you mean with "start from $p=\sqrt{n}$ up"? Do you realize that there are probably a lot of numbers between $\sqrt n$ and $p$ or $q$ and thus just incrementing until you hit one will likely not work? – SEJPM Jun 23 '18 at 18:24