Return to Question

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$"'

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$"'

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?

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$"'

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

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?