Re: Very slow thue()

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

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