Georgi Guninski on Sun, 01 Dec 2019 14:45:08 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Hypotheses on P(x) in zncoppersmith? |
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)