so easy rsa

RSA but $p,q$ are taken as two numbers close in a LCG sequence $x_i=a{x}_{i-1}+b(\mathrm{mod}m)$. You get $a,b,m$. Generous indeed.

First I thought it would be Coppersmith whatever, since you get some easy relations there, but as I was working out the algebra (again thinking in comments) I found you could find $p$ directly under $(\mathrm{mod}m)$:

# p (a^k p + (a^(k-1)+...)b == n (mod m)
# aa p^2 + bb p == n
# p^2 + bb/aa p == n/aa
# p^2 + 2*Q*p + Q^2 = ... + Q^2
# (p+Q)^2 = ...

I.e. an LCG is given directly by $x_i=a^{i+1}s+\frac{a^i-1}{a-1}b(\mathrm{mod}m)$. We may set $s=p$ and pretend that’s the start of the sequence. Then we get $q=a^{k+1}p+\frac{a^k-1}{a-1}b(\mathrm{mod}m)$ for some (very) small $k$. (Since both factors are generated by this LCG, we know $p,q<m$ so it’s fine to work under $(\mathrm{mod}m)$.)

Now, $n=p(a^{k+1}p+\frac{a^k-1}{a-1}b)(\mathrm{mod}m)$. And naming these cumbersome coefficients $A$ and $B$ we get $n=A{p}^2+Bp(\mathrm{mod}m)$ and we do some algebra to complete the square $\frac{n}{A}+(\frac{B}{2A}{)}^2=(p+\frac{B}{2A}{)}^2(\mathrm{mod}m)$. Testing a few values of $k$ and using standard modular square root leads to the factors.

Took about an hour or so.