1 /****************************************************************************
2 **
3 ** This file is part of GAP, a system for computational discrete algebra.
4 **
5 ** Copyright of GAP belongs to its developers, whose names are too numerous
6 ** to list here. Please refer to the COPYRIGHT file for details.
7 **
8 ** SPDX-License-Identifier: GPL-2.0-or-later
9 **
10 ** This file declares the functions to compute with elements from small
11 ** finite fields.
12 **
13 ** Finite fields are an important domain in computational group theory
14 ** because the classical matrix groups are defined over those finite fields.
15 ** In GAP we support small finite fields with up to 65536 elements,
16 ** larger fields can be realized as polynomial domains over smaller fields.
17 **
18 ** Elements in small finite fields are represented as immediate objects.
19 **
20 ** +----------------+-------------+---+
21 ** | <value> | <field> |010|
22 ** +----------------+-------------+---+
23 **
24 ** The least significant 3 bits of such an immediate object are always 010,
25 ** flagging the object as an object of a small finite field.
26 **
27 ** The next 13 bits represent the small finite field where the element lies.
28 ** They are simply an index into a global table of small finite fields.
29 **
30 ** The most significant 16 bits represent the value of the element.
31 **
32 ** If the value is 0, then the element is the zero from the finite field.
33 ** Otherwise the integer is the logarithm of this element with respect to a
34 ** fixed generator of the multiplicative group of the finite field plus one.
35 ** In the following descriptions we denote this generator always with $z$, it
36 ** is an element of order $o-1$, where $o$ is the order of the finite field.
37 ** Thus 1 corresponds to $z^{1-1} = z^0 = 1$, i.e., the one from the field.
38 ** Likewise 2 corresponds to $z^{2-1} = z^1 = z$, i.e., the root itself.
39 **
40 ** This representation makes multiplication very easy, we only have to add
41 ** the values and subtract 1 , because $z^{a-1} * z^{b-1} = z^{(a+b-1)-1}$.
42 ** Addition is reduced to * by the formula $z^a + z^b = z^b * (z^{a-b}+1)$.
43 ** This makes it necessary to know the successor $z^a + 1$ of every value.
44 **
45 ** The finite field bag contains the successor for every nonzero value,
46 ** i.e., 'SUCC_FF(<ff>)[<a>]' is the successor of the element <a>, i.e, it
47 ** is the logarithm of $z^{a-1} + 1$. This list is usually called the
48 ** Zech-Logarithm table. The zeroth entry in the finite field bag is the
49 ** order of the finite field minus one.
50 */
51
52 #ifndef GAP_FINFIELD_H
53 #define GAP_FINFIELD_H
54
55 #include "ffdata.h"
56 #include "objects.h"
57
58 #ifdef HPCGAP
59 #include "hpc/aobjects.h"
60 #endif
61
62
63 /****************************************************************************
64 **
65 *T FF . . . . . . . . . . . . . . . . . . . . . type of small finite fields
66 **
67 ** 'FF' is the type used to represent small finite fields.
68 **
69 ** Small finite fields are represented by an index into a global table.
70 **
71 ** Since there are only 6542 (prime) + 93 (nonprime) small finite fields,
72 ** the index fits into a 'UInt2' (actually into 13 bits).
73 */
74 typedef UInt2 FF;
75
76
77 /****************************************************************************
78 **
79 *F CHAR_FF(<ff>) . . . . . . . . . . . characteristic of small finite field
80 **
81 ** 'CHAR_FF' returns the characteristic of the small finite field <ff>.
82 **
83 ** Note that 'CHAR_FF' is a macro, so do not call it with arguments that
84 ** have side effects.
85 */
86 #define CHAR_FF(ff) (CharFF[ff])
87
88
89 /****************************************************************************
90 **
91 *F DEGR_FF(<ff>) . . . . . . . . . . . . . . . degree of small finite field
92 **
93 ** 'DEGR_FF' returns the degree of the small finite field <ff>.
94 **
95 ** Note that 'DEGR_FF' is a macro, so do not call it with arguments that
96 ** have side effects.
97 */
98 #define DEGR_FF(ff) (DegrFF[ff])
99
100
101 /****************************************************************************
102 **
103 *F SIZE_FF(<ff>) . . . . . . . . . . . . . . . . size of small finite field
104 **
105 ** 'SIZE_FF' returns the size of the small finite field <ff>.
106 **
107 ** Note that 'SIZE_FF' is a macro, so do not call it with arguments that
108 ** have side effects.
109 */
110 #define SIZE_FF(ff) (SizeFF[ff])
111
112
113 /****************************************************************************
114 **
115 *F SUCC_FF(<ff>) . . . . . . . . . . . successor table of small finite field
116 **
117 ** 'SUCC_FF' returns a pointer to the successor table of the small finite
118 ** field <ff>.
119 **
120 ** Note that 'SUCC_FF' is a macro, so do not call it with arguments that
121 ** side effects.
122 */
123 #ifdef HPCGAP
124 #define SUCC_FF(ff) ((const FFV*)(1+CONST_ADDR_OBJ( ATOMIC_ELM_PLIST( SuccFF, ff ) )))
125 #else
126 #define SUCC_FF(ff) ((const FFV*)(1+CONST_ADDR_OBJ( ELM_PLIST( SuccFF, ff ) )))
127 #endif
128
129 extern Obj SuccFF;
130
131
132 /****************************************************************************
133 **
134 *T FFV . . . . . . . . type of the values of elements of small finite fields
135 **
136 ** 'FFV' is the type used to represent the values of elements of small
137 ** finite fields.
138 **
139 ** Values of elements of small finite fields are represented by the
140 ** logarithm of the element with respect to the root plus one.
141 **
142 ** Since small finite fields contain at most 65536 elements, the value fits
143 ** into a 'UInt2'.
144 **
145 ** It may be possible to change this to 'UInt4' to allow small finite fields
146 ** with more than than 65536 elements. The macros and have been coded in
147 ** such a way that they work without problems. The exception is 'POW_FFV'
148 ** which will only work if the product of integers of type 'FFV' does not
149 ** cause an overflow. And of course the successor table stored for a finite
150 ** field will become quite large for fields with more than 65536 elements.
151 */
152 typedef UInt2 FFV;
153
154 GAP_STATIC_ASSERT(sizeof(UInt) >= 2 * sizeof(FFV),
155 "Overflow possibility in POW_FFV");
156
157 /****************************************************************************
158 **
159 *F PROD_FFV(<a>,<b>,<f>) . . . . . . . . . . . product of finite field value
160 **
161 ** 'PROD_FFV' returns the product of the two finite field values <a> and <b>
162 ** from the finite field pointed to by the pointer <f>.
163 **
164 ** Note that 'PROD_FFV' may only be used if the operands are represented in
165 ** the same finite field. If you want to multiply two elements where one
166 ** lies in a subfield of the other use 'ProdFFEFFE'.
167 **
168 ** If one of the values is 0 the product is 0.
169 ** If $a+b <= o$ we have $a * b ~ z^{a-1} * z^{b-1} = z^{(a+b-1)-1} ~ a+b-1$
170 ** otherwise we have $a * b ~ z^{(a+b-2)-(o-1)} = z^{(a+b-o)-1} ~ a+b-o$
171 */
PROD_FFV(FFV a,FFV b,const FFV * f)172 EXPORT_INLINE FFV PROD_FFV(FFV a, FFV b, const FFV * f)
173 {
174 GAP_ASSERT(a <= f[0]);
175 GAP_ASSERT(b <= f[0]);
176 if (a == 0 || b == 0)
177 return 0;
178 FFV q1 = f[0];
179 FFV a1 = a - 1;
180 FFV b1 = q1 - b;
181 if (a1 <= b1)
182 return a1 + b;
183 else
184 return a1 - b1;
185 }
186
187
188 /****************************************************************************
189 **
190 *F SUM_FFV(<a>,<b>,<f>) . . . . . . . . . . . . sum of finite field values
191 **
192 ** 'SUM_FFV' returns the sum of the two finite field values <a> and <b> from
193 ** the finite field pointed to by the pointer <f>.
194 **
195 ** Note that 'SUM_FFV' may only be used if the operands are represented in
196 ** the same finite field. If you want to add two elements where one lies in
197 ** a subfield of the other use 'SumFFEFFE'.
198 **
199 ** If either operand is 0, the sum is just the other operand.
200 ** If $a <= b$ we have
201 ** $a + b ~ z^{a-1}+z^{b-1} = z^{a-1} * (z^{(b-1)-(a-1)}+1) ~ a * f[b-a+1]$,
202 ** otherwise we have
203 ** $a + b ~ z^{b-1}+z^{a-1} = z^{b-1} * (z^{(a-1)-(b-1)}+1) ~ b * f[a-b+1]$.
204 */
SUM_FFV(FFV a,FFV b,const FFV * f)205 EXPORT_INLINE FFV SUM_FFV(FFV a, FFV b, const FFV * f)
206 {
207 GAP_ASSERT(a <= f[0]);
208 GAP_ASSERT(b <= f[0]);
209 if (a == 0)
210 return b;
211 if (b == 0)
212 return a;
213 if (b > a) {
214 FFV t = a;
215 a = b;
216 b = t;
217 }
218 return PROD_FFV(b, f[a - b + 1], f);
219 }
220
221
222 /****************************************************************************
223 **
224 *F NEG_FFV(<a>,<f>) . . . . . . . . . . . . negative of finite field value
225 **
226 ** 'NEG_FFV' returns the negative of the finite field value <a> from the
227 ** finite field pointed to by the pointer <f>.
228 **
229 ** If the characteristic is 2, every element is its own additive inverse.
230 ** Otherwise note that $z^{o-1} = 1 = -1^2$ so $z^{(o-1)/2} = 1^{1/2} = -1$.
231 ** If $a <= (o-1)/2$ we have
232 ** $-a ~ -1 * z^{a-1} = z^{(o-1)/2} * z^{a-1} = z^{a+(o-1)/2-1} ~ a+(o-1)/2$
233 ** otherwise we have
234 ** $-a ~ -1 * z^{a-1} = z^{a+(o-1)/2-1} = z^{a+(o-1)/2-1-(o-1)} ~ a-(o-1)/2$
235 */
NEG_FFV(FFV a,const FFV * f)236 EXPORT_INLINE FFV NEG_FFV(FFV a, const FFV * f)
237 {
238 GAP_ASSERT(a <= f[0]);
239 UInt q1 = f[0];
240 if (a == 0)
241 return 0;
242 if (q1 % 2)
243 return a;
244 if (a <= q1 / 2)
245 return a + q1 / 2;
246 else
247 return a - q1 / 2;
248 }
249
250
251 /****************************************************************************
252 **
253 *F QUO_FFV(<a>,<b>,<f>) . . . . . . . . . . quotient of finite field values
254 **
255 ** 'QUO_FFV' returns the quotient of the two finite field values <a> and <b>
256 ** from the finite field pointed to by the pointer <f>.
257 **
258 ** Note that 'QUO_FFV' may only be used if the operands are represented in
259 ** the same finite field. If you want to divide two elements where one lies
260 ** in a subfield of the other use 'QuoFFEFFE'.
261 **
262 ** A division by 0 is an error, and dividing 0 by a nonzero value gives 0.
263 ** If $0 <= a-b$ we have $a / b ~ z^{a-1} / z^{b-1} = z^{a-b+1-1} ~ a-b+1$,
264 ** otherwise we have $a / b ~ z^{a-b+1-1} = z^{a-b+(o-1)} ~ a-b+o$.
265 */
QUO_FFV(FFV a,FFV b,const FFV * f)266 EXPORT_INLINE FFV QUO_FFV(FFV a, FFV b, const FFV * f)
267 {
268 GAP_ASSERT(a <= f[0]);
269 GAP_ASSERT(b <= f[0]);
270 if (a == 0)
271 return 0;
272 if (b <= a)
273 return a - b + 1;
274 else
275 return a + (f[0] - b) + 1;
276 }
277
278
279 /****************************************************************************
280 **
281 *F POW_FFV(<a>,<n>,<f>) . . . . . . . . . . . power of a finite field value
282 **
283 ** 'POW_FFV' returns the <n>th power of the finite field value <a> from the
284 ** the finite field pointed to by the pointer <f>.
285 **
286 ** Note that 'POW_FFV' may only be used if the right operand is an integer
287 ** in the range $0..order(f)-1$.
288 **
289 ** Finally 'POW_FFV' may only be used if the product of two integers of the
290 ** size of 'FFV' does not cause an overflow, i.e. only if 'FFV' is
291 ** 'unsigned short'.
292 **
293 ** If the finite field element is 0 the power is also 0, otherwise we have
294 ** $a^n ~ (z^{a-1})^n = z^{(a-1)*n} = z^{(a-1)*n % (o-1)} ~ (a-1)*n % (o-1)$
295 */
POW_FFV(FFV a,UInt n,const FFV * f)296 EXPORT_INLINE FFV POW_FFV(FFV a, UInt n, const FFV * f)
297 {
298 GAP_ASSERT(a <= f[0]);
299 GAP_ASSERT(n <= f[0]);
300 if (!n)
301 return 1;
302 if (!a)
303 return 0;
304
305 // Use UInt to avoid overflow in the multiplication
306 UInt a1 = a - 1;
307 return ((a1 * n) % f[0]) + 1;
308 }
309
310
311 /****************************************************************************
312 **
313 *F FLD_FFE(<ffe>) . . . . . . . field of an element of a small finite field
314 **
315 ** 'FLD_FFE' returns the small finite field over which the element <ffe> is
316 ** represented.
317 **
318 */
FLD_FFE(Obj ffe)319 EXPORT_INLINE FF FLD_FFE(Obj ffe)
320 {
321 GAP_ASSERT(IS_FFE(ffe));
322 return (FF)((((UInt)(ffe)) & 0xFFFF) >> 3);
323 }
324
325
326 /****************************************************************************
327 **
328 *F VAL_FFE(<ffe>) . . . . . . . value of an element of a small finite field
329 **
330 ** 'VAL_FFE' returns the value of the element <ffe> of a small finite field.
331 ** Thus, if <ffe> is $0_F$, it returns 0; if <ffe> is $1_F$, it returns 1;
332 ** and otherwise if <ffe> is $z^i$, it returns $i+1$.
333 **
334 */
VAL_FFE(Obj ffe)335 EXPORT_INLINE FFV VAL_FFE(Obj ffe)
336 {
337 GAP_ASSERT(IS_FFE(ffe));
338 return (FFV)(((UInt)(ffe)) >> 16);
339 }
340
341
342 /****************************************************************************
343 **
344 *F NEW_FFE(<fld>,<val>) . . . . make a new element of a small finite field
345 **
346 ** 'NEW_FFE' returns a new element <ffe> of the small finite field <fld>
347 ** with the value <val>.
348 **
349 */
NEW_FFE(FF fld,FFV val)350 EXPORT_INLINE Obj NEW_FFE(FF fld, FFV val)
351 {
352 GAP_ASSERT(val < SIZE_FF(fld));
353 return (Obj)(((UInt)(val) << 16) + ((UInt)(fld) << 3) + (UInt)0x02);
354 }
355
356
357 /****************************************************************************
358 **
359 *F FiniteField(<p>,<d>) . make the small finite field with <p>^<d> elements
360 *F FiniteFieldBySize(<q>) . . make the small finite field with <q> elements
361 **
362 ** 'FiniteField' returns the small finite field with <p>^<d> elements.
363 ** 'FiniteFieldBySize' returns the small finite field with <q> elements.
364 */
365 FF FiniteField(UInt p, UInt d);
366 FF FiniteFieldBySize(UInt q);
367
368
369 /****************************************************************************
370 **
371 *F CommonFF(<f1>,<d1>,<f2>,<d2>) . . . . . . . . . . . . find a common field
372 **
373 ** 'CommonFF' returns a small finite field that can represent elements of
374 ** degree <d1> from the small finite field <f1> and elements of degree <d2>
375 ** from the small finite field <f2>. Note that this is not guaranteed to be
376 ** the smallest such field. If <f1> and <f2> have different characteristic
377 ** or the smallest common field, is too large, 'CommonFF' returns 0.
378 */
379 FF CommonFF(FF f1, UInt d1, FF f2, UInt d2);
380
381
382 /****************************************************************************
383 **
384 *F CharFFE(<ffe>) . . . . . . . . . characteristic of a small finite field
385 **
386 ** 'CharFFE' returns the characteristic of the small finite field in which
387 ** the element <ffe> lies.
388 */
389 UInt CharFFE(Obj ffe);
390
391
392 /****************************************************************************
393 **
394 *F DegreeFFE(<ffe>) . . . . . . . . . . . . degree of a small finite field
395 **
396 ** 'DegreeFFE' returns the degree of the smallest finite field in which the
397 ** element <ffe> lies.
398 */
399 UInt DegreeFFE(Obj ffe);
400
401
402 /****************************************************************************
403 **
404 *F TypeFFE(<ffe>) . . . . . . . . . . type of element of small finite field
405 **
406 ** 'TypeFFE' returns the type of the element <ffe> of a small finite field.
407 **
408 ** 'TypeFFE' is the function in 'TypeObjFuncs' for elements in small finite
409 ** fields.
410 */
411 Obj TypeFFE(Obj ffe);
412
413
414 /****************************************************************************
415 **
416 *F * * * * * * * * * * * * * initialize module * * * * * * * * * * * * * * *
417 */
418
419
420 /****************************************************************************
421 **
422 *F InitInfoFinfield() . . . . . . . . . . . . . . . table of init functions
423 */
424 StructInitInfo * InitInfoFinfield ( void );
425
426
427 #endif // GAP_FINFIELD_H
428