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?

  • $\begingroup$ Coppersmith mentions integer factorization in his second paper on the topic: link.springer.com/chapter/10.1007%2F3-540-68339-9_16 $\endgroup$ Feb 19 '16 at 16:31
  • $\begingroup$ @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. $\endgroup$
    – joro
    Feb 20 '16 at 8:34
  • $\begingroup$ @joro Where did you get the bound? $\endgroup$
    – 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$.

This is fixed in pari-master.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.