Karim Belabas on Wed, 04 Dec 2019 02:26:07 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Hypotheses on P(x) in zncoppersmith? |
* Georgi Guninski [2019-12-01 14:45]: > 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? Yes, although this won't help for your application. The documentation was inaccurate: the stated (simple) condition X in terms of deg(P), N, B is only valid when N and the leading coefficient of P are coprime. In which case you may as well multiply P by lc(P)^(-1) mod N to reduce to P monic but the function will do it on its own in any case. When gcd(lc(P), N) > 1, there is no easy formula. The best I can come up with is the following d := deg P b := log_N B x := log_N X p := log_N gcd(lc(P), N) 1) p > d / (2d - 1) > 1/2 is large: we must have * x d < 2b - 1 2) p < d / (2d - 1) is small: we must have * x (d + p(1-2d)) < (b - p)^2 [reduces to the documented xd < b^2 if p = 0] * p < b < 1 - p + p / d Of course such details are moot since the application is to factor N, which can easily be done if gcd(lc(P), N) > 1 [ when the latter is N, we may as well reduce d since only P modulo N matters ] The documentation is now corrected in master. Cheers, K.B. -- Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17 Universite de Bordeaux Fax: (+33) (0)5 40 00 21 23 351, cours de la Liberation http://www.math.u-bordeaux.fr/~kbelabas/ F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP] `