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)