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 $(2^nX+Y)(2^nY+Z)(2^nZ+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.

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.

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 contracts an integer polynomial with an unusually small integer solution and uses lattice methods to find the solution.

In this case the polynomial $(2^nX+Y)(2^nY+Z)(2^nZ+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.

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 $(2^nX+Y)(2^nY+Z)(2^nZ+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.