/usr/share/axiom-20170501/src/algebra/DLP.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | )abbrev package DLP DiscreteLogarithmPackage
++ Author: J. Grabmeier, A. Scheerhorn
++ Date Created: 12 March 1991
++ Date Last Updated: 31 March 1991
++ References:
++ Grab92 Finite Fields in Axiom
++ Description:
++ DiscreteLogarithmPackage implements help functions for discrete logarithms
++ in monoids using small cyclic groups.
DiscreteLogarithmPackage(M) : SIG == CODE where
M : Join(Monoid,Finite) with
"**": (M,Integer) -> M
++ x ** n returns x raised to the integer power n
I ==> Integer
PI ==> PositiveInteger
NNI ==> NonNegativeInteger
SUP ==> SparseUnivariatePolynomial
DLP ==> DiscreteLogarithmPackage
SIG ==> with
shanksDiscLogAlgorithm:(M,M,NonNegativeInteger)-> _
Union(NonNegativeInteger,"failed")
++ shanksDiscLogAlgorithm(b,a,p) computes s with \spad{b**s = a} for
++ assuming that \spad{a} and b are elements in a 'small' cyclic group of
++ order p by Shank's algorithm.
++ Note that this is a subroutine of the function \spadfun{discreteLog}.
CODE ==> add
shanksDiscLogAlgorithm(logbase,c,p) ==
limit:Integer:= 30
-- for logarithms up to cyclic groups of order limit a full
-- logarithm table is computed
p < limit =>
a:M:=1
disclog:Integer:=0
found:Boolean:=false
for i in 0..p-1 while not found repeat
a = c =>
disclog:=i
found:=true
a:=a*logbase
not found =>
messagePrint("discreteLog: second argument not in cyclic group_
generated by first argument")$OutputForm
"failed"
disclog pretend NonNegativeInteger
l:Integer:=length(p)$Integer
if odd?(l)$Integer then n:Integer:= shift(p,-(l quo 2))
else n:Integer:= shift(1,(l quo 2))
a:M:=1
exptable : Table(PI,NNI) :=table()$Table(PI,NNI)
for i in (0::NNI)..(n-1)::NNI repeat
insert_!([lookup(a),i::NNI]$Record(key:PI,entry:NNI),_
exptable)$Table(PI,NNI)
a:=a*logbase
found := false
end := (p-1) quo n
disclog:Integer:=0
a := c
b := logbase ** (-n)
for i in 0..end while not found repeat
rho:= search(lookup(a),exptable)_
$Table(PositiveInteger,NNI)
rho case NNI =>
found := true
disclog:= n * i + rho pretend Integer
a := a * b
not found =>
messagePrint("discreteLog: second argument not in cyclic group_
generated by first argument")$OutputForm
"failed"
disclog pretend NonNegativeInteger
|