Re: Hypotheses on P(x) in zncoppersmith?

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* 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]
`