1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Frank Lübeck.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains methods related to discrete logarithms.
## The code was copied from the StandardFF package.
##
#############################################################################
##
#F DLogShanks( <base>, <x>, <r> )
##
## Let <base> be a multiplicative element of order <r>.
## Return an integer l such that <x> = <base>^l holds,
## or 'fail' if no such l exists.
##
InstallGlobalFunction( DLogShanks, function(base, x, r)
local rr, baby, ord, giant, t, pos, i, j;
rr := RootInt(r, 2);
baby := [One(base)];
if x = baby[1] then
return 0;
fi;
for i in [1..rr-1] do
baby[i+1] := baby[i]*base;
if x = baby[i+1] then
return i;
fi;
od;
giant := baby[rr]*base;
ord := [0..rr-1];
SortParallel(baby, ord);
t := x;
for j in [1..QuoInt(r, rr)+1] do
t := t*giant;
pos := PositionSet(baby, t);
if IsInt(pos) then
return (ord[pos] - j * rr) mod r;
fi;
od;
return fail;
end );
#############################################################################
##
#F DLog( <base>, <x>[, <m>] )
##
## recursive method, <m> can be the order m of <base> or its factorization
## Let r be the largest prime factor of m, then we use
## <base>^e = <x> with e = a + b*r where 0 <= a < r and
## 0 <= b < m/r,
## and compute a with DLogShanks and b by recursion.
##
InstallGlobalFunction( DLog, function(base, x, m...)
local r, mm, mp, a, b;
if Length(m) = 0 then
m := Order(base);
else
m := m[1];
fi;
if not IsList(m) then
m := Factors(m);
fi;
if Length(m) = 1 then
return DLogShanks(base, x, m[1]);
fi;
r := Last(m);
mm := m{[1..Length(m)-1]};
mp := Product(mm);
a := DLogShanks(base^mp, x^mp, r);
if a = fail then
return fail;
fi;
b := DLog(base^r, x/(base^a), mm);
if b = fail then
return fail;
fi;
return a + b*r;
end );
#############################################################################
##
## used as method for LogFFE
##
BindGlobal( "DoDLog", function(x, base)
local ob, o, e;
ob := Order(base);
o := Order(x);
if ob mod o <> 0 then
return fail;
fi;
if ob <> o then
e := ob/o;
base := base^e;
else
e := 1;
fi;
return DLog(base, x, o) * e;
end );
|
