Re: bnfinit - algorithm in use, timings

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

On Tue, 22 Jan 2002, SockeSchuhRegel wrote:
> Somebody told me the algorithm used in pari would be probabilistic?

This is correct.

> Is pari using the random squaring method (McCurley, Buchmann, etc.) or is
> it a generalization of the NFS (Jacobsen Jr.) or am i completely on the
> wrong way?

PARI uses (an improved version of) the algorithm described in Henri Cohen's
book (GTM 138) [ so only McCurley/Buchmann, no NFS ].

The deterministic part looks for elements of small norm in the various prime
ideals; for small fields, it produces most of the relations and is the most
time-consuming part.

The random part uses random products of a few small prime ideals (the
"subfactorbase", usually about 3 or 4 ideals, raised to powers < 16)
multiplied by a single prime in the factorbase. The resulting ideal is then
LLL-reduced in various directious (for various twisted T2-norms).

> i'm new to this subject (number theory), so please forgive me for asking
> simple questions!(i'm no mathematician, which makes the situation even
> worse)  I would like to know which algorithm is used within pari for
> bnfinit and why the output timing is so wide spread even using comparable
> large polynoms coefficients:(for example: x^3 - 1348000^3 - 1 => 2176s
> while x^3 - 1349000^3 -1 take only 178s)

Using the latest stable release, pari-2.1.3, on my PIII 1GHz (+ 80MB stack).
I get analogous timings to yours (29 min and 3min respectively).

The stable version uses more conservative heuristics, and is generally much
less efficient than the development version since most improvements are not
backported (only bug fixes are). So I double checked the timing using
pari-2.2.2.ALPHA: I get 5mn 30 s and 3mn respectively, which is much more
sensible.

Cheers,

    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/