Re: Very slow thue()

[Georgi Guninski <guninski@guninski.com>]

Thanks you for the information.

Got confused because some other thue equations
were faster with much bigger RHS.

On Thu, May 08, 2014 at 06:13:47PM +0200, Karim Belabas wrote:
> * Georgi Guninski [2014-05-08 16:01]:
> > In this case thue() didn't finish in about 30 minutes,
> > is this normal?
> > 
> > ? a=41 * 113 * 241 * 569
> > %9 = 635318657
> > ? th=thueinit(x^4+1)
> > %10 = [[x^4 + 1, 1, 1], 4.000000000000000000]
> > ? so=thue(th,a^5)
> 
> Given our implementation, yes.
> 
> You're in the "trivial case" r1 = 0 (the number field has no real place)
> where the Bilu-Hanrot method does not apply: if f(x,y) = a, we directly have
> 
>   |x| < C * a^(1/deg f)
> 
> for some small effective C(f) (and this is essentially sharp). In your
> case, this trivial bound yields
> 
>   |x| <= 142644328629
> 
> For each such value, we must check whether the univariate polynomial
> f(x,Y) - a has integer roots. Which will take some time...
> 
> Here, the generic method is wasteful, you can find directly the set of
> solutions by solving
> 
>   X^2 + Y^2 = a
> 
> then restricting to the X,Y which are both squares, so 
>   [37483800763, 100380347806]
>   [84497381381, 85132700038]
> up to signs.
> 
>   L = bnfisintnorm(bnfinit(x^2+1),a^5);
>   for(i=1,#L, [a,b]=Vec(L[i]); \
>     if (issquare(abs(a),&a) && issquare(abs(b),&b), print([a,b])))
> 
> Cheers,
> 
>     K.B.
> --
> Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
> Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
> 351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
> F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
> `