# When is Coppersmith method polynomial? (Factorization related)

From pari's implementation of Coppersmith method

zncoppersmith(P, N, X, {B=N}): finds all integers $x$ with $|x| \le X$ such that $\gcd(N, P(x)) \ge B$. $X$ should be smaller than

$$\exp((\log B)^2 / (\deg(P) \log N)) \qquad (1)$$

Observe that this might find non-trivial factor and pari's documentation gives example of this.

Linear $P(x)$ is allowed and looks like the content (the gcd of coefficients) of $P(x)$ need not be $1$.

I believe this algorithm (if successful) might find non-trivial factor for general $N$.

Let $v$ be positive integer and set $P(x)=v(x-1), N=nv$ where $n$ is integer to be factored.

For a divisor $d$ of $n$, $\gcd(P(d+1),N)=dv$.

With few guesses, one can find $v,X,B$ such that (1) holds.

Experimentally, for very small $n$, this indeed factors $n$.

Examining the source, I believe this is explained by small $N$ handled specially.

For larger $N$, the algorithm, doesn't return in reasonable time and debugging info shows signs of infinite loop, possibly caused by C double.

Q1 When Coppersmith's algorithm is polynomial and this approach factors $n$? Is the content the only obstacle?

• Coppersmith mentions integer factorization in his second paper on the topic: link.springer.com/chapter/10.1007%2F3-540-68339-9_16 Feb 19 '16 at 16:31
• @MaxAlekseyev Thanks. Your link is bivariate and doesn't mention the bound AFAICT. In some cases it requires coprime content, which may answer the question.
– joro
Feb 20 '16 at 8:34
• @joro Where did you get the bound?
– Mr.
Dec 31 '18 at 18:10

We asked on the pari-dev mailing list and the developers replied that the documentation was incorrect if the leading coefficient is not coprime to $$N$$.