Skip to main content
2 of 5
added 28 characters in body
user avatar
user avatar

Structured factoring

Is it easier to factor $$(ax + b) (ay+ c)=M$$ where $a,b,c\in\Bbb N$ are known where $b$ and $c$ are similar in size and approximately $\sqrt M$ and $a$ is approximately $b^{2/3}$ and unknowns $x,y\in\Bbb N$ and are approximately $b^{1/3}$?

Does coppersmith's techniques speed up factorization here?

$$(ax + at+u) (ay+ av+w)=(a(x+t) + u) (a(y+v)+ w)=M$$

$$uw=M\bmod a$$

user76479