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 &amp; = &amp; p \mathbin\Vert q \\
Q &amp; = &amp; q \mathbin\Vert r \\
R &amp; = &amp; 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?
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.