From pari's implementation of [Coppersmith method](https://en.wikipedia.org/wiki/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?
> 
> 
> 



When is Coppersmith method polynomial? (Factorization related)
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$.


This is fixed in pari-master.


Discussion:
<http://pari.math.u-bordeaux1.fr/archives/pari-dev-1912/msg00002.html>


