# 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
Commented Jun 11, 2018 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
Commented Jun 13, 2018 at 12:20
• @111 Complexity $O\left(2^\frac{\ell}{2}\right)$ is not efficient at all. Commented Jun 13, 2018 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. Commented Jun 15, 2018 at 21:10
• A second observation: $\phi(n) = n - (a+b)^2$, but I cannot see how to exploit this to factor n.
– user27950
Commented Jun 16, 2018 at 20:46

From the special form of p and q specified it can be determined that the difference d= |p-q| is of the form k^2-1 with one exception. Also d mod 24 = 0. The exception is when a=b=1. In this case d = 1.

The limited number of unique differences significantly reduces the factorization time.

Note that n is known but p,q,a, b and d are not. p and q are prime.

The difference d= |p-q| = |a^2+b^2-(2ab+1)| = |a^2+b^2-2ab-1|
This reduces to d=(a-b)^2-1.

With the difference d known the factors of n can be found by finding integer solutions to the quadratic: p^2+dp-n = 0 which is a rearrangement of p(p+d) = n.

The algorithm to factor n with this special form:

'RSA numbers usually have equal length factors
n_len = length(n)   'length in decimal digits
factor_len = round(n_len/2)
min_factor_value = 10^(factor_len-1)
max_factor_value = 10^(factor_len)-1

'm is the maximum possible difference between p and q
'     Example for 4 digit factors  m=9999-1000 = 8999
m = max_factor_value - min_factor_value

k =round(sqrt(m))

loop:
If k^2 mod 24 = 1
d = k^2-1
if (d^2+4n) is a square
p = (-d+sqrt(d^2+4n))/2
q = n/p
return p,q
k = k-1
goto loop


Benchmarked this algorithm in Pari/Gp versus the Fermat algorithm for n, a random modulus of the special form requested.
n = 74234692929546985792914275827849
The algorithm above took 4.978 seconds.
Fermat's algorithm was still running after 49 minutes and 25 seconds and had not completed.

n is a random modulus of the special form requested.
p = a^2+b^2
q = 2ab+1
both p and q prime

After factoring n
p = 8622962252581529
q = 8608954875956081
d = 14007376625448
a = 67506520
b = 63763877

Hope this helps.

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$. Commented Jun 22, 2018 at 9:39
• It seems to me that the method does not exploit the fact that p and q are correlated
– user27950
Commented Jun 23, 2018 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
Commented Jun 25, 2018 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? Commented Jun 23, 2018 at 18:24