Karim Belabas on Sun, 07 Dec 2008 19:40:24 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Difficulty with binary quadratic equation solver |
* 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] `