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
|
#############################################################################
##
## 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 declares operations related to discrete logarithms.
##
#############################################################################
##
#F DLog( <base>, <x>[, <m>] )
##
## <#GAPDoc Label="DLog">
## <ManSection>
## <Func Name="DLog" Arg="base, x[, m]"/>
## <Returns>an integer</Returns>
## <Description>
## <Index Subkey="discrete">logarithm</Index>
## The argument <A>base</A> must be a multiplicative element and <A>x</A>
## must lie in the cyclic group generated by <A>base</A>. The third argument
## <A>m</A> must be the order of <A>base</A> or its factorization. If
## <A>m</A> is not given, it is computed first. This function returns the
## discrete logarithm, that is an integer <M>e</M> such that <A>base</A><M>^e
## = </M> <A>x</A>.
## <P/>
## If <A>m</A> is prime then Shanks' algorithm is used (which needs
## <M>O(\sqrt{<A>m</A>})</M> space and time). Otherwise let <A>m</A> <M> = r
## l</M> and <M>e = a + b r</M> with <M>0 \leq a < r</M>. Then <M>a
## =</M> <C>DLog</C><M>(<A>base</A>^l, <A>x</A>^l, r)</M> and <M>b = </M>
## <C>DLog</C><M>(<A>base</A>^r, <A>x</A>/<A>base</A>^a, l)</M>.
## <P/>
## This function is used for a method of <Ref Oper="LogFFE"/>.
##
## <Example>
## gap> q:= 67^12;
## 8182718904632857144561
## gap> z:= Z(q);;
## gap> DLog(z, z+1);
## 2874413785388345993274
## gap> DLog(z, z^2+1);
## 1667375214152688471247
## gap> DLog(z, Z(67));
## 123980589464134199160
## </Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "DLog" );
DeclareGlobalFunction( "DLogShanks" );
|
