Re: Hypotheses on P(x) in zncoppersmith?

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

* Georgi Guninski [2019-12-04 09:15]:
> On Wed, Dec 4, 2019 at 3:26 AM Karim Belabas
> <Karim.Belabas@math.u-bordeaux.fr> wrote:
> 
> > 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)
> >
> 
> Your constraints are so restrictive I am not sure
> they are ever satisfiable.
> Do you have explicit N,P with gcd(N,lc(P))>1 where
> zncoppersmith finds root?

Sure. Here's a "random" example in the "small p" category [ 2) in my original
message ]

q = nextprime(10^20);
N = q * nextprime(10^10) * nextprime(10^30) * nextprime(10^50);
P = q * t + 100000000189172653204751006593737760787542892542935566160916650706339174019956544019987983467739604695370082353

p = log(q) / log(N);
b = 1/2;
x = 0.1;

? zncoppersmith(P, N, N^x, sqrtint(N))
%1 = [-11987937]

? gcd(subst(P,t,%1[1]), N)
%2 = 10000000000000000003900000000000000000000000000015100000000000000005889

? x * (1 + p*(1-2)) - (b - p)^2   \\ negative
%3 = -0.019421487604037331500073537357409660596

I'm not claiming that the feature is very useful, just that this is supported
with no extra cost in the implementation. (And that the documentation is now
correct.)

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