# Factorizing a handiwork number $n$ in two prime factors

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?

• This is an example: $r_0 = 12476250663352613257$ and $s_0 = 9486385304221910839$ and $p = 94106286778769262446541721210277285743927271229498284753164654370662758702469992454479622592965377831346910438507499335897172318522001$ and $q = 13827234148199454847612050065924174471975125236724755327652050769520573869973860987904563428946961505616430440398323041612571106720001$. – Lisbeth Jun 8 '17 at 14:25
• 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$. – 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.
• Please note that only $r_0$ and $s_0$ are prime, other $r_i$ and $s_i$ are not necessarily prime. – Lisbeth Jun 8 '17 at 15:36
• @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). – tylo Jun 8 '17 at 15:38