Karim BELABAS on Thu, 11 Mar 1999 13:16:24 +0100 (MET)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: new bnfinit() bug

> Looks like this one was introduced in 2.0.12:
> ? setrand(1);bnfinit(x^3-4*x^2+x-3,3)
>   ***   bug in codeprime/smallbuchinit.

It's not a bnfinit bug, but a "smallbnfinit" bug [a simple "mathematical
compression" gimmick used to greatly reduce the size of bnf structures, so
that the missing information can be very quickly recomputed without starting
from scratch. For tables mostly]. 

The bug is in the coding of prime ideals (doesn't affect decoding, hence
existing structures). The _ideals_ produced by the PARI implementation of the
classical Buchman-Lenstra algorithm (primedec) are output in a deterministic,
reproducible order.

In 2.0.12, I removed the "setrand(1)" that were in the code around this
point. But in some rare cases (primes dividing the index + extra conditions),
the uniformizer returned (second generator) after using the random number
generator (which at this point is very inefficient anyway). The coding
depends on that generator, hence is not necessarily consistent.

I have a patch (remove random stuff, making the whole thing completely
deterministic), but I'm checking details (non trivial unrolled recursive
stuff in there).

Stay tuned...

Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
PARI/GP Home Page: http://hasse.mathematik.tu-muenchen.de/ntsw/pari/