> < ^ From:

< ^ Subject:

Dear Forum,

Lewis McCarthy asked:

I'm new to GAP (v3r4) and I have a couple of initial questions which I

haven't been able to answer with the manual thus far:

Unfortunately the manual is (yet) very short-spoken about these subjects,

particularly, since the part about algebraic extensions of fields is missing

(see my mail in the forum two weeks ago).

(1) Is there any built-in way to compute the resultant of two polynomials ?

Judging from the manual, there doesn't appear to be, but I just want to

make sure I haven't missed something. Otherwise I'll be coding my own.

There is a command 'Resultant' that computes the resultant of two

polynomials in the same polynomial ring by eliminating the indeterminate of

this ring. I.e.:

Resultant(f,g) is res_x(f(x),g(x)).

For computing resultants of multivariate polynomials, one can use iteraded

polynomial ring extensions, however (at the moment) the indeterminate to

eliminate must be the "topmost" indeterminate. Also computations in multiple

polynomial rings tend to be quite slow.

(2) What algorithms are used to factor polynomials over number fields in GAP ?

Since you asked this question, I suppose, you are familiar with the

algorithms. Therefore I will keep this description rather short. Feel free

to contaxct me personally, if you have further questions, that might be too

special for the general audience.

Let f be the minimal polynomial for the number field Q(alpha) and g\in

Q(alpha)[x] the polynomial to factor.

If deg f<=4 and degf*deg g<=20, then Trager's method will be used

(factoring the norm).

otherwise a Hensel approach is used. For tehse, the methods of Weinberger

and Lenstra (the '82 article which is in practice preferable to the method

suggested in the '83 article though theoretical complexity bounds might tell

something else) are used:

If a prime can be found (so far, 6 proimes are tested), modulo which f

remains irreducible, then Weinberger's method is used.

If not, and the coefficients coefficient bound is less then 10^400, then

Lenstras Approach is used. However, if coefficients become even larger, then

the LLL will choke on the coefficients (note that Lenstra requires a

significant higher bound than ~Weinberger); so Weinbergers methos is used

then again (i.e. simultaneous Henmsel lifting for all factors of f and final

recombination by Chinese Remainder methods).

I have not yet found much references in the literature about how to decide,

which methods to use (or how many primes to check). As computations become

extremely hard if f will split for al primes it is possibly worth event to

try to compute the galois group of f partially to see, whether there is a

chance to find a prime, modulo which f will remain irreducible.

Th heuristics are based on observations I made with polynomial

factorizations needed for identification of galois groups. Those

factorizations seem to be quite nasty in general, thus I think the algorithm

used should not perform too worse, however I have not yet made sufficient

observations to give even a hint, whether these heuristics are well chosen.

If you have specific problems on which GAPs algorithmm fails, I can send you

some further internal information on how to change the algorithm selection.

This text has been written over a rather slow telnet line, so please excuse

any typos.

Thanks for your help

You're welcome.

Alexander Hulpke

-- Lehrstuhl D fuer Mathematik, RWTH, Templergraben 64, 52056 Aachen, Germany,

eMail: Alexander.Hulpke@math.rwth-aachen.de

> < [top]