15
$\begingroup$

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.

$\endgroup$
  • 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
  • 2
    $\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
1
$\begingroup$

Let $N=pq$ be an RSA modulus such that $p>N^\beta$ and $p=\sum_{i=0}^k a_ix^i$ such that $max(a_i)<N^\delta$ and

$$\delta <\frac{1}{k+1}(1-(1-\beta)^\frac{k+1}{k}-(k+1)(1-(1-\beta)^\frac{1}{k})(1-\beta)).$$

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 is means that if $2c+1<N^\delta$ then we can factor $N$ in polynomial time.

$\endgroup$
  • $\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
-2
$\begingroup$

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

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

$\endgroup$
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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