Operations on Structures#

The majority of functions for quadratic fields and orders apply identically to number fields and orders in general. The functions which exist only for quadratic fields and orders are listed here along with those which deserve a special mention.

AssignNames(~F, [s]): FldQuad, [ MonStgElt ])#
AssignNames(~O, [s]): RngQuad, [ MonStgElt ])#: Procedure to change the name of the generator of a quadratic field \(F\) or an order \(O\) in a quadratic field to the string \(s\). Elements of the quadratic field \({\mathbb{Q}}(\sqrt{d})\) with \(m\) squarefree will be printed in the form 1/b*(x + y*s), where \(b, x, y\) are integers. Similarly, for an order \(O\) of conductor \(f\) in a quadratic field elements will be printed in the format x + y*s. This procedure only changes the name used in printing the elements of \(F\) or \(O\), it does not make an assignment to an identifier \(s\). To do this, use an assignment statement, or angle brackets when creating the field or order: F<s> := QuadraticField(-3);. Note that since this is a procedure that modifies \(F\) or \(O\), it is necessary to have a reference ~ in the call to this function.

Name(F, 1): FldQuad, RngIntElt -> FldQuadElt#
Name(O, 1): RngQuad, RngIntElt -> RngQuadElt#: Given a quadratic field \(F\) or one of its orders \(O\), return the element which has the name attached to it, that is, return \(\sqrt{d}\) in the field, or \(f \epsilon_d\) in a suborder of the maximal order or \(f \sqrt{d}\) in a suborder of the equation order.

FundamentalUnit(K): FldQuad -> FldQuadElt#
FundamentalUnit(O): RngQuad -> RngQuadElt#: A generator for the unit group of the order \(O\) or the maximal order of the quadratic field \(K\).

Discriminant(K): FldQuad -> RngIntElt#: The discriminant of the field \(K\) which is only defined up to squares. The discriminant will be the discriminant of the polynomial or better.

Conductor(K): FldQuad -> RngIntElt, [RngIntElt]#: The conductor of the field \(K\) which is the order of the smallest cyclotomic field containing \(K\) and a sequence containing the ramified real places of \(K\).

Conductor(O): RngQuad -> RngIntElt#: The conductor of the order \(O\), which equals the index of \(O\) in the maximal order.

Ideal Class Group#

The function ClassGroup is available for number fields and orders in general but a different and faster algorithm is used by default for the quadratics. All of the algorithms, except for the sieving method described in [Jacobson, Jr., 1999] which uses the multiple polynomial quadratic sieve (MPQS), are based on binary quadratic forms, see ClassGroup in Chapter Binary Quadratic Forms for details.

ClassGroup(K): FldQuad -> GrpAb, Map#

ClassGroup(O): RngQuad -> GrpAb, Map#

FactorBasisBound: FldReElt                           Default: 0.1
ProofBound      : FldReElt                           Default: 6
ExtraRelations  : RngIntElt                          Default: 1
Al              : MonStgElt                          Default: "Automatic"
verbose         : ClassGroupSieve                    Default: Verbose : 5

The class group of a maximal order \(O\) or the maximal order of the quadratic field \(K\), as an abelian group. The function also returns a map between the group and the power structure of ideals of \(O\) or the maximal order of \(K\). The parameter Al can be set to "Sieve" or "NoSieve" to control whether the sieving algorithm is used or not; by default it is used when the discriminant is greater than \(10^{20}\). For more details on the parameters see ClassGroup in Chapter Binary Quadratic Forms.

ClassNumber(K): FldQuad -> RngIntElt#

ClassNumber(O): RngQuad -> RngIntElt#

FactorBasisBound: FldReElt                     Default: 0.1
ProofBound      : FldReElt                     Default: 6
ExtraRelations  : RngIntElt                    Default: 1
Al              : MonStgElt                    Default: "Automatic"

The class number of the maximal order \(O\) or the maximal order of the quadratic field \(K\).

PicardGroup(O): RngQuad -> GrpAb, Map#

PicardNumber(O): RngQuad -> RngIntElt#

FactorBasisBound: FldReElt                     Default: 0.1
ProofBound      : FldReElt                     Default: 6
ExtraRelations  : RngIntElt                    Default: 1
Al              : MonStgElt                    Default: "Automatic"

The picard group (the group of the invertible ideals of \(O\) modulo the principal ones) of the order \(O\) or the size of this group. PicardGroup also returns a map from the group to the ideals of \(O\).

Example: Quad Sieve (ex-a05688)#

We give examples of class group calculations using sieving. We also show the use of the mapping between the group and the set of ideals. First a field with negative discriminant.

> D:=-(10^(30) + 3 );
> K := QuadraticField(D);
> time G, m := ClassGroup(K : Al := "Sieve");
Time: 10.750
> G, m;
Abelian Group isomorphic to Z/125355959329602
Defined on 1 generator
Relations:
    125355959329602*G.1 = 0
