Number Fields and Algebraic Numbers
The Standard Representation of Algebraic Numbers
Representing field elements as coefficient vectors relative to a power basis or integral basis, with a common denominator.
Engineering / MathematicsNumber Fields and Algebraic Numbers2 min readKV-MATH-0575
The standard representation writes a field element as a polynomial in the generator, stored as a coefficient vector with a common denominator. It is compact, exact, and the default for almost all computation.
The representation
- Power basis
- Powers of the generator. Natural and immediate from the presentation, but generally not a basis of the maximal order.
- Integral basis
- A basis of the maximal order. Required for ideal arithmetic and for anything involving integrality.
- Denominator
- Kept in lowest terms. Its growth is the main hygiene concern.
Operations
| Operation | Method | Cost |
|---|---|---|
| Addition | Clear to a common denominator, add coefficientwise | O(n) plus a denominator GCD |
| Multiplication | Polynomial product, reduce modulo the defining polynomial | O(n^2) |
| Inversion | Extended Euclidean against the defining polynomial | One polynomial GCD |
| Equality | Compare after reducing denominators to lowest terms | O(n) |
Denominator hygiene
Multiplication in detail
Multiplication in the power basis is a polynomial product followed by reduction modulo the defining polynomial. Precomputing the reduction of each power from degree n up to 2n - 2 turns the reduction into a fixed linear combination.
Integrality testing
An element is an algebraic integer exactly when its coordinates relative to an integral basis are integers — that is, when the denominator is one. Relative to a power basis, no such simple test exists, which is a principal reason integral bases are computed.
Relation to other representations
The standard representation is exact and compact but hides analytic information. Sizes and signs require the conjugate vector representation; traces, norms and characteristic polynomials are most easily obtained from the matrix representation.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 4.2.2. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.