# so easy rsa

RSA but are taken as two numbers close in a LCG sequence . You get . 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 directly under :


# 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 . We may set and pretend that’s the start of the sequence. Then we get for some (very) small . (Since both factors are generated by this LCG, we know so it’s fine to work under .)

Now, . And naming these cumbersome coefficients and we get and we do some algebra to complete the square . Testing a few values of and using standard modular square root leads to the factors.

Took about an hour or so.