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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
/*
------------------------------------------------------------------------
Efficient Galois Fields in Maxima
by Alasdair McAndrew
and later extended by Fabrizio Caruso and Jacopo Daurizio
it is distribuited together with gf_roots by Jacopo Daurizio
Authors:
Fabrizio Caruso (optimizations, testing)
Jacopo D'Aurizio (optimizations, modular roots)
Alasdair McAndrew (original version of the package, pohlig-helman log, etc... )
------------------------------------------------------------------------*/
/* Released under terms of the GNU General Public License, version 2,
* by permission of the authors to Robert Dodier circa 2007-12-02.
*/
/* Defines a flag for dealing with large fields. If it is set to "false",
then lookup tables are used for exponentiation and logarithms. Otherwise
other algorithms are used */
define_variable(largefield,true,bool)$
define_variable(gf_char,0,integer)$
define_variable(gf_exp,0,integer)$
define_variable(gf_order,0,integer)$
define_variable (gf_one, 'gf_one, any_check)$
define_variable (gf_prim, 'gf_prim, any_check)$
define_variable (gf_irr, 'gf_irr, any_check)$
define_variable (gf_list, 'gf_list, any_check)$
define_variable (gen_powers, 'gf_list, any_check)$
remvalue(x,z,gf_char,gf_exp,gf_irr,pg,gp,lg,gf_prim,gf_one,gf_order,gf_list,gen_powers)$
/* --------------------------------------------------------------------------------------------- */
/* Settings */
GF_VERBOSE:false; /* Verbosity */
GF_WARNING: true; /* Warnings */
GF_IRREDUCIBILITY_CHECK:false; /* Irreducibility test for the minimal polynomial of the extension */
/*
------------------------------------------------------------------------------------------------ */
/* It defines a new current field with gf_char=b, min. pol.= p of deg= e*/
gf_set([ars]):=block([gj,m,i,j,dg],
if length(ars)=1 then
(
gf_setp(ars[1]),
return(true)
)
else
(
if length(ars)=2 then
(
if numberp(ars[2]) then
(
if ars[2]=0 and GF_WARNING then
(
print("WARNING: the irreducible is zero! We assume GF(",ars[1],")"),
gf_setp(ars[1]),
return(true)
)
else
(
error("ERROR: you tried to extend with a non-zero constant!"),
return(false)
)
)
else
(
dg:hipow(ars[2],x),
if dg=1 then
gf_setp(ars[1]),
gf_irr:ars[2],
gf_exp:dg,
return(true)
)
)
else
(
gf_exp:ars[2],
if gf_exp=1 then
(
gf_setp(ars[1]),
gf_irr:rat(ars[3]),
return(true)
),
gf_irr:rat(ars[3])
)
),
gf_char:ars[1],
gf_one:rat(1,x),
gf_order:gf_char^gf_exp-1,
m:makelist(coeff(gf_irr,x,i),i,0,gf_exp),
gf_list:[[first(m),0]],j:1,
for i:2 thru gf_exp+1 do if m[i]=0 then j:j+1 else ( gf_list:endcons([m[i],j],gf_list), j:1 ),
if not(primep(gf_char)) then error("ERROR: Gf_Char must be a prime number.")
else
modulus:gf_char,
if GF_IRREDUCIBILITY_CHECK and
hipow(args(factor(ars[3]))[1],x)#hipow(rat(ars[3]),x) then
error("ERROR: Polynomial is not irreducible"),
if not(largefield) then
(
pg:mkpowers(),
lg:mklogs()
)
else
(
if GF_VERBOSE then
print("finding a primitive element..."),
gf_prim:rat(gf_findprim(),x),
if GF_VERBOSE then
print("...primitive element found.")
),
modulus:false, /* it resets the modulus */
return(true)
)$
/* Prints out information about the field */
gf_info():=block(
print("Prime gf_char value: ",gf_char),
print("Exponent: ", gf_exp),
print("Multiplicative order: ",gf_order),
print("Irreducible polynomial: ",gf_irr),
print("Primitive element: ",gf_prim),
if (largefield) then
print("Largefield flag is true; powers and logarithms not computed.")
else
print("Largefield flag is false; powers and logarithms computed."),
disp()
)$
|
