The problem that we want to address here is how to compute effectively with algebraic numbers and algebraic functions. Part of the algorithms presented here were studied and developed by Trevor J. Smedley for his thesis dissertation. His thesis and related papers are the main references for this chapter.

What do we mean by computation with algebraic numbers?

- Normalizing expressions, i.e. representing every algebraic
number of arithmetic expression involving algebraic numbers, into
a canonical, simplified form.
For algebraic numbers of order
*k*, all powers*k*or larger will be reduced. - Rationalize expressions. Remove the occurrence of the algebraic numbers in the denominator of expressions.
- Gcd computations.
- Polynomial factorization.
- Other polynomial operations, e.g. resultants.

There are deterministic conventional algorithms for all of the above problems, but these are, in some cases, very difficult to implement and always extremely expensive to run.

The heuristic algorithms presented in this chapter are two variations
of the same flavour.
In both cases we reduce our domain from polynomials over the integers
with the addition of algebraic numbers to a domain of polynomials over
the integers mod *n* and without algebraic numbers.
In the first method, the one described in Smedley et al., we select
the representation of so that it is easy to lift the results.
For the second method, we rely on the LLL algorithm for lifting the
results.
Complete algorithms for the first method are currently implemented and
used in Maple.

Let be an algebraic number defined by the polynomial
*p*(*x*) with
.
Without loss of generality we will assume that *p*(*x*) is an
primitive, irreducible polynomial over the integers of degree
2 or higher.
The degree of the algebraic number , is the degree of
the polynomial,
.
If the leading coefficient of *p*(*x*) is 1 or -1, then will be called an algebraic integer.

From the above definitions and the proposed mapping, it is obvious that should be selected so that , or that is a root of (or that is a factor of ).

*Example.*
Suppose we want to simplify , where is an
algebraic number of degree 3, i.e. *d* = 3.
We know that the answer will be of the form

If we choose to be a root of , the resulting signature for is typically a number as large as

It is not very difficult to find an *n* such that
for small
.
But first lets be a bit more precise.
Lets assume that
.
So
just to be able to lift the coefficients.
In particular,
to be able to lift the
last coefficient.
In summary this means that

(2*a*)^{d} < 2*n*

The procedure to select
and *n* witht the above conditions
is as follows:

You can experiment with other values for `a` by
changing its assignment, or with other expressions in
by changing the assignment to

tt S.

There is an alternative approach to solve this problem which does not require the searching of a suitable prime (which in turns requires a partial factorization). This alternative also resolves the problem of common denominators which are very difficult to estimate correctly. It is based on the LLL algorithm and proceeds as follows.

For some arbitrary expression, *e* involving an algebraic
number , we compute its signature using some prime
number *n*.
This prime number *n* is chosen so that the characteristic
polynomial *p*(*x*) has at least one linear factor .
(Obtaining the linear factors of a polynomial is
much easier than factoring.)
We assume that our expression *e* can be expressed in terms of
the algebraic number as

for rational numbers