From: bs@gauss.mitre.org (Robert D. Silverman)
Subject: Re: ALGEBRAIC NUMBER ARITHMETIC
Keywords: algebraic numbers, arithmetic
Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
Date: Thu, 30 Jul 1992 16:37:46 GMT

In article <1992Jul30.151149.12688@ugle.unit.no> ap@levangerhs.no (Andrei Prasolov) writes:
>Answering to <aet.712408532@munagin> 
>in <1992Jul29.163830.6443@ugle.unit.no> 
>I made a mistake. If we represent algebraic numbers
>only by their minimal polynomials, we cannot construct
>a correct arithmetic. Let us take the main root x of
					^^^^

There is no such animal as a 'main root'. There is only a
root and its conjugates. If alpha is a root of a polynomial,
then the field Q(alpha) is isomorphic to Q(alpha') where
alpha' is any of alpha's conjugates.  The map is controlled by the
Galois group.

Your assertion that one cannot construct a correct arithmetic if all
one has is the minimal polynomial is FALSE.

>        2                              
>f(X) = X -2 and the main root y of
>
>        4                
>g(Y) = Y -2. The algorythm says that z = x+y is 
 
The fields Q(x), Q(y) are different. The field Q(x+y) is an extension
of Q(x) and also an extension of Q(y). 

>a root of h(Z) = h_1(Z) * h_2(Z) where
>h_1(Z) = (Z^2+2)^2-2(2Z+1)^2 
>     has roots x+y, x-y, -x+iy, -x-iy, and
>h_2(Z) = (Z^2+2)^2-2(2Z-1)^2
>     has roots x+iy, x-iy, -x+y, -x-y.
 
Which algorithm? I'm afraid I don't follow you when you say "the" algorithm.

>The algorythm cannot determine, which polynomial
>from the two the number x+y is a root of.
 
So? This is totally irrelevent if working in Q(x+y). Your polynomial
h(Z) is not irreducible. You further confuse the issues involved by writing
terms like x + iy because the field Q(x) is purely real, while Q(y) is
imaginary.


I must confess that I don't understand what you are trying to say.

>   So the representation by pairs (irr. polynomial, interval)
>seems to be reasonable. One needs, however, the following
>two algorythms:
>  1. Separation of roots of a polynomial 
>           (there exists a lot of algorythms).
>  2. Decomposition of polynomials over Q into
>     prime factors (I am not aware of any). 
 
This is totally irrelevent.

Let me try to give a simple overview, along with an example.

Let f(x) be the minimal (irreducible) polynomial of alpha. Assume
f has degree d.

Any element of the (algebraic extension) field Q(alpha) may be represented
by a1 + a2 * alpha + a3* alpha^2 + ....  a_d alpha^(d-1).  This element is
an algebraic number. I use the notation a = [a1,a2,...a_d] to represent
one such number. Now, to perform arithmetic [let's say multiplication] on
a and b [a*b = [a1,a2,...a_d] * [b1,b2... b_d] ] one does this as one would
ordinary multiplication of two polynomials in alpha subject to the simplifying
side condition f(alpha) = 0.

For example. Consider Q(alpha = sqrt(2)) with f(x) = x^2 - 2. 
Now, (a1 + a2 alpha)*(b1 + b2 alpha) = a1 b1 + (a2 b1 + a1 b2) alpha + a2 b2 alpha^2.

Use the fact that alpha^2 = 2 and this simplifies to:

a1 b1 + 2 a2 b2 + (a2 b1 + a1 b2) alpha.


Where's the problem???? Basic arithmetic in algebraic number fields [e.g.
addition subtraction, multiplication] is trivial. Division is a little more
complicated because one must find a representation for an inverse via (say)
the extended Euclidean algorithm or by linear algebra.

Now arithmetic in the ring of integers of an extension field Q(alpha) can
get more complicated, because one must find an integral basis for the ring.
It is currently an open field of study to find good algorithms for doing so
when the field discriminant is large.

I hope this clarifies things.
--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"