Skip to main content
5 of 5
added 58 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 $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?


Coppersmith's theorem $2$ in Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities says that:

"`Let $p(x, y)$ be an irreducible polynomial in two variables over $\Bbb Z$, of maximum degree $\delta$ in each variable separately. Let $X, Y$ be bounds on the desired solutions $x_0, y_0$. Define $\tilde p(x, y) = p(x X, yY )$ and let $W$ be the absolute value of the largest coefficient of $\tilde p$. If $XY < W^{{2/(3\delta)}−\epsilon}2^{−14\delta/3}$ then in time polynomial in $(\log W, \delta, 1/\epsilon)$, we can find all integer pairs $(x_0, y_0)$ with $p(x_0, y_0) = 0$, $|x_0| < X$, and $|y_0| < Y$"'

In corollay $2$ he sharpens this to "`With the hypothesis of Theorem $2$, except that $XY ≤ W^{2/(3\delta)}$, then in time polynomial in $(\log W, 2^\delta )$, we can find all integer pairs $(x_0, y_0)$ with $p(x_0, y_0) = 0$, $|x_0|\leq X$, and $|y_0| \leq Y$"'

user76479