Hypotheses on P(x) in zncoppersmith?
Georgi Guninski <[email protected]>
| Newsgroups | gmane.comp.mathematics.pari.devel |
|---|---|
| Message-ID | <CAGUWgD90sU1XhdKky-Y_2SKHriHxdip3_7cW8VL4iQcwVpqphg@mail.gmail.com> |
Initially posted on mathoverflow: https://mathoverflow.net/questions/231598/when-is-coppersmith-method-polynomial-factorization-related Main question: Does zncoppersmith allow P(x)=v * P0(x) for large integer $v$ and univariate polynomial P0? Suppose you want to factor $n$. Chose large integer $v$ and polynomial P0. Set: P(x)=v * P0 N= v * n X= d B= v*d P(x) is always divisible by v. Experimentally P need not be monic. Experimentally testing this never finishes, e.g.: ? p=nextprime(2^20);q=nextprime(2*p);n=q*p;v=n+1;P=x^2-1; zncoppersmith(v*P,v*n,p,p*v)