Re: yet another rnfkummer() posting

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

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/