3
$\begingroup$

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?

$\endgroup$
3
  • $\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, 2016 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, 2016 at 8:34
  • $\begingroup$ @joro Where did you get the bound? $\endgroup$
    – Turbo
    Dec 31, 2018 at 18:10

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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