I have generated two primes $r_0$ and $s_0$ with same bit size $\le 64$, then make another two primes as follows: choose constant $k$ and define $$r_i = r_0 + \alpha_i, \quad 1 \le i \le k, \quad 0 \le \alpha_i \le 1000$$ and $$s_i = s_0 + \beta_i, \quad 1 \le i \le k, \quad 0 \le \beta_i \le 1000$$ I have chosen $\alpha_i$ and $\beta_i$ such that both p and q are prime, $p = 2\times r_0\times r_1\times\cdots\times r_k + 1$ and $q = 2\times s_0\times s_1\times\cdots\times s_k + 1$. Can we factor $n = p \times q$ with knowing above facts?

  • $\begingroup$ This is an example: $r_0 = 12476250663352613257$ and $s_0 = 9486385304221910839$ and $p = 94106286778769262446541721210277285743927271229498284753164654370662758702469992454479622592965377831346910438507499335897172318522001$ and $q = 13827234148199454847612050065924174471975125236724755327652050769520573869973860987904563428946961505616430440398323041612571106720001$. $\endgroup$ – Lisbeth Jun 8 '17 at 14:25
  • $\begingroup$ So you have $\alpha_0,\alpha_1,\dots \alpha_k$ and similarly for $\beta$ and each $\alpha_i, \beta_i$ can have 1001 values. So you potentially have $1001^k$ values of each of the alphas and betas. That's a lot of values to consider to find a prime $p, q$. $\endgroup$ – user2460798 Jun 13 '17 at 0:03

The number you constructed is somewhat vulnerable to Pollard's p-1 method. If $r_0$ and $s_0$ are 64 bit long primes, then these are the largest factors in $p-1$ and $q-1$. The method works when $p-1$ (or $q-1$) is powersmooth for some "small" $B$ (choosing $B$ as $64$ bit number isn't that practical - the expected runtime of the algorithm is $O(\log^2(n)B \log(B))$).

In your question you wrote $r_0$ and $s_0$ have less than $64$ bit. If it is actually much smaller, the $p-1$ method will become viable.

Regarding the numbers in the comment: Those are $6\cdot 64 = 384$ bit primes? That is not an acceptable length for RSA - if that was your intention. According to the latest recommendation on keylength.com, today's fatoring moduli should have $2000$ bits at least, meaning you need primes with $1000$ bit each.

| improve this answer | |
  • $\begingroup$ Please note that only $r_0$ and $s_0$ are prime, other $r_i$ and $s_i$ are not necessarily prime. $\endgroup$ – Lisbeth Jun 8 '17 at 15:36
  • $\begingroup$ @Lisbeth Okay, noted. But that doesn't change anything: You can consider $B$ as the upper bound of the prime factors of $p-1$ (or $q-1$, that doesn't matter). $\endgroup$ – tylo Jun 8 '17 at 15:38
  • $\begingroup$ Note that especially with factors this small, ECM will probably outperform Pollard p-1. $\endgroup$ – SEJPM Jun 8 '17 at 17:14

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.