Re: long-standing bug

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

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/