# Factorization for special primes $P$, $Q$, and $R$

Suppose that $$p$$, $$q$$, and $$r$$ are distinct $$n$$-bit primes, we define $$\begin{array}{rcl} P & = & p \mathbin\Vert q \\ Q & = & q \mathbin\Vert r \\ R & = & r \mathbin\Vert p \end{array}$$ Where $$\mathbin\Vert$$ means concatenation of two integers. For example $$1165993 \mathbin\Vert 1420831 = 11659931420831$$ We are given $$N = P \times Q \times R$$ and $$P, Q, R \in \mathbb{P}$$, that is they are primes too. Can we factor $$N$$ in polynomial time? I have listed an example for this question too, we know that $$\scriptsize N = P \times Q \times R = 12263640959607413166286548792372138857838409113471105337781351695720741222286495632687410855193016269011718576637693250596988228986909434347895553431945099$$

Can we factor it?

• Could you tell us the origin of this question? What is the size of $p,q,r$? Apr 2 at 20:20
• Note $11659931420831 = 894167 \times 13039993$ Apr 2 at 21:38
• @kelalaka $p, q, r$ are 85-bit primes, and I have constructed $P, Q, R$ from those three primes with concatenation that I defined above. Also these new integers are prime. Please note that $\mathbin\Vert$ just means concatenation, $5\mathbin\Vert7 = 57$, $1\mathbin\Vert1 = 11$, and etc. Apr 3 at 2:15
• $2^{2n}\cdot P + R - 2^n\cdot Q = (2^{3n}+1)\cdot p$, but I don't see how to use this in a lattice attack.
– j.p.
Apr 3 at 8:20
• Are you using base 10 or base 2 concatenation here?
– SEJPM
Apr 3 at 10:44

## 1 Answer

I don't think that we currently know how to exploit such structure.

The set-up immediately makes one think of Coppersmith's method for factoring RSA moduli with some bits of the factors known. This constructs a two-variable integer polynomial with an unusually small integer solution and uses lattice methods to find the solution.

In this case the polynomial $$(10^cX+Y)(10^cY+Z)(10^cZ+X)-N$$ has the solution $$(X,Y,Z)=(p,q,r)$$ with $$p,q,r\approx N^{1/6}$$. However this is a polynomial in three variables which is beyond our current knowledge of Coppersmith's method. The additional information that $$p$$, $$q$$ and $$r$$ are primes (and indeed that $$P$$, $$Q$$ and $$R$$ are primes) is not used by the methods, but I cannot see anyway to exploit this. If there are additional relationships between $$p$$, $$q$$ and $$r$$ that can eliminate on variable, more might be possible.

If you drop the polynomial-time requirement, then your example with $$n=85$$ can be solved in four hours for less than \$100.

• There are papers using trivariate coppersmith for some funny attacks on RSA. Why care about "provable" variants? Apr 4 at 9:35
• @Fractalice The question asks about polynomial time, which I can only really make sense of in the abstract vice pragmatic sense. I'll confess to unfamiliarity with the full literature and there may be a version that does do precisely what is needed. Apr 4 at 9:45
• That is the use of fass here? I don't see that what is written here answers this question at all. It is rather a comment. If you don't solve it why write as an answer instead of comment? Apr 4 at 11:30