Quelle  dlog.gd   Sprache: unbekannt

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

[ Dauer der Verarbeitung: 0.28 Sekunden  (vorverarbeitet)  ]