Operations on Elements

Contents

Order of an Element

It is possible to determine the order of an element of a generic group with first calculating the structure of the group. The order function involves the use of one of several algorithms:

--
an improved baby-step giant-step algorithm, due to J. Buchmann, M.J. Jacobson, E. Teske [BJT97],
--
the Pollard--Rho method based algorithm, described above [Tes98a].

When computing the order of an element whose lower and upper bounds are known, or where lower and upper bounds for the group order are known, the following two algorithms have been shown to be significantly faster than the two algorithms mentioned above.

--
the standard baby-step giant-step Shanks algorithm,
--
another variant of the Pollard--Rho method which is due to P. Gaudry and R. Harley [GH00].

To avoid confusion we will distinguish the algorithms due to Teske et al and name them the T baby-step giant-step algorithm and the T Pollard--Rho algorithm respectively. The Pollard--Rho algorithm has smaller space requirements than the baby-step giant-step algorithm, so it is recommended for use in very large groups.

In all cases, if the group order is known beforehand, the element order is computed using this knowledge. This is a trivial operation.

Order(x) : GrpAbElt -> RngIntElt
Order of the element x belonging to an fp-abelian group. If the element has infinite order, the value zero is returned.

Example GrpAb_DiscreteLog (H75E10)

We compute the orders of some elements in the group Z2 x Z3 x Z4 x Z5 x Z. 
> G<[x]> := AbelianGroup([2,3,4,5,0]);
> Order( x[1] + 2*x[2] + 3*x[4]);
30
> Order( x[1] + x[5] );
0
Order(g: parameters) : GrpAbGenElt -> RngIntElt
    ComputeGroupOrder: Bool             Default: true
    BSGSLowerBound: RngIntElt           Default: 0
    BSGSStepWidth: RngIntElt            Default: 0
Assume that g is an element of the generic abelian group A. This functions returns the order of the element g. Note that if UseRepresentation is set to true for A, then this is a trivial operation.

If the parameter ComputeGroupOrder is true, the order of A is computed first (unless it is already known). The order of g is then computed using this knowledge; this last computation is trivial.

If ComputeGroupOrder is false, the order of g is computed using the T baby-step giant-step algorithm.

BSGSLowerBound and BSGSStepWidth are parameters which can be passed to the baby-step giant-step algorithm.

BSGSLowerBound sets a lowerbound on the order of the element g, and BSGSStepWidth sets the step-width in the algorithm.

Order(g, l, u: parameters) : GrpAbGenElt, RngIntElt, RngIntElt -> RngIntElt
    Alg: MonStg                         Default: "Shanks"
    UseInversion: BoolElt               Default: false
Assume that g is an element of the generic abelian group A such that the order of g or the order of A is bounded by u and l. This function returns the order of the element g.

If the parameter Alg is set to "Shanks" then the generic Shanks algorithm is used, and when Alg is set to "PollardRho", the Gaudry--Harley Pollard--Rho variant is used. Setting UseInversion halves the search space. To be effective element inversion must be fast.

Order(g, l, u, n, m: parameters) : GrpAbGenElt, RngIntElt, RngIntElt ,RngIntElt, RngIntElt -> RngIntElt
    Alg: MonStg                         Default: "Shanks"
    UseInversion: BoolElt               Default: false
Assume that g is an element of the generic abelian group A such that the order of g or the order of A is bounded by u and l. Assume also that Order(g) ≡ n (mod m) or that #A ≡ (mod m) This function returns the order of the element g. The two parameters Alg and UseInversion have the same meaning as for the previous Order function.

Discrete Logarithm

Log(g, d: parameters) : GrpAbGenElt, GrpAbGenElt -> RngIntElt
    ComputeGroupOrder: Bool             Default: true
    AlInPohligHellmanLoop: MonStg       Default: "BSGS"
    BSGSStepWidth: RngIntElt            Default: 0
    PollardRhoRParam: RngInt            Default: 20
    PollardRhoTParam: RngInt            Default: 8
    PollardRhoVParam: RngInt            Default: 3
Assume that g and d are elements of the generic abelian group A. This function returns the discrete logarithm of d to the base g. If ComputeGroupOrder is true, then the group order is computed first (if not already known) and from this the order of the base g is computed. The discrete logarithm problem is then solved using a Pohlig--Hellman loop calling either the T baby-step giant-step algorithm (AlInPohligHellmanLoop := "BSGS") or the T Pollard--Rho algorithm (AlInPohligHellmanLoop := "PollardRho").

The parameter BSGSStepWidth has the same meaning as for the Order function. Parameters PollardRhoRParam, PollardRhoTParam, and PollardRhoVParam have the same meaning as they do for the determination of structure (function AbelianGroup). If ComputeGroupOrder is false then the discrete logarithm problem is solved using the T baby-step giant-step algorithm. Here again the parameter BSGSStepWidth applies.

Example GrpAb_DiscreteLog (H75E11)

It is assumed that the structure of the groups QF has already been computed. We illustrate the computation of the discrete logarithm relative to a given base. 
> n := 38716;
> Ip := Reduction(PrimeForm(Q,11));
> g := GA_qf!Ip;
> d := n * g;
>
> l1 := Log(g, d : BSGSStepWidth := Floor((-Dk)^(1/4)/2));
> l2 := Log(g, d : AlInPohligHellmanLoop := "PollardRho");
> l3 := Log(g, d : ComputeGroupOrder := false);
> l4 := Log(g, d: ComputeGroupOrder := false,
>                 BSGSStepWidth := Floor((-Dk)^(1/4)/2));
> assert l1 eq l2 and l2 eq l3 and l3 eq l4;
> assert IsDivisibleBy(n - l1, Order(g));

Equality and Comparison

u eq v : GrpAbElt, GrpAbElt -> BoolElt
Returns true if the elements u and v are identical (as elements of the appropriate free abelian group), false otherwise.
u ne v : GrpAbElt, GrpAbElt -> BoolElt
Returns true if the elements u and v are not identical (as elements of the appropriate free abelian group), false otherwise.
IsIdentity(u) : GrpAbElt -> BoolElt
IsId(u) : GrpAbElt -> BoolElt
Returns true if the element u, belonging to the abelian group A, is the identity element (zero), false otherwise.
V2.28, 13 July 2023