# 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$. ```magma > G<[x]> := AbelianGroup([2,3,4,5,0]); > Order( x[1] + 2*x[2] + 3*x[4]); 30 > Order( x[1] + x[5] ); 0 ``` 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](../../references.md#cite-teske-bsgs)], **–** the Pollard–Rho method based algorithm, described above [[Teske, 1998](../../references.md#cite-teske-prho)]. 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.](../../references.md#cite-gaudry-har)]. 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` ```magma 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` ```magma 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` ```magma 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` ```magma 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. ```magma > 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.