Operations on Elements

[Next][Prev] [Right] [Left] [Up] [Index] [Root]

Two operations are provided: computing the order of an element, and computing the discrete logarithm of an element to a given base. In this instance, it is not necessary that the group structure of the generic abelian group be known beforehand, unless the group has been built with UseRepresentation as true.

These operations involve 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 already mentioned here [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, two more algorithms have been implemented:

-- 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]. In the special case where the order of the element or the order of the group can be bounded these two algorithms have been shown to be significantly faster than the two algorithms mentioned above.

To avoid confusion we'll 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, otherwise, when Alg is "PollardRho", the Gaudry-Harley Pollard-Rho variant is used.
Setting UseInversion halves the search space. To be effective this of course assumes that the inversion g is cost-effective.

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 can be set in the same manner as in the previous Order function.

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 parameters BSGSStepWidth, PollardRhoRParam, PollardRhoTParam, and PollardRhoVParam serve the same purpose as the one described in the Order function (for BSGSStepWidth), and in the AbelianGroup function (for the remaining three).

If ComputeGroupOrder is false then the discrete logarithm problem is solved using the T baby-step giant-step algorithm. Here again one can set the parameter BSGSStepWidth.

Example `GrpAbGen_ElementOrderLog (H27E7)`

It is assumed that the structure of the groups GA_(Zm) and GA_(qf) has already been computed. Here follow some statements illustrating the computation of the order of an element and of the discrete logarithm relative to a given base. First for GA_(Zm):

> g := Random(GA_Zm); g;
4723
> n := Random(1, #GA_Zm - 1); n;
7289
> d := n * g; d;
25651
> assert IsDivisibleBy(n - Log(g, d), Order(g));

Next, for GA_(qf):

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