Mapping from: GrpAb: G to Set of ideals of Maximal Order of K
> m(G.1);
Ideal
Two element generators:
    385706622580333
    148769598702327446467038390888*$.2 + 307255216496036
> $1 @@ m;
G.1

Run in calculator

And now a field with positive discriminant.

> K := QuadraticField(NextPrime(10^24));
> time G, m := ClassGroup(K : Al := "Sieve");
Time: 3.330
> G, m;
Abelian Group isomorphic to Z/3
Defined on 1 generator
Relations:
    3*$.1 = 0
Mapping from: GrpAb: G to Set of ideals of Maximal Equation Order of K
> m(G.1);
Ideal
Two element generators:
    3847
    $.2 + 616
> $1 @@ m;
G.1
> IsPrincipal($2^3);
true

Run in calculator

QuadraticClassGroupTwoPart(K): FldQuad -> GrpAb, Map#

QuadraticClassGroupTwoPart(O): RngQuad -> GrpAb, Map#

QuadraticClassGroupTwoPart(d): RngIntElt -> GrpAb, Map#

Factorization: RngIntEltFact                    Default: []

Use the Bosma-Stevenhagen algorithm to compute the 2-part of the class group of a quadratic order. Returned are: an array of forms that generates the 2-part and an array that gives the orders of the respective elements. The Factorization of the given discriminant can be given as additional information.

Example: qcgtp (ex-53f1e4)#

> G, f := QuadraticClassGroupTwoPart(33923894057872); G;
Abelian Group isomorphic to Z/2 + Z/2 + Z/2 + Z/4 + Z/16 + Z/16
> Random(G);
11*G.1 + 2*G.2 + G.3 + G.4 + G.6
> f($1);
<-1212992,3947508,3780131>
> G, f := QuadraticClassGroupTwoPart(QuadraticField(33923894057872)); G;
Abelian Group isomorphic to Z/2 + Z/8 + Z/16

Run in calculator

Norm Equations#

For imaginary quadratic fields, (that is, for quadratic fields \({\mathbb{Q}}(\sqrt m)\) with \(m < 0\)), the function NormEquation is provided specially for quadratics to find integral elements of a given norm. For real quadratic fields conics are used, see Section Finding Points for details.

NormEquation(F, m): FldQuad, RngIntElt -> BoolElt, SeqEnum#

NormEquation(F, m: parameters): FldQuad, RngIntElt -> BoolElt, SeqEnum#

NormEquation(O, m): RngQuad, RngIntElt -> BoolElt, SeqEnum#

NormEquation(O, m: parameters): RngQuad, RngIntElt -> BoolElt, SeqEnum#

Factorization: [<RngIntElt, RngIntElt>]                    Default: 
All          : BoolElt                                     Default: true
Solutions    : RngIntElt                                   Default: All
Exact        : BoolElt                                     Default: false
Ineq         : BoolElt                                     Default: false
verbose      : NormEquation                                Default: Verbose : 1

Given quadratic field \(F\) and a non-negative integer \(m\), return true if there exists an element \(\alpha\) in the ring of integers \(O_F\) of \(F\) with norm \(m\), and false otherwise. Instead of searching the maximal order \(O_F\) it is possible to search any suborder \(O\) of \(O_F\) for such element \(\alpha\) by supplying \(O\) as a first argument. For imaginary quadratic fields the method used is constructive (it uses Cornacchia’s algorithm, see [Cohen, 1993] section 1.5.2), and if the value true is returned then a solution \([x]\) is also returned as a second return value. Note that if the discriminant \(F={\mathbb{Q}}(\sqrt{d})\) with \(d\equiv1\bmod4\) (and squarefree) this function searches for a solution in integers to \(x^2+y^2d=4m\) (and the solution \(\alpha={x+y\sqrt{d}\over 2}\) is returned), whereas for \(d\equiv 2, 3\bmod4\) a solution \(\alpha=x+y\sqrt{d}\) with \(x^2+y^2d=m\) in integers \(x, y\) is returned, if it exists. In an order of conductor \(f\) a search is conducted for a solution to the same equation with \(d\) replaced by \(f^2d\). Note that a version of NormEquation with integer arguments \(d\) and \(m\) also exists (see Section The Solution of Modular Equations). Unless \(m\) is the square of an integer, the factorization of \(m\) is used by the algorithm; if it is known, it may be supplied as the value of the optional parameter Factorization to speed up the calculation. A verbose flag can be set to obtain some information on progress with the computation (see SetVerbose).

For real quadratic fields the same algorithm is used as for the general number fields. The last \(4\) parameters refer to this algorithm. See Section Solving Norm Equations for a description.

Example: Norm Equation (ex-6e8332)#

> d := 302401481761723680;
> m := 76814814791186002463716;
> Q<z> := QuadraticField(-d);
> O<w> := sub< MaximalOrder(Q) | 6 >;
> f, s := NormEquation(O, m);
> s, Norm(s[1]);
406 + 1008*w 76814814791186002463716

Run in calculator