Operations on Elements#

Order of an Element#

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: Discrete Log (ex-5056af)#

We compute the orders of some elements in the group \(Z_2 \times Z_3 \times Z_4 \times Z_5 \times 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

Run in calculator

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 [Buchmann et al., 1997],
–: the Pollard–Rho method based algorithm, described above [Teske, 1998].

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 [Gaudry and Harley, n.d.].

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(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) \(\equiv n\) (mod m) or that \(\#A \equiv\) (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: Discrete Log (ex-cb963b)#

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));

Run in calculator

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.