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?
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 ).
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
It is not very difficult to find an n such that
But first lets be a bit more precise.
Lets assume that
just to be able to lift the coefficients.
to be able to lift the
In summary this means that
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
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
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