Mryntu

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 = pq$ 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?

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$.

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)