18
$\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$
11
  • 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, 2018 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, 2018 at 12:20
  • $\begingroup$ @111 Complexity $O\left(2^\frac{\ell}{2}\right)$ is not efficient at all. $\endgroup$
    – Lisbeth
    Jun 13, 2018 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, 2018 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, 2018 at 20:46

3 Answers 3

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ So I just ran the math on this and it yielded $\delta<0.069$ for $\beta=1/2$. $\endgroup$
    – SEJPM
    Jun 22, 2018 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, 2018 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, 2018 at 14:39
0
$\begingroup$

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.

$\endgroup$
-3
$\begingroup$

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

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

$\endgroup$
1
  • 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, 2018 at 18:24

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