Karim BELABAS on Sun, 8 Sep 2002 17:52:06 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: yet another rnfkummer() posting |
On Sat, 7 Sep 2002, Igor Schein wrote: > On Sat, Sep 07, 2002 at 03:39:31PM +0200, Karim BELABAS wrote: > > I'm afraid you will have to re-run your regression suite now. > > 1 more type of bug is still present: > > ? setrand(6);rnfkummer(bnrinit(bnfinit(quadpoly(3409,y),1),25,1),[5,1;0,1]); > *** bug in isvirtualunit, please report [and later:] > ? setrand(1745131910);rnfkummer(bnrinit(bnfinit(quadpoly(3413,y),1),25,1),[5,1;0,1 ]); > *** not an n-th power in idealsqrtn. [and later:] > ? setrand(5);rnfkummer(bnrinit(bnfinit(quadpoly(440,y),1),109,1),[3,1;0,1]); > enters infinite loop. All three are gone now. I think I owe you an explanation for what I was trying to do, and the ensuing disasters. 1): I noticed that: * the bnf structure stored (a) a factorbase of prime ideals, (b) a permutation of the factorbase. * bnfinit(,3) was storing the _permuted_ factorbase, forever losing the permutation. bnfmake() restored the bnf with (a) a permuted factorbase, (b) the identity permutation. So I gathered the precise ordering of the bnf factorbase was irrelevant [ besides, nothing was documented to the contrary in the source code or elsewhere ]. I then changed the bnf format to directly store the permuted factobase and be done with the permutation, which removed a number of useless indirections, and a useless component from an already complicated object. Unfortunately, my assumption was wrong. It was in fact essential for _tough_ instances of bnfisprincipal(), that the factorbase in bnf would be sorted according to the underlying rational primes [ in most cases it would not matter ]. rnfkummer() is a tough testground for isprincipal(), especially now that it can treat much larger examples than before, and soon problems started to appear. 2): Cancelling my patch was a bad idea, since the bnf produced by bnfinit(,,3) / bnfmake did (sometimes) produce incorrect output in isprincipal. So I started fixing isprincipal, so that it would not rely on factorbase ordering. isprincipal operates by multiplying the given ideal by random products, pseudo-LLL-reducing, and trying to factor the result on the prime ideal factorbase. The factorbase ordering mattered in a specific optimization, that enabled the trial division code to quickly detect that the given ideal J was not smooth, but that J/n was, for some rational number n. Since idealred insists that its ouput be integral, and cancels the denominators, it often produces such ideal, when the base field is not Galois. Removing the optimization, I started getting infinite loops and ideals that could not possibly be factored (quite rarely, but still). 3) So I decided to reuse the existing bnfinit code [which builds and uses the factorbase in the first place], which in particular never calls idealred, but a private version returning 'm' a pseudo-minimum in J instead of 'numerator( J / m )'. In that case, the problem does not occur. But for that I had to remove most global variables, and rebuild in isprincipal() the necessary factorbase information that was discarded at the end of bnfinit(). Etc... I hope the nightmare is over now. Karim. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathematiques, Bat. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud Email: Karim.Belabas@math.u-psud.fr F-91405 Orsay (France) http://www.math.u-psud.fr/~belabas/ -- PARI/GP Home Page: http://www.parigp-home.de/