5
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Could you tell us the origin of this question? What is the size of $p,q,r$? $\endgroup$
    – kelalaka
    Apr 2 at 20:20
  • $\begingroup$ Note $11659931420831 = 894167 \times 13039993$ $\endgroup$
    – kelalaka
    Apr 2 at 21:38
  • $\begingroup$ @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. $\endgroup$
    – Lisbeth
    Apr 3 at 2:15
  • $\begingroup$ $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. $\endgroup$
    – j.p.
    Apr 3 at 8:20
  • 1
    $\begingroup$ Are you using base 10 or base 2 concatenation here? $\endgroup$
    – SEJPM
    Apr 3 at 10:44
1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ There are papers using trivariate coppersmith for some funny attacks on RSA. Why care about "provable" variants? $\endgroup$
    – Fractalice
    Apr 4 at 9:35
  • $\begingroup$ @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. $\endgroup$
    – Daniel S
    Apr 4 at 9:45
  • $\begingroup$ 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? $\endgroup$
    – kelalaka
    Apr 4 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.