Karim BELABAS on Sun, 8 Sep 2002 21:11:00 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: long-standing bug |
On Sat, 7 Sep 2002, Karim BELABAS wrote: > On Fri, 6 Sep 2002, Igor Schein wrote: > > ? allocatemem() > > *** Warning: doubling stack size; new stack = 16000000 (15.259 Mbytes). > > ? setrand(1);rnfkummer(bnrinit(bnfinit(quadpoly(-9748,y),1),1,1),matdiagonal([3,1])); > > *** sorry, buchxxx couldn't deal with this field PLEASE REPORT!. > > More natural way to reproduce the problem: > > setrand(1); bnfinit(x^4 - 2437*x^2 + 5938969) > > [the random seed doesn't seem to be important] > > > The *beauty* of this bug is that it goes as far back as version > > 2.0.14. Looks like it could be a genuine failure of Buchmann > > algorithm. > > of our implementation thereof... > > I'm investigating this. setrand(1); bnfinit(x^4 - 2437*x^2 + 5938969,,[0.3,0.3,5,3,1,5]) works [also in the stable version]. The important parameter here is the '5' at the end (minimum size for the subfactorbase). [ Side Note: out of the 6 "technical parameters", 2 are rather useless (#rel / ideal in small norm phase, and #extra relations), and one is deprecated [ignored] ] After my CVS patch, it works without fiddling with the technical parameters. Background: The standard index calculus algorithm chooses a subfactorbase to form random products, with which we try to "smooth out" the elements of our factorbase, in order to produce relations. We start with about 3 elements in there (by default), then increase that number if we are going nowhere (at most twice before giving up and increasing the factorbase itself). The old strategy to fill subfactorbase was: take prime ideals of increasing norm, unramified, and such that no rational prime would factor on the subfactorbase. The new strategy is: as above for the initial subfactorbase, but when increasing the size, use the permutation of the factorbase, which is updated after each HNF reduction of the relation set. The permutation is such that "good" generators (the ones between which we want to find relations) end up first, followed by generators dependant from the first ones, followed by trivial generators. Since we increase the subfactorbase very late in the algorithm (hundreds of relations have been found), we have a lot of information, hence the subgroup generated by the subfactorbase tends to be very large, whereas the first 5 or 6 primes of small norm might all be principal! I think this is a relatively harmless patch, since the "increase subfactorbase" code is almost never triggered. So it shouldn't be detrimental to efficiency on average. 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/