Re: Pell's equations and beyond

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

Hi Denis,

* Denis Simon [2023-12-19 16:04]:
> If norm(u) = 1, is there a quick way to test whether this u is a
> square or not ?

The problem with the quadclassunit approach is that, as it stands,
you don't get u. (If you write down u, then it becomes a O(D^{1/2}) algorithm.)

With some effort, the implementation could be changed to get u as a product 
of S-units. In that case, one could easily prove it's *not* a square by a few
modular tests, which is enough for our application. (If it's a square, I
don't know how to prove that with decent complexity ... But since GRH is
true, this won't happen)

Cheers,

    K.B.

> Denis.
> 
> ----- Mail original -----
> > De: "Karim Belabas" <Karim.Belabas@math.u-bordeaux.fr>
> > À: "Kurt Foster" <drsardonicus@earthlink.net>
> > Cc: "Pari Users" <pari-users@pari.math.u-bordeaux.fr>
> > Envoyé: Mardi 19 Décembre 2023 10:06:03
> > Objet: Re: Pell's equations and beyond
> 
> > * Kurt Foster [2023-12-19 01:28]:
> > [...]
> >> If D is composite, and all its prime factors are congruent to 1 (mod 4), I
> >> don't know how to tell in general whether norm(u) is +1 or -1 other than by
> >> calculating u.
> > [...]
> > 
> > In the 'master' branch:
> > 
> >  quadclassunit(D).normfu
> > 
> > If the result is 1, the result is conditional on the GRH. The complexity
> > is D^ε for any ε > 0 (writing down u is in D^{1/2} in the worst case)
> > 
> > Cheers,
> > 
> >    K.B.
> > --
> > Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
> > Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
> > http://www.math.u-bordeaux.fr/~kbelabas/
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/