3
$\begingroup$

Assume my prime generation is as follows:

  1. Pick a number $p$ between 1000 and 9999. $p=abcd$.

  2. Make sure $p$ is prime

  3. Construct $q$ such by taking the last 2 digits of $p$ and the first 2 digits of $p$, i.e. $q=cdab$

  4. Make sure $q$ is prime.

Is the resulting $n = p·q$ more easily factorable?

My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?

$\endgroup$
3
  • 2
    $\begingroup$ Of course, any product of two 4-digit primes is trivially factorable by trial division anyway, since there are only 1061 primes between 1000 and 9999. Add in the digit reversal requirement, and there are only 76(!) possible pairs to consider. $\endgroup$ Commented Apr 6, 2019 at 1:37
  • 1
    $\begingroup$ @Nat: My fault, I added the "$= pq$" for context in an edit, and didn't notice the potential ambiguity. I see Paŭlo has already fixed it. $\endgroup$ Commented Apr 6, 2019 at 12:19
  • $\begingroup$ I'd just like to add that this is inspired by a contest that just ended (12 minutes ago). $\endgroup$
    – enedil
    Commented Apr 6, 2019 at 16:12

2 Answers 2

9
$\begingroup$

You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 \lt x, y \lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.

The rightmost digit of $n$ in base $B$ is $(x y) \bmod B$. Since $\{x,y\} \le B-1$, $(x^2 + y^2) B + x y \le 2 (B-1)^2 B + (B-1)^2 \lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) \lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 \le z \lt 2$, i.e. $z \in \{0, 1\}$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y \in \{W_0, W_1\}$.

Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.

$\endgroup$
2
  • $\begingroup$ Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold? $\endgroup$
    – S. L.
    Commented Apr 5, 2019 at 19:03
  • $\begingroup$ @S.L. Woops, different equation, but same principle. $\endgroup$ Commented Apr 5, 2019 at 20:39
3
$\begingroup$

Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):

We have $n = xyB^2 + (x^2+y^2)B + xy$

First, compute $n \bmod B$, that gives you $xy \bmod B$

Then, compute $\lfloor (n - B^2(xy \bmod B)) / B^3 \rfloor$; this gives you $xy / B + \epsilon$, where $0 \le \epsilon \le 2$

Pasting those two together will give you a total of three possibilities of $xy$.

Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $\epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.

(Thanks for Giles for pointing out this last part)

$\endgroup$
4
  • $\begingroup$ Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$. $\endgroup$ Commented Apr 5, 2019 at 20:39
  • $\begingroup$ @Gilles: yup, you're right; I'll update the answer $\endgroup$
    – poncho
    Commented Apr 5, 2019 at 21:01
  • $\begingroup$ I don't get this part: Then, compute $⌊(n−B^2(xy\mod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xy\mod B$ but not $xy$? $\endgroup$
    – S. L.
    Commented Apr 5, 2019 at 21:10
  • 1
    $\begingroup$ $(n - B^2(xy \bmod B)) / B^3 = \lfloor(xy/B) \rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $\ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down... $\endgroup$
    – poncho
    Commented Apr 5, 2019 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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