Ideals of orders are of two types. All ideals are fractional and inherit from type RngOrdFracIdl. Integral ideals can have (the sub--)type RngOrdIdl. Some functions only apply to integral ideals and only ideals with the integral type can be prime. An ideal with fractional type but trivial denominator can be converted to have the integral type and any integral ideal can be converted to fractional type.
Ideals can be taken of orders over Z and orders defined over a maximal order. A few functions are not implemented for the latter.
Where an element or elements are returned from a function the elements are usually in the field of fractions if the ideal has the fractional type and in the order if it has integral type.
The general ideal constructor can be used to create ideals in orders of algebraic fields, as described below. Since ideals in orders are allowed to be fractional ideals, algebraic field elements are allowed as generators. Ideals can also be created how they are written on paper: as an element multiplied by an order.
Create the ideal x * O for element x and order O. If the ideal is integral it will be returned with the integral type.
Make the ideal I either fractional (first case where F is a field of fractions compatible with the order of I) or integral (second case where O is an order compatible with the order of I).
Given an order O, as well as anything that can be used to produce a sequence of elements of the field of fractions of O return the ideal generated by those elements. If the ideal is integral then it will be returned with the integral type.A single integer may be given in which case the principal ideal it generates will be returned. A matrix or a module over an order (ModDed) (or a matrix and ideals which the module could be created from) can be supplied as the basis for the resulting ideal. An optional second argument is a denominator given as an integer, (except when ideals are given).
> R<x> := PolynomialRing(Integers()); > f := x^4-420*x^2+40000; > K<y> := NumberField(f); > E := EquationOrder(K); > O := MaximalOrder(K); > elt := O ! (y^2/40+y/4); > elt in E; false > I := ideal< O | elt >; > I; Principal Ideal of O Generator: [0, 0, 1, 0] > FieldOfFractions(O)!!I; Principal Ideal of O Generator: O.3 > O!!$1 eq I; true
Some information describing an ideal can be retrieved.
The order O which the ideal I is of.
The denominator of the fractional ideal I. This is the smallest positive integer d such that d * I is an integral ideal.
A primitive element of an ideal I is an element a which is in I but not in the square of I. This function returns such an element a. UniformizingElement returns the primitive element of a prime ideal.
The index of the integral ideal I, when viewed as a submodule of the order O. This is the same as the cardinality of the finite quotient ring O/I.
The norm of the fractional ideal I. This returns the index of the ideal if the ideal is integral, and is defined on fractional ideals by multiplicativity so that the norm of I - 1 equals the reciprocal of the norm of I.
Given an ideal I of an order in some number field, the function returns the least positive integer contained in the ideal.
Given an ideal I, this function returns the least positive integer m if the ideal is integral or the least positive rational r if is fractional contained in I.
The absolute norm of the fractional ideal I. This returns the index of the ideal if the ideal is integral, and is defined on fractional ideals by multiplicativity so that the norm of I - 1 equals the reciprocal of the norm of I.
For an ideal I the coefficient height is defined to be the maximum integer occurring in the current representation of the ideal: If the ideal is given via two elements, this will be the maximal coefficient height of the generators, otherwise the maximal entry of the basis matrix.
For an ideal I the coefficient length is defined to be the size of the current representation: If the ideal is given via two elements, this will be the sum of the coefficient lengths of the generators, otherwise the sum of the entries of the basis matrix.
For a prime ideal I of an order O such that p ∈I returns the maximal exponent e such that Ie divides the principal ideal pO. If p is not given it is taken to be the minimal integer of I.
Computes the relative ramification index of the prime ideal I over the coefficient ring. To be more precise: Let I be an prime ideal of some order O with coeffcient ring o. Then I ∩o is an prime ideal p in o. The ramification index e = e(I|p) is the maximal exponent e such that Ie divides pO.
If I is a prime ideal of O, this function returns the finite field F isomorphic to O/I and the map O -> F.
Given a prime ideal I this function returns the relative degree f of the residue class field of the ideal I. To be more precise: Let I be a prime ideal in some order O with coefficient ring o. Then p := o ∩I is a prime ideal in o and the residue class field O/I is a finite extension of degree f=f(I|p) of the residue class field o/p.
Given an ideal I and a prime ideal p in an order O, returns the valuation vp(I) of I at p, that is, the number of factors p in the prime ideal decomposition of I. Note that, since the ideal I is allowed to be a fractional ideal, the returned value may be a negative integer.
The content of the ideal I, i.e. the maximal ideal of the base ring dividing I.
> R<x> := PolynomialRing(Integers()); > M := MaximalOrder(x^5 + 4*x^4 - x^3 + 7*x^2 - 1); > R<x> := PolynomialRing(M); > O := MaximalOrder(x^3 - 2); > M; Maximal Equation Order with defining polynomial x^5 + 4*x^4 - x^3 + 7*x^2 - 1 over Z > O; Maximal Order of Equation Order with defining polynomial x^3 - [2, 0, 0, 0, 0] over M > I := 19/43*M.4*O.3*O; > I; Fractional Principal Ideal of O Generator: 19/43*M.4*O.3 > Order(I); Maximal Order of Equation Order with defining polynomial x^3 - [2, 0, 0, 0, 0] over M > Denominator(I); 86 > Denominator(O.3); 2 > PrimitiveElement(I); 19/43*M.4*O.3 > Norm(I); Fractional Ideal of M Basis: [6859 0 0 0 0] [ 0 6859 0 0 0] [ 0 0 6859 0 0] [ 0 0 0 6859 0] [ 0 0 0 0 6859] Denominator: 159014 > Minimum(I); 19/43 > p := Factorization(3*M.2*O)[1][1]; > Valuation(I, p); 0
The basis of an ideal can be computed as well as related matrices.
For relative extensions, a different method is available:
Given an ideal I of an order O of the algebraic field F, this function returns a basis for I as a sequence of elements of F (if fractional), O (if integral) or the ring R if given.
Returns the basis matrix for the ideal I of the order O. The basis matrix consists of the elements of a basis for the ideal written as rows of rational coefficients with respect to the basis of O. The entries of the matrix are elements of Z for an integral ideal of an order over Z only or the field of fractions of the coefficient ring of O.
Returns the transformation matrix for the ideal I of the order O, as well as a denominator. The transformation matrix consists of the elements of a basis for the ideal written as rows of coefficients with respect to the basis of the order O. The entries of the matrix are elements of Z for an integral ideal of an order over Z or the field of fractions of the coefficient ring of O.
The coefficient ideals of the ideal I in a relative extension. These are the ideals {Ai} of the coefficient ring of the order of I such that for every element e ∈I, e = ∑i ai * bi where {bi} is the basis returned for I and each ai ∈Ai.
> Basis(I); [ 19/43*M.4*O.3, 19/86*M.4*O.1, 19/43*M.4*O.2 ] > Basis(I, NumberField(O)); [ 19/86*$.1^3*$.1^2, 19/86*$.1^3, 19/86*$.1^3*$.1 ] > BasisMatrix(I); [0 0 19/43*M.4] [19/86*M.4 0 0] [0 19/43*M.4 0] > TransformationMatrix(I); [M.1 0 0] [0 M.1 0] [0 0 M.1] 1
For an ideal I in some relative extension, return a Dedekind module over the coefficient ring with the "same" basis.
All ideals of maximal orders can be generated by one or two elements of the field of fractions of the order they are an ideal of.
Given a (fractional) ideal I of O, return a sequence containing two elements that generate I as an ideal. The elements will be in the order iff the ideal is integral, otherwise they will come from the field of fractions of O.
Given a (fractional) ideal I of O, return two elements of (the field of fractions of) O that generate I as an ideal.
Given an integral ideal I of O (a maximal order over Z), return two elements of O that form a two-element normal presentation for I, as well as an integer g such that I is g-normal.
> Generators(I); [ 19/43*M.4*O.3 ] > TwoElement(I); 19/43*M.4*O.3 19/43*M.4*O.3
Ideals may be tested for various properties and whether given elements lie in the ideal.
Returns true if and only if the fractional ideal I is integral.
Returns true if the ideal I is the zero ideal, false otherwise.
Returns true if the ideal I is the ideal generated by 1, false otherwise.
Returns true if and only if the ideal I is a prime ideal, and false otherwise. If I has the integral type and is not prime, the function also returns a proper (ideal) divisor.Currently, this function becomes very slow as the norm of the ideal becomes large.
SetVerbose("ClassGroup", n): Maximum: 5
Returns true if the fractional ideal I of the order O is a principal ideal, otherwise false. If I is principal, a generator (as an element of the field of fractions of O) is also returned.If it is known or easy to decide whether I is principal the function will return quickly. If it is necessary to compute the class group of O the function will be slower. If the generator is required this may cause the function to take longer as well.
Returns true iff the ramification index of the prime ideal P is greater than 1.
Returns true iff for any prime ideal Q lying above P in the order O, the ramification index of Q is greater than 1. P must be a prime ideal of the base ring of O or a prime number (if O is an absolute order).
Returns true iff the ramification index of the prime ideal P equals the degree of its order over the base field.
Returns true iff for any prime ideal Q lying above P in the order O, the ramification index of Q equals the field degree. P must be a prime ideal of the base ring of O or a prime number (if O is an absolute order).
Returns true if all primes dividing the discriminant the maximal order of the algebraic field K are totally ramified over the coefficient field of K.
Returns true if all primes dividing the discriminant of the maximal order O are totally ramified over the coefficient ring of O.
Returns true iff the ramification index of the prime ideal P is a multiple of the characteristic of the residue class field of P.
Returns true iff for any prime ideal Q of the order O lying above P, the ramification index e(Q|P) is a multiple of the characteristic of the residue class field of Q. P must be a prime ideal of the base ring of O or a prime number (if O is an absolute order).
Returns true iff the prime ideal P is not wildly ramified.
Returns true iff the prime ideal or integer P is not wildly ramified in the order O.
Returns true iff the ramification index of the prime ideal P is 1.
Returns true iff for all prime ideals Q lying above P in the order O, the ramification index of Q is 1. P must be a prime ideal of the base ring of O or a prime number (if O is an absolute order).
Returns true iff the inertia degree of the prime ideal P is the field degree.
Returns true iff the prime integer or ideal P in the base ring of the order O is inert, i.e. PO is an unramified prime ideal of O.
Returns true iff the prime ideal P is not the only prime ideal which lies above its intersection with the base ring of its order.
Returns true iff at least two prime ideals in the order O lie above the prime integer or ideal P of the base ring of O.
Returns true iff there are as many prime ideals lying above the intersection of the prime ideal P with the base ring of its order as the degree of the order of P.
Returns true iff as many prime ideals in the order O lying above the prime integer or ideal P of the base ring of O as the degree of O.
Ideals can be multiplied in several ways, divided and added. Powers of ideals, the least common multiple and the intersection of two ideals can also be calculated.
The product IJ of the (fractional) ideals I and J, generated by the products of elements in I and elements in J.
Given an element x of (or coercible into) a field of fractions F, and a (fractional) ideal I in the order of F, return the product of the ideal and the principal ideal generated by x.
The product of all ideals in the sequence or set L.
The quotient of the (fractional) ideals I and J of an maximal order O. This is the fractional ideal K of O with the property that J K=I.
For integral ideals I and J of some maximal order such that J divides I (or, equivalently, J is contained in I), return the integral ideal I/J.
Given an ideal I and an element x construct the fractional ideal I / x.
The sum of the (fractional) ideals I and J, generated by the sums of elements in I and elements in J.
The k-th power of the (fractional) ideal I (for an integer k). If I has integral type and k is negative the result will have fractional type.
Tests if the ideals I and J are equal.
Tests if the two ideals I and J of the same order are contained in each other. For invertible ideals this is equivalent to checking if J divides I,
Tests if the element E is actually in the ideal I. The element and the ideal have to be compatible, i.e., live in the same number field.
Return the least common multiple of ideals I and J. They must both be of the same maximal order.
The greatest common divisor of the ideals I and J of some maximal order of an algebraic number field.
For a matrix M with entries in some number field k, compute the gcd of all elements as principal ideals in the maximal order of k.
The intersection of the (fractional) ideals I and J. For ideal in the maximal order this is the same as the lcm.
The intersection of all ideals I of the sequence or set S. For ideals in some maximal order this is the same as the lcm.
The intersection of the ideal I with the compatible ring R. If R = Q an error will occur since ideals of Q cannot be created. If such information is required use Minimum instead. An ideal of R is returned.
A representative of the element a of an order O in the quotient O/I.
An element y such that y * E = 1 mod M where M is an integral ideal or an integer and E is an element of an order.
The colon ideal [I:J] or (I/J) is defined as { x∈F : x J ⊆I} where F is the field of fractions of the order the ideals I and J belong to.For ideals of a maximal order (or in general for invertible ideals) this is equivalent to I/J, otherwise only J*ColonIdeal(I, J) subset 1*Order(I) holds.
Given an ideal I, return an integral ideal J and a minimal positive integer d such that I = J/d.
It is possible to ask for the k-th root of an ideal where k is a positive integer.
Find the kth root of the ideal I if it exists.
Return true if the ideal I is a kth power of an ideal and the ideal it is a power of otherwise false.
Return the square root of the ideal I if I is square.
Return true if the ideal I is the square of an ideal and the ideal it is a square of otherwise false.
The factorization of an ideal into prime ideals and the divisors of an ideal can be determined.
SetVerbose("IdealDecompose", n): Maximum: 5
Given an order O and a rational prime number p or a prime ideal p of the coefficient ring of O, return a sequence of tuples consisting of prime ideals and exponents, according to the decomposition of p in O.
SetVerbose("IdealDecompose", n): Maximum: 5
Given an order O and a rational prime number p or a prime ideal p of the coefficient ring of O, return the decomposition type, ie. a sequence of tuples consisting of the degree of the prime ideals and their ramification index, according to the decomposition of p in O.
SetVerbose("IdealDecompose", n): Maximum: 5
Returns the prime ideal factorization of an ideal I in an order O, as a sequence of 2-tuples (prime ideal and integer exponent).
Return the ideals which divide the ideal I which must be of a maximal order.
For a non-zero ideal I of some maximal order, return the set of prime ideals p dividing I.
GaloisStable: BoolElt Default: false
CoprimeOnly: BoolElt Default: false
UseBernstein: BoolElt Default: false
For a sequence L of ideals in some maximal order (or of number field elements representing principal ideals), return the set of prime ideals dividing at least one of the ideals. If CoprimeOnly is given, the set returned will not in general be containing prime ideals, but will satisfy the following:If the number field is normal and if GaloisStable is given, then the set returned will be closed under the action of the galois group. Depending on the (unknown) factorisation pattern of the ideals, taking the Galois action into account will in general refine the coprime factorisation.
- Every ideal in L can be uniquely decomposed into a power product of ideals in the set returned
- The set is minimal and closed under gcd, ie. for two elements in the set, their gcd will be one.
In general, this function will first construct a coprime basis, and the factorise the result of this step.
If UseBernstein is given, then Dan Berstein's asymptoically fast algorithm ([Ber05], which runs in time essentially linear in #L) is used.
GaloisStable: BoolElt Default: false
UseBernstein: BoolElt Default: false
Given a sequence L of ideals in some maximal order, a coprime basis C for L is constructed. That meansIf the field is normal and if GaloisStable is given, the input sequence is supplemented by the action of the automorphism group, thus potentially refining the coprime basis.
- - every element in L has a unique representation as a power product with elements in C
- - C is closed under gcd, the ideals in C are pairwise coprime.
If UseBernstein is given then instead of the naive algorithm with quadratic complexity in #L, an asymptotically fast, almost linear algorithm by Dan Berstein is used, [Ber05].
GaloisStable: BoolElt Default: false
UseBernstein: BoolElt Default: false
Given a coprime basis in the sequence L, enlarge it by the ideal I, ie. enlarge L in such a way that L stays a coprime basis but allows the decomposition of I as well. If the ideals are in a normal field and if GaloisStable is given, then in addition of I all its Galois conjugates are inserted as well. Furthermore, a fractional ideal is always decomposed into the numerator and denominator ideal, ach of which is inserted independently.If UseBernstein is given then instead of the naive algorithm with quadratic complexity in #L, an asymptotically fast, almost linear algorithm by Dan Berstein is used, [Ber05].
Given sequences B of ideals of some maximal order and E of integers, compute the ideal ∏B[i]E[i].
Various other functions can be applied to ideals. In addition to those listed, the completion of an order at a prime ideal can also be taken (see Completion and Chapter p-ADIC RINGS AND THEIR EXTENSIONS).
Returns an element e of the order O such that (e1 - e) is in the ideal I1 of O and (e2 - e) is in the ideal I2. If a sequence of elements X and a sequence of ideals M is given then the element e will be such that (X[i] - e) is in M[i] for all i.
Returns an element e of the order O such that (e1 - e) is in the ideal I1 of O and the signs of the conjugates listed in L1 are the same as in L2.L1, a sorted sequence of integers 0<li<= r1, is meant to be formal product of infinite places. The signs of the li'th conjugate of e will be the same as the sign of L2[i].
For coprime integral ideals I and J return true and elements i∈I and j∈J such that i + j=1.
Given two integral ideals I and J in the same maximal order, find an element q in the field of fractions of this order such that qI is coprime to J.
Let I be an ideal in the absolute maximal order O of the number field K. Further, assume that the class group of O has been computed. The class group calculation will have chosen a set of ideal class representatives. This function returns the representative ideal for the ideal class to which I belongs.
Given an ideal I in an absolute order, returns the lattice determined by the real and complex embeddings of I.
The different of the (possibly fractional) ideal I of an order of an algebraic number field.
The codifferent of the ideal I. This will be the inverse of the different of I if I is an ideal of a maximal order.
Raw: BoolElt Default: false
SetVerbose("ClassGroup", n): Maximum: 5
An element mu of F, the field of fractions of the order of I, is an S-unit iff vp(mu) = 0 for all p not in S. This function returns the group of S-units of the prime ideals given either as a sequence S of ideals or as a product ideal I. The map from the group into the order containing the ideals is also returned.If Raw is true then a product representation of the units is returned instead. That means a sequence L of order elements is determined such that the S-unit group is contained in their multiplicative span. The S-unit group is represented as the Z-module of the exponent vectors for L that give rise to some S-unit. Formally we obtain the S-unit group as an abstract abelian group A, a map from A into some large RSpace and the sequence L.
> K := QuadraticField(10); > M := MaximalOrder(K); > U, mU := SUnitGroup(3*M); > U; Abelian Group isomorphic to Z/2 + Z + Z + Z Defined on 4 generators Relations: 2*U.1 = 0 > mU; Mapping from: GrpAb: U to Field of Fractions of M > u := mU(U.3); u; 7/1*M.1 - 2/1*M.2 > Decomposition(u); [ <Prime Ideal of M Two element generators: 3 $.2 + 1, 2> ]So u is indeed a 3 unit, as the factorization contains only prime ideals over 3. Next we do the same computation but using the Raw option:
> U, mU, base := SUnitGroup(3*M:Raw); > mU; Mapping from: GrpAb: U to Full RSpace of degree 14 over Integer Ring > mU(U.3); ( 0 2 1 0 0 0 0 0 0 0 -2) > PowerProduct(base, $1); 7/1*M.1 - 2/1*M.2 > base[2]^2 * base[3]^1 * base[11]^-2; 7/1*M.1 - 2/1*M.2This representation is of particular importance for large degree fields or fields with large units. To illustrate this, consider the following field from the pari-mailing list:
> K := NumberField(Polynomial([ 13824, -3894, -1723, 5, 1291, 1 ])); > L := LLL(MaximalOrder(K)); > C, mC := ClassGroup(L:Bound := 500); > U, mU, base := SUnitGroup(1*L:Raw); > logs := Matrix([Logs(x) : x in Eltseq(base)]); > mU(U.3)*logs; (2815256.998090806477937318458440358713392011019115562 -636746.05251910981832558348350489744160309616673457 -770882.44652629342064307574571528191509290934280166)As the logarithm of the absolute value of the real embeddings is of the order 106, we expect that a basis representation will have coefficients requiring roughly 106 digits. While it is feasible to compute them (using PowerProduct), this will take a long time.
Base: SeqEnum[RngOrdElt] Default: []
Given a description of the S-unit group as computed by SUnitGroup and a (multiplicative) map of the underlying number field, this function computes the induced map on the abstract abelian group.The argument S should be a sequence of ideals as in SUnitGroup. The argument SU should either be the map returned by SUnitGroup(S) as second return value - in which case Base is trivial (and not specified) or the second return value of SUnitGroup(S:Raw) in which case Base should equal the third computed value.
The argument Act must be any (multiplicative) function of the underlying number field or any order, that acts on the S-unit group.
On return, a endomorphism of the domain of SU is obtained.
Base: SeqEnum[RngOrdElt] Default: []
Given a description of the S-unit group as computed by SUnitGroup and a sequence of (multiplicative) maps of the underlying number field, this function computes the induced maps on the abstract abelian group.The argument S should be a sequence of ideals as in SUnitGroup. The argument SU should either be the map returned by SUnitGroup(S) as second return value - in which case Base is trivial (and not specified) or the second return value of SUnitGroup(S:Raw) in which case Base should equal the third computed value.
The argument Act must be a sequence of (multiplicative) functions of the underlying number field or any order, that acts on the S-unit group.
On return, a sequence of endomorphisms of the domain of SU is obtained.
Base: SeqEnum[RngOrdElt] Default: []
Given a description of the S-unit group as computed by SUnitGroup and a (multiplicative) map of the underlying number field, this function computes the induced map on the abstract abelian group.The argument S should be a sequence of ideals as in SUnitGroup. The argument SU should either be the map returned by SUnitGroup(S) as second return value - in which case Base is trivial (and not specified) or the second return value of SUnitGroup(S:Raw) in which case Base should equal the third computed value.
This function solves the discrete logarithm problem for the S-unit group and the algebraic number x. That is, an element in the abstract abelian group representing the S-unit group is computed which corresponds to x. If a list of algebraic numbers L is passed into this function, the discrete logarithm is computed for each of them.
> M := MaximalOrder(Polynomial([ 25, 0, -30, 0, 1 ])); > S := [ x[1] : x in Factorisation(30*M)]; > U, mU := SUnitGroup(S); > L := Automorphisms(NumberField(M)); > s2 := SUnitAction(mU, L[2], S); > s2; Mapping from: GrpAb: U to GrpAb: U > L[2](mU(U.2)) eq mU(s2(U.2));Now the same in Raw representation:
> R, mR, Base := SUnitGroup(S:Raw); > S2 := SUnitAction(mR, L[2], S:Base := Base); > [S2(R.i) : i in [1..Ngens(R)]]; [ R.1, R.1 - R.2, R.3, R.1 + R.3 - R.4, R.1 + R.5, R.1 + R.3 + R.7, R.1 - R.3 + R.6, R.8 ]If we combine SUnitAction with SUnitDiscLog we can solve norm equations:
> N := map<M -> M | x:-> L[1](x) * L[2](x)>; > NR := SUnitAction(mR, N, S:Base := Base);Now NR is the norm function with respect to the field fixed by L[2].
> SUnitDiscLog(mR, FieldOfFractions(M)!5, S:Base := Base); 2*R.5 > $1 in Image(NR); true > $2 @@ NR; R.2 + R.5 > PowerProduct(Base, mR($1)); -3/1*M.1 - 2/1*M.2 + M.4 > N($1); [5, 0, 0, 0]
Quotients of orders defined over maximal orders and their integral ideals can be formed resulting in an object with type RngOrdRes. Elements of such orders can be created and elementary arithmetic and predicates may be applied to them.
The creation of quotient rings and the functions which may be applied to them are described.
Creates the quotient ring Q=O/I of the order O. The right hand side of the constructor may contain an ideal or anything that the ideal constructor can create an ideal from.
Returns an abelian group and the map from the group into OQ. OQ must be a quotient of an absolute maximal order.
Return the denominator of the quotient ring OQ, i.e. I where OQ = O/I.
> I := Denominator(I)*I; > I; Principal Ideal of O Generator: 38/1*M.4*O.3 > Basis(I); [ 38/1*M.4*O.3, 19/1*M.4*O.1, 38/1*M.4*O.2 ] > Q := quo<Order(I) | I>; > Q; Quotient Ring of Principal Ideal of O Generator: [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 38, 0]] > Modulus(Q); Principal Ideal of O Generator: [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 38, 0]]
Functions for elements of the quotient rings are predominantly arithmetic.
Coerce the element a into the quotient OQ where a is anything that can be coerced into the order OQ is a quotient of.
A canonical representative of the element a (belonging to an order O) in the quotient ring O/I.
Returns true if and only if the quotient ring element a is the zero element of the quotient ring OQ.
Returns true if and only if the quotient ring element a is the one element of the quotient ring OQ.
Returns true if and only if the quotient ring element a is the minus one element of the quotient ring OQ.
Returns true if and only if the quotient ring element a has an inverse in the quotient ring OQ.
The coefficients of the quotient ring element a in the field of fractions of the coefficient ring of the order of the quotient ring containing a.
Given an element e in some order O, known modulo some ideal I, a common problem in several algorithms is to recover e, ie. a unique minimal element f∈O such that e - f∈I and f is as "small" as possible. An equally common variation would be to ask for some field element f/d with d an integer, such that f - de ∈I and f as well as d are small.
In the case of O being the ring of integers and I a power of a prime (ideal), this is usually done by moving to the symmetric residue system in the first case and by rational reconstruction in the second. Here, we use techniques based on the LLL algorithm as described in [FF00].
Since the method is more complicated than in the case of the integer ring, one first has to create a "reconstruction environment" of type RngOrdRecoEnv, which is subsequently used to reconstruct any number of elements.
Given a (prime) ideal p and an exponent k, initialize the reconstruction process for the ideal I=pk, that is, the object returned can be used to reconstruct elements from "approximations" modulo pk.
UseDenominator: BoolElt Default: false
Given an order element e, thought to be an approximation modulo pk where p and k are stored in the reconstruction environment R, return the unique minimal f in the same order such that e - g∈pk. Is UseDenominator is true, then a field element is computed, otherwise a ring element will be found.
Change the ideal I=pl stored in R to pk.
> f := Polynomial([1,1,1,1,1]); > M := MaximalOrder(f); > P := Decomposition(M, 11)[1][1]; P; Prime Ideal of M Two element generators: [11, 0, 0, 0] [2, 1, 0, 0] > C, mC := Completion(M, P:Precision := 10); > fC := Polynomial([c@ mC : c in Eltseq(f)]); > rt := Roots(fC); rt; > R := ReconstructionEnvironment(P, 10); > [Reconstruct((x[1]) @@ mC, R) : x in rt]; [ M.4, M.3, -M.1 - M.2 - M.3 - M.4, M.2 ] > [ Evaluate(f, x) : x in $1]; [ 0, 0, 0, 0 ]