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

Question

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?

Answer 1

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.