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


q = 1591646908070155847916963586885757663611980465519823631755037539680092095045862090726135581178157761817489455092117167782391955226530969795393239461418421

have such property.

  • 4
    $\begingroup$ Is this homework? I am only asking to judge if that problem is probably too hard to solve in my lifetime. $\endgroup$
    – user27950
    Jun 11 '18 at 19:40
  • $\begingroup$ 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? $\endgroup$
    – 111
    Jun 13 '18 at 12:20
  • $\begingroup$ @111 Complexity $O\left(2^\frac{\ell}{2}\right)$ is not efficient at all. $\endgroup$
    – Lisbeth
    Jun 13 '18 at 12:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – David R
    Jun 15 '18 at 21:10
  • 3
    $\begingroup$ A second observation: $\phi(n) = n - (a+b)^2$, but I cannot see how to exploit this to factor n. $\endgroup$
    – 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)<N^\delta$ 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<N^\delta$ then we can factor $N$ in polynomial time.

  • $\begingroup$ So I just ran the math on this and it yielded $\delta<0.069$ for $\beta=1/2$. $\endgroup$
    – SEJPM
    Jun 22 '18 at 9:39
  • 3
    $\begingroup$ It seems to me that the method does not exploit the fact that p and q are correlated $\endgroup$
    – user27950
    Jun 23 '18 at 14:55
  • 2
    $\begingroup$ 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. $\endgroup$
    – 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.

  • 3
    $\begingroup$ 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? $\endgroup$
    – SEJPM
    Jun 23 '18 at 18:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.