Re: Difficulty with binary quadratic equation solver

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

* Bill Allombert [2008-11-30 13:42]:
> On Fri, Nov 28, 2008 at 09:36:47AM -0700, Kurt Foster wrote:
> > for which the field discriminant N = 5, the index m is 2, U =  
> > (B.fu)^2, the smallest value of k is 3, and plowing through the  
> > calculations by hand shows that there are two "inequivalent" solutions
> > 
> > [x,y] = [1,1] and [-5, -2]
> > 
> > For a given positive fundamental discriminant N and index m > 1,  
> > determining the exact smallest value of k for which U^k is in O has  
> > proven to be rather exasperating, although certain multiples of it are  
> > easy to find.  I've dug into it a fair bit, but I'm sure this is a  
> > known calculation.  Can someone provide a reference?
> 
> Well, we can use the ray class number formula that give the ray class number
> in term of the class number:
> 
>    h_f=h*Phi(f)/phi(f)/k

That's correct. But since we must check

  (+/-)U^j*L[i], for 0 <= j <= k-1

anyway, we can also just compute U^j for j = 1, 2, ... stopping as soon as
we land in O, i.e. have second coordinate in K.zk representation
(= algtobasis) divisible by f.

This translates into an equally simple criterion in t_POLMOD
(= basistoalg) form, i.e. some divisibility property of
polcoeff(lift(U), 1).).

My guess is that this part would be much faster ( and negligible compared to
the rest in any case, granted :-)

    K.B.

P.S:

> So the following should compute k:
> 
>   K=bnfinit(x^2-b*x+a*c);
>   B=bnrinit(K,K.index);
>   k=K.no*B.bid.no/(eulerphi(K.index)*B.no);

In current svn,

   bid = idealstar(K,K.index);
   k = K.no*bid.no/(eulerphi(K.index)*bnrclassno(K,bid));

will be faster than the above. Current svn only since for some strange
reason, older versions no not accept (much richer) "bid" structures when
a module is requested.

--
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-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`