Example GrpAb_DiscreteLog (H77E10)

> 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.

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