$SPAD/src/input ffdemo.input

Timothy Daly December 3, 2016

Abstract

Contents

2

1 License

— license —

--Copyright The Numerical Algorithms Group Limited 1991.

———-

— * —

)set break resume
)spool ffdemo.output
)set message test on
)set message auto off
)clear all

———-

2 finite field demonstrations

2.1 prime field

Get a prime — * —

--S 1 of 350
p:=4817
--R
--R
--R   (1)  4817
--R                                                        Type: PositiveInteger
--E 1

———-

Construct a field — * —

--S 2 of 350
F:=PrimeField p
--R
--R
--R   (2)  PrimeField(4817)
--R                                                                 Type: Domain
--E 2

———-

Demonstration of common finite field functions. The finite field domain is in variable F. We take some random elements

— * —

--S 3 of 350
size()$F
--R
--R
--R   (3)  4817
--R                                                     Type: NonNegativeInteger
--E
--S 4 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R   (4)  1605
--R                                                       Type: PrimeField(4817)
--E 4
--S 5 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R   (5)  688
--R                                                       Type: PrimeField(4817)
--E 5

———-

2.2 Simple arithmetic

— * —

--S 6 of 350
a+b
--R
--R
--R   (6)  2293
--R                                                       Type: PrimeField(4817)
--E 6
--S 7 of 350
a-b
--R
--R
--R   (7)  917

--R                                                       Type: PrimeField(4817)
--E 7
--S 8 of 350
a*b
--R
--R
--R   (8)  1147
--R                                                       Type: PrimeField(4817)
--E 8
--S 9 of 350
a/b
--R
--R
--R   (9)  3216
--R                                                       Type: PrimeField(4817)
--E 9
--S 10 of 350
a**1234
--R
--R
--R   (10)  2068
--R                                                       Type: PrimeField(4817)
--E 10
--S 11 of 350
a**(-1)
--R
--R
--R   (11)  2407
--R                                                       Type: PrimeField(4817)
--E 11
--S 12 of 350
g := generator()$F
--R
--R
--R   (12)  1
--R                                                       Type: PrimeField(4817)
--E 12
--S 13 of 350
(definingPolynomial()$F::SUP(F)).g
--R
--R
--R   (13)  0
--R                                                       Type: PrimeField(4817)
--E 13

———-

2.3 functions concerning the multiplicative cyclic group

— * —

--S 14 of 350
order(a)
--R
--R
--R   (14)  688
--R                                                        Type: PositiveInteger
--E 14
--S 15 of 350
g:=primitiveElement()$F
--R
--R
--R   (15)  3
--R                                                       Type: PrimeField(4817)
--E 15
--S 16 of 350
discreteLog(a)
--R
--R
--R   (16)  987
--R                                                        Type: PositiveInteger
--E 16

———-

The next one should equal 0 — * —

--S 17 of 350
g**% - a
--R
--R
--R   (17)  0
--R                                                       Type: PrimeField(4817)
--E 17

———-

The next may fail — * —

--S 18 of 350
discreteLog(b,a)
--R
--R   discreteLog: second argument not in cyclic group generated by first argument
--R
--R   (18)  "failed"
--R                                                    Type: Union("failed",...)
--E 18

———-

2.4 special finite field functions

— * —

--S 19 of 350
extensionDegree()$F
--R
--R
--R   (19)  1
--R                                                        Type: PositiveInteger
--E 19
--S 20 of 350
degree(a)
--R
--R
--R   (20)  1
--R                                                        Type: PositiveInteger
--E 20
--S 21 of 350
normalElement()$F
--R
--R
--R   (21)  1
--R                                                       Type: PrimeField(4817)
--E 21
--S 22 of 350
definingPolynomial()$F
--R
--R
--R   (22)  ? + 4816
--R                           Type: SparseUnivariatePolynomial(PrimeField(4817))
--E 22
--S 23 of 350

minimalPolynomial(a)
--R
--R
--R   (23)  ? + 3212
--R                           Type: SparseUnivariatePolynomial(PrimeField(4817))
--E 23
--S 24 of 350
Frobenius(a)
--R
--R
--R   (24)  1605
--R                                                       Type: PrimeField(4817)
--E 24
--S 25 of 350
linearAssociatedOrder(a)
--R
--R
--R   (25)  ? + 4816
--R                           Type: SparseUnivariatePolynomial(PrimeField(4817))
--E 25
--S 26 of 350
linearAssociatedLog(a)
--R
--R
--R   (26)  1605
--R                           Type: SparseUnivariatePolynomial(PrimeField(4817))
--E 26
--S 27 of 350
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
--R
--I   Compiling function G1462 with type Integer -> Boolean
--I   Compiling function G1641 with type NonNegativeInteger -> Boolean
--R   1605
--R   1605
--R                                                                   Type: Void
--E 27

———-

End of common finite field demonstration

2.5 finite field with polynomail basis

Get a small prime — * —

--S 28 of 350
p:=7
--R
--R
--R   (28)  7
--R                                                        Type: PositiveInteger
--E 28
--S 29 of 350
P:=PrimeField p
--R
--R
--R   (29)  PrimeField(7)
--R                                                                 Type: Domain
--E 29

———-

Get a small extension degree — * —

--S 30 of 350
d:=6
--R
--R
--R   (30)  6
--R                                                        Type: PositiveInteger
--E 30

———-

Get a irreducible polynomial — * —

--S 31 of 350
f:=createIrreduciblePoly(d)$FFPOLY(P)
--R
--R
--R          6
--R   (31)  ?  + 2
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))
--E 31

———-

Construct the field — * —

--S 32 of 350
F:=FFP(P,f)
--R
--R
--R   (32)  FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--R                                                                 Type: Domain
--E 32

———-

This field is the same as constructed by F:=FFX(P,d) or F:=FF(p,d)

2.6 demonstration of common finite field functions

The finite field domain is in variable F. Take some random elements — * —

--S 33 of 350
size()$F
--R
--R
--R   (33)  117649
--R                                                     Type: NonNegativeInteger
--E 33
--S 34 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R            5      4      3      2
--R   (34)  2%A  + 2%A  + 2%A  + 2%A  + 2%A + 2
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 34
--S 35 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R           5
--R   (35)  %A
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 35

———-

Simple arithmetic — * —

--S 36 of 350
a+b

--R
--R
--R            5      4      3      2
--R   (36)  3%A  + 2%A  + 2%A  + 2%A  + 2%A + 2
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 36
--S 37 of 350
a-b
--R
--R
--R           5      4      3      2
--R   (37)  %A  + 2%A  + 2%A  + 2%A  + 2%A + 2
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 37
--S 38 of 350
a*b
--R
--R
--R            5      4      3      2
--R   (38)  2%A  + 3%A  + 3%A  + 3%A  + 3%A + 3
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 38
--S 39 of 350
a/b
--R
--R
--R            5      4      3      2
--R   (39)  6%A  + 6%A  + 6%A  + 6%A  + 6%A + 2
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 39
--S 40 of 350
a**1234
--R
--R
--R            5     4      3
--R   (40)  5%A  + %A  + 3%A  + 3%A + 4
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 40
--S 41 of 350
a**(-1)
--R
--R
--R   (41)  %A + 6
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 41

--S 42 of 350
g := generator()$F
--R
--R
--R   (42)  %A
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 42
--S 43 of 350
(definingPolynomial()$F::SUP(F)).g
--R
--R
--R   (43)  0
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 43

———-

2.7 functions concerning the multiplicative cyclic group

— * —

--S 44 of 350
order(a)
--R
--R
--R   (44)  117648
--R                                                        Type: PositiveInteger
--E 44
--S 45 of 350
g:=primitiveElement()$F
--R
--R
--R   (45)  %A + 1
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 45
--S 46 of 350
discreteLog(a)
--R
--R
--R   (46)  58481
--R                                                        Type: PositiveInteger
--E 46

———- The next one should equal 0

— * —

--S 47 of 350
g**% - a
--R
--R
--R   (47)  0
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 47

———-

The next may fail — * —

--S 48 of 350
discreteLog(b,a)
--R
--R   discreteLog: second argument not in cyclic group generated by first argument
--R
--R   (48)  "failed"
--R                                                    Type: Union("failed",...)
--E 48

———-

2.8 special finite field functions

— * —

--S 49 of 350
extensionDegree()$F
--R
--R
--R   (49)  6
--R                                                        Type: PositiveInteger
--E 49
--S 50 of 350
degree(a)
--R
--R
--R   (50)  6
--R                                                        Type: PositiveInteger
--E 50
--S 51 of 350
normalElement()$F

--R
--R
--R            5      4      3      2
--R   (51)  5%A  + 3%A  + 3%A  + 5%A  + %A + 5
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 51
--S 52 of 350
definingPolynomial()$F
--R
--R
--R          6
--R   (52)  ?  + 2
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))
--E 52
--S 53 of 350
minimalPolynomial(a)
--R
--R
--R          6     5     4     3     2
--R   (53)  ?  + 2?  + 5?  + 2?  + 5?  + 2? + 5
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))
--E 53
--S 54 of 350
Frobenius(a)
--R
--R
--R            5      4      3     2
--R   (54)  6%A  + 4%A  + 5%A  + %A  + 3%A + 2
--R                  Type: FiniteFieldExtensionByPolynomial(PrimeField(7),?^6+2)
--E 54
--S 55 of 350
linearAssociatedOrder(a)
--R
--R
--R          6
--R   (55)  ?  + 6
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))
--E 55
--S 56 of 350
linearAssociatedLog(a)
--R
--R
--R           5     4     3     2
--R   (56)  2?  + 3?  + 3?  + 3?  + 2
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))

--E 56
--S 57 of 350
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
--R
--R   5
--R   5
--R      3
--R   2%A  + 2
--R      3
--R   6%A  + 6
--R      4      2
--R   5%A  + 5%A  + 5
--R      4      2
--R   4%A  + 4%A  + 4
--R      5      4      3      2
--R   2%A  + 2%A  + 2%A  + 2%A  + 2%A + 2
--R      5      4      3      2
--R   2%A  + 2%A  + 2%A  + 2%A  + 2%A + 2
--R                                                                   Type: Void
--E 57

———-

End of common finite field demonstration

2.9 finite field with normal basis

Get a normal Polynomial — * —

--S 58 of 350
f:=createNormalPoly(d)$FFPOLY(P)
--R
--R
--R          6     5
--R   (58)  ?  + 6?  + 2? + 4
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))
--E 58

———-

Build the field — * —

--S 59 of 350
F:=FFNBP(P,f)
--R

--R
--R   (59)
--R   FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--R                                                                 Type: Domain
--E 59

———-

This field is the same as constructed by F:=FFNBX(P,d) or F:=FFNB(p,d)

2.10 demonstration of common finite field functions

The finite field domain is in variable F. Take some random elements.

— * —

--S 60 of 350
size()$F
--R
--R
--R   (60)  117649
--R                                                     Type: NonNegativeInteger
--E 60
--S 61 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R             5       4       3       2
--R            q       q       q       q       q
--R   (61)  2%B   + 2%B   + 2%B   + 2%B   + 2%B  + 2%B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 61
--S 62 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R            5
--R           q
--R   (62)  %B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 62

———-

Simple arithmetic — * —

--S 63 of 350
a+b

--R
--R
--R             5       4       3       2
--R            q       q       q       q       q
--R   (63)  3%B   + 2%B   + 2%B   + 2%B   + 2%B  + 2%B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 63
--S 64 of 350
a-b
--R
--R
--R            5       4       3       2
--R           q       q       q       q       q
--R   (64)  %B   + 2%B   + 2%B   + 2%B   + 2%B  + 2%B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 64
--S 65 of 350
a*b
--R
--R
--R             5
--R            q
--R   (65)  2%B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 65
--S 66 of 350
a/b
--R
--R
--R             4       3       2
--R            q       q       q      q
--R   (66)  3%B   + 2%B   + 4%B   + %B  + 3%B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 66
--S 67 of 350
a**1234
--R
--R
--R             5       4       3       2
--R            q       q       q       q       q
--R   (67)  2%B   + 2%B   + 2%B   + 2%B   + 2%B  + 2%B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 67
--S 68 of 350
a**(-1)

--R
--R
--R             5       4       3       2
--R            q       q       q       q       q
--R   (68)  4%B   + 4%B   + 4%B   + 4%B   + 4%B  + 4%B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 68
--S 69 of 350
g := generator()$F
--R
--R
--R   (69)  %B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 69
--S 70 of 350
(definingPolynomial()$F::SUP(F)).g
--R
--R
--R   (70)  0
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 70

———-

2.11 functions concerning the multiplicative cyclic group

— * —

--S 71 of 350
order(a)
--R
--R
--R   (71)  3
--R                                                        Type: PositiveInteger
--E 71
--S 72 of 350
g:=primitiveElement()$F
--R
--R
--R            2
--R           q
--R   (72)  %B   + %B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 72

--S 73 of 350
discreteLog(a)
--R
--R
--R   (73)  39216
--R                                                        Type: PositiveInteger
--E 73

———-

The next one should equal 0 — * —

--S 74 of 350
g**% - a
--R
--R
--R   (74)  0
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 74

———-

The next may fail — * —

--S 75 of 350
discreteLog(b,a)
--R
--R
--R   (75)  9804
--R                                          Type: Union(NonNegativeInteger,...)
--E 75

———-

2.12 special finite field functions

— * —

--S 76 of 350
extensionDegree()$F
--R
--R
--R   (76)  6
--R                                                        Type: PositiveInteger
--E 76
--S 77 of 350

degree(a)
--R
--R
--R   (77)  1
--R                                                        Type: PositiveInteger
--E 77
--S 78 of 350
normalElement()$F
--R
--R
--R   (78)  %B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 78
--S 79 of 350
definingPolynomial()$F
--R
--R
--R          6     5
--R   (79)  ?  + 6?  + 2? + 4
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))
--E 79
--S 80 of 350
minimalPolynomial(a)
--R
--R
--R   (80)  ? + 5
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))
--E 80
--S 81 of 350
Frobenius(a)
--R
--R
--R             5       4       3       2
--R            q       q       q       q       q
--R   (81)  2%B   + 2%B   + 2%B   + 2%B   + 2%B  + 2%B
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(7),?^6+6*?^5+2*?+4)
--E 81
--S 82 of 350
linearAssociatedOrder(a)
--R
--R
--R   (82)  ? + 6
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))
--E 82

--S 83 of 350
linearAssociatedLog(a)
--R
--R
--R           5     4     3     2
--R   (83)  2?  + 2?  + 2?  + 2?  + 2? + 2
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))
--E 83
--S 84 of 350
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
--R
--R      5      4      3      2
--R     q      q      q      q      q
--R   %B   + %B   + %B   + %B   + %B  + %B
--R       5       4       3       2
--R      q       q       q       q       q
--R   5%B   + 5%B   + 5%B   + 5%B   + 5%B  + 5%B
--R      5      4      3      2
--R     q      q      q      q      q
--R   %B   + %B   + %B   + %B   + %B  + %B
--R       5       4       3       2
--R      q       q       q       q       q
--R   6%B   + 6%B   + 6%B   + 6%B   + 6%B  + 6%B
--R       5       4       3       2
--R      q       q       q       q       q
--R   4%B   + 4%B   + 4%B   + 4%B   + 4%B  + 4%B
--R       5       4       3       2
--R      q       q       q       q       q
--R   4%B   + 4%B   + 4%B   + 4%B   + 4%B  + 4%B
--R       5       4       3       2
--R      q       q       q       q       q
--R   2%B   + 2%B   + 2%B   + 2%B   + 2%B  + 2%B
--R       5       4       3       2
--R      q       q       q       q       q
--R   2%B   + 2%B   + 2%B   + 2%B   + 2%B  + 2%B
--R                                                                   Type: Void
--E 84

———-

End of common finite field demonstration

2.13 finite field represented as cyclic group

Because a Zech logarithm table of half the field size is kept in memory during the computations, the size of the field should not be too big. Get a small prime

— * —

--S 85 of 350
p:=5
--R
--R
--R   (85)  5
--R                                                        Type: PositiveInteger
--E 85
--S 86 of 350
P:=PrimeField p
--R
--R
--R   (86)  PrimeField(5)
--R                                                                 Type: Domain
--E 86

———-

Get a small extension degree — * —

--S 87 of 350
d:=4
--R
--R
--R   (87)  4
--R                                                        Type: PositiveInteger
--E 87

———-

Get a primitive polynomial — * —

--S 88 of 350
f:=createPrimitivePoly(d)$FFPOLY(P)
--R
--R
--R          4    2
--R   (88)  ?  + ?  + 2? + 2
--R                              Type: SparseUnivariatePolynomial(PrimeField(5))
--E 88

———-

Construct the field — * —

--S 89 of 350
F:=FFCGP(P,f)
--R

--R
--R   (89)
--R   FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--R                                                                 Type: Domain
--E 89

———-

This field is the same as constructed by F:=FFCGX(P,d) or F:=FFCG(p,d)

2.14 demonstration of common finite field functions

The finite field domain is in variable F. Take some random elements — * —

--S 90 of 350
size()$F
--R
--R
--R   (90)  625
--R                                                     Type: NonNegativeInteger
--E 90
--S 91 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R           207
--R   (91)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 91
--S 92 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R           88
--R   (92)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 92

———-

Simple arithmetic — * —

--S 93 of 350
a+b
--R
--R

--R           70
--R   (93)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 93
--S 94 of 350
a-b
--R
--R
--R           237
--R   (94)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 94
--S 95 of 350
a*b
--R
--R
--R           295
--R   (95)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 95
--S 96 of 350
a/b
--R
--R
--R           119
--R   (96)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 96
--S 97 of 350
a**1234
--R
--R
--R           222
--R   (97)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 97
--S 98 of 350
a**(-1)
--R
--R
--R           417
--R   (98)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 98

--S 99 of 350
g := generator()$F
--R
--R
--R           1
--R   (99)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 99
--S 100 of 350
(definingPolynomial()$F::SUP(F)).g
--R
--R
--R   (100)  0
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 100

———-

2.15 functions concerning the multiplicative cyclic group

— * —

--S 101 of 350
order(a)
--R
--R
--R   (101)  208
--R                                                        Type: PositiveInteger
--E 101
--S 102 of 350
g:=primitiveElement()$F
--R
--R
--R            1
--R   (102)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 102
--S 103 of 350
discreteLog(a)
--R
--R
--R   (103)  207
--R                                                        Type: PositiveInteger
--E 103

———-

The next one should equal 0 — * —

--S 104 of 350
g**% - a
--R
--R
--R   (104)  0
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 104

———-

The next may fail — * —

--S 105 of 350
discreteLog(b,a)
--R
--R
--R   (105)  "failed"
--R                                                    Type: Union("failed",...)
--E 105

———-

Special finite field functions — * —

--S 106 of 350
extensionDegree()$F
--R
--R
--R   (106)  4
--R                                                        Type: PositiveInteger
--E 106
--S 107 of 350
degree(a)
--R
--R
--R   (107)  4
--R                                                        Type: PositiveInteger
--E 107
--S 108 of 350
normalElement()$F
--R
--R
--R            3

--R   (108)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 108
--S 109 of 350
definingPolynomial()$F
--R
--R
--R           4    2
--R   (109)  ?  + ?  + 2? + 2
--R                              Type: SparseUnivariatePolynomial(PrimeField(5))
--E 109
--S 110 of 350
minimalPolynomial(a)
--R
--R
--R           4    3    2
--R   (110)  ?  + ?  + ?  + 3? + 3
--R                              Type: SparseUnivariatePolynomial(PrimeField(5))
--E 110
--S 111 of 350
Frobenius(a)
--R
--R
--R            411
--R   (111)  %C
--RType: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(5),?^4+?^2+2*?+2)
--E 111
--S 112 of 350
linearAssociatedOrder(a)
--R
--R
--R           4
--R   (112)  ?  + 4
--R                              Type: SparseUnivariatePolynomial(PrimeField(5))
--E 112
--S 113 of 350
linearAssociatedLog(a)
--R
--R
--R            3
--R   (113)  3?  + 4? + 4
--R                              Type: SparseUnivariatePolynomial(PrimeField(5))
--E 113
--S 114 of 350

for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
--R
--R     468
--R   %C
--R     312
--R   %C
--R     390
--R   %C
--R     416
--R   %C
--R     207
--R   %C
--R     207
--R   %C
--R                                                                   Type: Void
--E 114

———-

End of common finite field demonstration

2.16 polynomial extension of a polynomial extension

Get a small prime, choose 2 or 3 — * —

--S 115 of 350
p:=3
--R
--R
--R   (115)  3
--R                                                        Type: PositiveInteger
--E 115
--S 116 of 350
P:=PrimeField p
--R
--R
--R   (116)  PrimeField(3)
--R                                                                 Type: Domain
--E 116

———-

Get two small extension degrees — * —

--S 117 of 350

d1:=2
--R
--R
--R   (117)  2
--R                                                        Type: PositiveInteger
--E 117
--S 118 of 350
d2:=3
--R
--R
--R   (118)  3
--R                                                        Type: PositiveInteger
--E 118

———-

Get irreducible polynomial of degree d1 over P — * —

--S 119 of 350
f1:=createIrreduciblePoly(d1)$FFPOLY(P)
--R
--R
--R           2
--R   (119)  ?  + 1
--R                              Type: SparseUnivariatePolynomial(PrimeField(3))
--E 119
--S 120 of 350
F1:=FFP(P,f1)
--R
--R
--R   (120)  FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1)
--R                                                                 Type: Domain
--E 120

———-

Get irreducible polynomial of degree d2 over F1 — * —

--S 121 of 350
f2:=createIrreduciblePoly(d2)$FFPOLY(F1)
--R
--R
--R           3
--R   (121)  ?  + ? + %D
--RType: SparseUnivariatePolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1))
--E 121

———-

Construct the field — * —

--S 122 of 350
F:=FFP(F1,f2)
--R
--R
--R   (122)
--R  FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(
--R  3),?^2+1),?^3+?+%D)
--R                                                                 Type: Domain
--E 122

———-

This field is the same as constructed by F:=FFX(F1,d2)

2.17 demonstration of common finite field functions

The finite field domain is in variable F. Take some random elements — * —

--S 123 of 350
size()$F
--R
--R
--R   (123)  729
--R                                                     Type: NonNegativeInteger
--E 123
--S 124 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R               2
--R   (124)  %D %E
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 124
--S 125 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R            2
--R   (125)  %E  + 2%E + %D + 2
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 125

———-

Simple arithmetic — * —

--S 126 of 350
a+b
--R
--R
--R                    2
--R   (126)  (%D + 1)%E  + 2%E + %D + 2
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 126
--S 127 of 350
a-b
--R
--R
--R                    2
--R   (127)  (%D + 2)%E  + %E + 2%D + 1
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 127
--S 128 of 350
a*b
--R
--R
--R                    2
--R   (128)  (%D + 2)%E  + (%D + 1)%E + 2
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 128
--S 129 of 350
a/b
--R
--R
--R                2
--R   (129)  2%D %E  + 2%D + 2
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 129
--S 130 of 350
a**1234
--R
--R
--R             2
--R   (130)  2%E  + %D %E + 2
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 130
--S 131 of 350

a**(-1)
--R
--R
--R               2
--R   (131)  %D %E  + %E + %D
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 131
--S 132 of 350
g := generator()$F
--R
--R
--R   (132)  %E
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 132
--S 133 of 350
(definingPolynomial()$F::SUP(F)).g
--R
--R
--R   (133)  0
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 133

———-

2.18 functions concerning the multiplicative cyclic group

— * —

--S 134 of 350
order(a)
--R
--R
--R   (134)  52
--R                                                        Type: PositiveInteger
--E 134
--S 135 of 350
g:=primitiveElement()$F
--R
--R
--R   (135)  %E + 1
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 135
--S 136 of 350
discreteLog(a)

--R
--R
--R   (136)  462
--R                                                        Type: PositiveInteger
--E 136

———-

The next one should equal 0 — * —

--S 137 of 350
g**% - a
--R
--R
--R   (137)  0
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 137

———-

The next may fail — * —

--S 138 of 350
discreteLog(b,a)
--R
--R
--R   (138)  154
--R                                          Type: Union(NonNegativeInteger,...)
--E 138

———-

Special finite field functions — * —

--S 139 of 350
extensionDegree()$F
--R
--R
--R   (139)  3
--R                                                        Type: PositiveInteger
--E 139
--S 140 of 350
degree(a)
--R
--R
--R   (140)  3
--R                                                        Type: PositiveInteger

--E 140
--S 141 of 350
normalElement()$F
--R
--R
--R            2
--R   (141)  %E  + %E
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 141
--S 142 of 350
definingPolynomial()$F
--R
--R
--R           3
--R   (142)  ?  + ? + %D
--RType: SparseUnivariatePolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1))
--E 142
--S 143 of 350
minimalPolynomial(a)
--R
--R
--R           3        2
--R   (143)  ?  + 2%D ?  + 2? + 2%D
--RType: SparseUnivariatePolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1))
--E 143
--S 144 of 350
Frobenius(a)
--R
--R
--R               2
--R   (144)  %D %E  + 2%E + 2%D
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+?+%D)
--E 144
--S 145 of 350
linearAssociatedOrder(a)
--R
--R
--R           3
--R   (145)  ?  + 2
--RType: SparseUnivariatePolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1))
--E 145
--S 146 of 350
linearAssociatedLog(a)
--R

--R
--R                    2
--R   (146)  (2%D + 2)?  + (2%D + 1)?
--RType: SparseUnivariatePolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1))
--E 146
--S 147 of 350
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
--R
--R   %D
--R   %D
--R        2
--R   %D %E
--R        2
--R   %D %E
--R                                                                   Type: Void
--E 147

———-

End of common finite field demonstration

3 polynomial extension of a normal extension

Get normal polynomial of degree d1 over P — * —

--S 148 of 350
f1:=createNormalPoly(d1)$FFPOLY(P)
--R
--R
--R           2
--R   (148)  ?  + 2? + 2
--R                              Type: SparseUnivariatePolynomial(PrimeField(3))
--E 148
--S 149 of 350
F1:=FFNBP(P,f1)
--R
--R
--R   (149)  FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2)
--R                                                                 Type: Domain
--E 149

———-

Get irreducible polynomial of degree d2 over F1 — * —

--S 150 of 350
f2:=createIrreduciblePoly(d2)$FFPOLY(F1)
--R
--R
--R           3
--R   (150)  ?  + ? + %F
--RType: SparseUnivariatePolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2))
--E 150

———-

Construct the field — * —

--S 151 of 350
F:=FFP(F1,f2)
--R
--R
--R   (151)
--R  FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(
--R  PrimeField(3),?^2+2*?+2),?^3+?+%F)
--R                                                                 Type: Domain
--E 151 of 350

———-

This field is the same as constructed by F:=FFX(F1,d2)

3.1 demonstration of common finite field functions

The finite field domain is in variable F. Take some random elements — * —

--S 152 of 250
size()$F
--R
--R
--R   (152)  729
--R                                                     Type: NonNegativeInteger
--E 152
--S 153 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R            q  2
--R   (153)  %F %G
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 153

--S 154 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R               2              q
--R   (154)  %F %G  + 2%F %G + %F  + 2%F
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 154

———-

Simple arithmetic — * —

--S 155 of 350
a+b
--R
--R
--R            2              q
--R   (155)  %G  + 2%F %G + %F  + 2%F
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 155
--S 156 of 350
a-b
--R
--R
--R             q         2              q
--R   (156)  (%F  + 2%F)%G  + %F %G + 2%F  + %F
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 156
--S 157 of 350
a*b
--R
--R
--R            q  2      q
--R   (157)  %F %G  + 2%F %G + 2%F
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 157
--S 158 of 350
a/b
--R
--R
--R            2
--R   (158)  %G  + %G
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 158

--S 159 of 350
a**1234
--R
--R
--R            q  2             q
--R   (159)  %F %G  + %F %G + %F  + 2%F
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 159
--S 160 of 350
a**(-1)
--R
--R
--R            q  2          q
--R   (160)  %F %G  + %G + %F
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 160
--S 161 of 350
g := generator()$F
--R
--R
--R   (161)  %G
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 161
--S 162 of 350
(definingPolynomial()$F::SUP(F)).g
--R
--R
--R   (162)  0
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 162

———-

3.2 functions concerning the multiplicative cyclic group

— * —

--S 163 of 350
order(a)
--R
--R
--R   (163)  728
--R                                                        Type: PositiveInteger
--E 163

--S 164 of 350
g:=primitiveElement()$F
--R
--R
--R   (164)  %G
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 164
--S 165 of 350
discreteLog(a)
--R
--R
--R   (165)  639
--R                                                        Type: PositiveInteger
--E 165

———-

The next one should equal 0 — * —

--S 166 of 350
g**% - a
--R
--R
--R   (166)  0
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 166

———-

The next may fail — * —

--S 167 of 350
discreteLog(b,a)
--R
--R   discreteLog: second argument not in cyclic group generated by first argument
--R
--R   (167)  "failed"
--R                                                    Type: Union("failed",...)
--E 167

———-

3.3 special finite field functions

— * —

--S 168 of 350
extensionDegree()$F
--R
--R
--R   (168)  3
--R                                                        Type: PositiveInteger
--E 168
--S 169 of 350
degree(a)
--R
--R
--R   (169)  3
--R                                                        Type: PositiveInteger
--E 169
--S 170 of 350
normalElement()$F
--R
--R
--R            2
--R   (170)  %G
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)
--E 170
--S 171 of 350
definingPolynomial()$F
--R
--R
--R           3
--R   (171)  ?  + ? + %F
--RType: SparseUnivariatePolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2))
--E 171
--S 172 of 350
minimalPolynomial(a)
--R
--R
--R           3      q 2       q             q
--R   (172)  ?  + 2%F ?  + (2%F  + %F)? + 2%F
--RType: SparseUnivariatePolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2))
--E 172
--S 173 of 350
Frobenius(a)
--R
--R
--R            q  2               q
--R   (173)  %F %G  + 2%F %G + 2%F
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+?+%F)

--E 173
--S 174 of 350
linearAssociatedOrder(a)
--R
--R
--R           3      q
--R   (174)  ?  + 2%F  + 2%F
--RType: SparseUnivariatePolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2))
--E 174
--S 175 of 350
linearAssociatedLog(a)
--R
--R
--R            q
--R   (175)  %F
--RType: SparseUnivariatePolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2))
--E 175
--S 176 of 350
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
--R
--R     q
--R   %F
--R     q
--R   %F
--R     q  2
--R   %F %G
--R     q  2
--R   %F %G
--R                                                                   Type: Void
--E 176

———-

End of common finite field demonstration

3.4 polynomial extension of a cyclic extension

Get primitive polynomial of degree d1 over P — * —

--S 177 of 350
f1:=createPrimitivePoly(d1)$FFPOLY(P)
--R
--R
--R           2

--R   (177)  ?  + ? + 2
--R                              Type: SparseUnivariatePolynomial(PrimeField(3))
--E 177
--S 178 of 350
F1:=FFCGP(P,f1)
--R
--R
--R   (178)  FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2)
--R                                                                 Type: Domain
--E 178

———-

Get irreducible polynomial of degree d2 over F1 — * —

--S 179 of 350
f2:=createIrreduciblePoly(d2)$FFPOLY(F1)
--R
--R
--R           3         1
--R   (179)  ?  + ? + %H
--RType: SparseUnivariatePolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2))
--E 179

———-

Construct the field — * —

--S 180 of 350
F:=FFP(F1,f2)
--R
--R
--R   (180)
--R  FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(
--R  PrimeField(3),?^2+?+2),?^3+?+%H^1)
--R                                                                 Type: Domain
--E 180

———-

This field is the same as constructed by F:=FFX(F1,d2)

3.5 demonstration of common finite field functions

The finite field domain is in variable F. Take some random elements — * —

--S 181 of 350
size()$F
--R
--R
--R   (181)  729
--R                                                     Type: NonNegativeInteger
--E 181
--S 192 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R            2  2
--R   (182)  %H %I
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 182
--S 183 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R            2     1       4
--R   (183)  %I  + %H %I + %H
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 183

———-

Simple arithmetic — * —

--S 184 of 350
a+b
--R
--R
--R            3  2     1       4
--R   (184)  %H %I  + %H %I + %H
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 184
--S 185 of 350
a-b
--R
--R
--R            5  2     5
--R   (185)  %H %I  + %H %I + 1
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 185
--S 186 of 350

a*b
--R
--R
--R            2  2     3
--R   (186)  %H %I  + %H %I + 1
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 186
--S 187 of 350
a/b
--R
--R
--R            1  2     6
--R   (187)  %H %I  + %H %I
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 187
--S 188 of 350
a**1234
--R
--R
--R            5  2     7
--R   (188)  %H %I  + %H %I + 1
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 188
--S 189 of 350
a**(-1)
--R
--R
--R            4  2     1       4
--R   (189)  %H %I  + %H %I + %H
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 189
--S 190 of 350
g := generator()$F
--R
--R
--R   (190)  %I
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 190
--S 191 of 350
(definingPolynomial()$F::SUP(F)).g
--R
--R
--R   (191)  0
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 191

3.6 functions concerning the multiplicative cyclic group

— * —

--S 192 of 350
order(a)
--R
--R
--R   (192)  91
--R                                                        Type: PositiveInteger
--E 192
--S 193 of 350
g:=primitiveElement()$F
--R
--R
--R   (193)  %I
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 193
--S 194 of 350
discreteLog(a)
--R
--R
--R   (194)  184
--R                                                        Type: PositiveInteger
--E 194

———-

The next one should equal 0 — * —

--S 195 of 350
g**% - a
--R
--R
--R   (195)  0
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 195

———-

The next may fail — * —

--S 196 of 350
discreteLog(b,a)
--R
--R
--R   (196)  352
--R                                          Type: Union(NonNegativeInteger,...)
--E 196

———-

Special finite field functions — * —

--S 197 of 350
extensionDegree()$F
--R
--R
--R   (197)  3
--R                                                        Type: PositiveInteger
--E 197
--S 198 of 350
degree(a)
--R
--R
--R   (198)  3
--R                                                        Type: PositiveInteger
--E 198
--S 199 of 350
normalElement()$F
--R
--R
--R            2
--R   (199)  %I
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 199
--S 200 of 350
definingPolynomial()$F
--R
--R
--R           3         1
--R   (200)  ?  + ? + %H
--RType: SparseUnivariatePolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2))
--E 200
--S 201 of 350
minimalPolynomial(a)
--R

--R
--R           3     6 2     4      4
--R   (201)  ?  + %H ?  + %H ? + %H
--RType: SparseUnivariatePolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2))
--E 201
--S 202 of 350
Frobenius(a)
--R
--R
--R            2  2          6
--R   (202)  %H %I  + %I + %H
--RType: FiniteFieldExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+?+%H^1)
--E 202
--S 203 of 350
linearAssociatedOrder(a)
--R
--R
--R           3     4
--R   (203)  ?  + %H
--RType: SparseUnivariatePolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2))
--E 203
--S 204 of 350
linearAssociatedLog(a)
--R
--R
--R            2
--R   (204)  %H
--RType: SparseUnivariatePolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2))
--E 204
--S 205 of 350
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
--R
--R   1
--R     2
--R   %H
--R     2  2
--R   %H %I
--R     2  2
--R   %H %I
--R                                                                   Type: Void
--E 205

———- End of common finite field demonstration

3.7 normal extension of a polynomial extension

Get a small prime. Get a irreducible polynomial of degree d1 over P — * —

--S 206 of 350
f1:=createIrreduciblePoly(d1)$FFPOLY(P)
--R
--R
--R           2
--R   (206)  ?  + 1
--R                              Type: SparseUnivariatePolynomial(PrimeField(3))
--E 206
--S 207 of 350
F1:=FFP(P,f1)
--R
--R
--R   (207)  FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1)
--R                                                                 Type: Domain
--E 207

———-

Get a normal polynomial of degree d2 over F1 — * —

--S 208 of 350
f2:=createNormalPoly(d2)$FFPOLY(F1)
--R
--R
--R           3     2
--R   (208)  ?  + 2?  + 1
--RType: SparseUnivariatePolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1))
--E 208

———-

Construct the field — * —

--S 209 of 350
F:=FFNBP(F1,f2)
--R
--R
--R   (209)
--R  FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(
--R  PrimeField(3),?^2+1),?^3+2*?^2+1)
--R                                                                 Type: Domain

--E 209

———-

This field is the same as constructed by F:=FFX(F1,d2)

3.8 demonstration of common finite field functions

The finite field domain is in variable F Take some random elements — * —

--S 210 of 350
size()$F
--R
--R
--R   (210)  729
--R                                                     Type: NonNegativeInteger
--E 210
--S 211 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R                2
--R               q
--R   (211)  %D %J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 211
--S 212 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R             2
--R            q       q
--R   (212)  %J   + 2%J  + (%D + 2)%J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 212

———-

Simple arithmetic — * —

--S 213 of 350
a+b
--R
--R
--R                     2
--R                    q       q

--R   (213)  (%D + 1)%J   + 2%J  + (%D + 2)%J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 213
--S 214 of 350
a-b
--R
--R
--R                     2
--R                    q      q
--R   (214)  (%D + 2)%J   + %J  + (2%D + 1)%J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 214
--S 215 of 350
a*b
--R
--R
--R                     2
--R                    q         q
--R   (215)  (%D + 2)%J   + %D %J  + (2%D + 1)%J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 215
--S 216 of 350
a/b
--R
--R
--R              2
--R             q         q
--R   (216)  2%J   + %D %J  + 2%J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 216
--S 217 of 350
a**1234
--R
--R
--R            q
--R   (217)  %J  + 2%J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 217
--S 218 of 350
a**(-1)
--R
--R
--R                q
--R   (218)  2%D %J  + %D %J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)

--E 218
--S 219 of 350
g := generator()$F
--R
--R
--R   (219)  %J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 219
--S 220 of 350
(definingPolynomial()$F::SUP(F)).g
--R
--R
--R   (220)  0
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 220

———-

3.9 functions concerning the multiplicative cyclic group

— * —

--S 221 of 350
order(a)
--R
--R
--R   (221)  52
--R                                                        Type: PositiveInteger
--E 221
--S 222 of 350
g:=primitiveElement()$F
--R
--R
--R                    q
--R   (222)  (%D + 1)%J  + 2%J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 222
--S 223 of 350
discreteLog(a)
--R
--R
--R   (223)  462
--R                                                        Type: PositiveInteger
--E 223

--S 224 of 350
g**% - a
--R
--R
--R   (224)  0
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 224

———-

The next may fail — * —

--S 225 of 350
discreteLog(b,a)
--R
--R
--R   (225)  70
--R                                          Type: Union(NonNegativeInteger,...)
--E 225

———-

3.10 special finite field functions

— * —

--S 226 of 350
extensionDegree()$F
--R
--R
--R   (226)  3
--R                                                        Type: PositiveInteger
--E 226
--S 227 of 350
degree(a)
--R
--R
--R   (227)  3
--R                                                        Type: PositiveInteger
--E 227

--S 228 of 350
normalElement()$F
--R
--R
--R   (228)  %J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 228
--S 229 of 350
definingPolynomial()$F
--R
--R
--R           3     2
--R   (229)  ?  + 2?  + 1
--RType: SparseUnivariatePolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1))
--E 229
--S 230 of 350
minimalPolynomial(a)
--R
--R
--R           3        2
--R   (230)  ?  + 2%D ?  + 2%D
--RType: SparseUnivariatePolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1))
--E 230
--S 231 of 350
Frobenius(a)
--R
--R
--R   (231)  %D %J
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1),?^3+2*?^2+1)
--E 231
--S 232 of 350
linearAssociatedOrder(a)
--R
--R
--R           3
--R   (232)  ?  + 2
--RType: SparseUnivariatePolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1))
--E 232
--S 233 of 350
linearAssociatedLog(a)
--R
--R
--R              2
--R   (233)  %D ?
--RType: SparseUnivariatePolynomial(FiniteFieldExtensionByPolynomial(PrimeField(3),?^2+1))

--E 233
--S 234 of 350
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
--R
--R         2
--R        q         q
--R   %D %J   + %D %J  + %D %J
--R         2
--R        q         q
--R   %D %J   + %D %J  + %D %J
--R         2
--R        q
--R   %D %J
--R         2
--R        q
--R   %D %J
--R                                                                   Type: Void
--E 234

———-

End of common finite field demonstration

3.11 normal extension of a normal extension

Get a normal polynomial of degree d1 over P — * —

--S 235 of 350
f1:=createNormalPoly(d1)$FFPOLY(P)
--R
--R
--R           2
--R   (235)  ?  + 2? + 2
--R                              Type: SparseUnivariatePolynomial(PrimeField(3))
--E 235
--S 236 of 350
F1:=FFNBP(P,f1)
--R
--R
--R   (236)  FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2)
--R                                                                 Type: Domain
--E 236

———- Get a normal polynomial of degree d2 over F1

— * —

--S 237 of 350
f2:=createNormalPoly(d2)$FFPOLY(F1)
--R
--R
--R           3       q        2     q
--R   (237)  ?  + (2%F  + 2%F)?  + %F  + %F
--RType: SparseUnivariatePolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2))
--E 237

———-

Construct the field — * —

--S 238 of 350
F:=FFNBP(F1,f2)
--R
--R
--R   (238)
--R  FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionBy
--R  Polynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--R                                                                 Type: Domain
--E 238

———-

This field is the same as constructed by F:=FFX(F1,d2)

3.12 demonstration of common finite field functions

The finite field domain is in variable F Take some random elements — * —

--S 239 of 350
size()$F
--R
--R
--R   (239)  729
--R                                                     Type: NonNegativeInteger
--E 239
--S 240 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R                2
--R            q  q
--R   (240)  %F %K

--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 240
--S 241 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R                2
--R               q          q      q
--R   (241)  %F %K   + 2%F %K  + (%F  + 2%F)%K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 241

———-

Simple arithmetic — * —

--S 242 of 350
a+b
--R
--R
--R             2
--R            q          q      q
--R   (242)  %K   + 2%F %K  + (%F  + 2%F)%K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 242
--S 243 of 350
a-b
--R
--R
--R                        2
--R             q         q         q       q
--R   (243)  (%F  + 2%F)%K   + %F %K  + (2%F  + %F)%K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 243
--S 244 of 350
a*b
--R
--R
--R                2
--R            q  q        q         q      q
--R   (244)  %F %K   + (2%F  + 2%F)%K  + 2%F %K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 244
--S 245 of 350
a/b

--R
--R
--R                         2
--R              q         q       q         q       q
--R   (245)  (2%F  + 2%F)%K   + (%F  + 2%F)%K  + (2%F  + 2%F)%K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 245
--S 246 of 350
a**1234
--R
--R
--R             q         q       q
--R   (246)  (%F  + 2%F)%K  + (2%F  + %F)%K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 246
--S 247 of 350
a**(-1)
--R
--R
--R                q
--R   (247)  2%F %K  + %F %K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 247
--S 248 of 350
g := generator()$F
--R
--R
--R   (248)  %K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 248
--S 249 of 350
(definingPolynomial()$F::SUP(F)).g
--R
--R
--R   (249)  0
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 249

———-

3.13 functions concerning the multiplicative cyclic group

— * —

--S 250 of 350
order(a)
--R
--R
--R   (250)  104
--R                                                        Type: PositiveInteger
--E 250
--S 251 of 350
g:=primitiveElement()$F
--R
--R
--R               q     q
--R   (251)  %F %K  + %F %K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 251
--S 252 of 350
discreteLog(a)
--R
--R
--R   (252)  343
--R                                                        Type: PositiveInteger
--E 252

———-

The next one should equal 0 — * —

--S 253 of 350
g**% - a
--R
--R
--R   (253)  0
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 253

———-

The next may fail — * —

--S 254 of 350
discreteLog(b,a)
--R
--R   discreteLog: second argument not in cyclic group generated by first argument
--R
--R   (254)  "failed"
--R                                                    Type: Union("failed",...)
--E 254

3.14 special finite field functions

— * —

--S 255 of 350
extensionDegree()$F
--R
--R
--R   (255)  3
--R                                                        Type: PositiveInteger
--E 255
--S 256 of 350
degree(a)
--R
--R
--R   (256)  3
--R                                                        Type: PositiveInteger
--E 256
--S 257 of 350
normalElement()$F
--R
--R
--R   (257)  %K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 257
--S 258 of 350
definingPolynomial()$F
--R
--R
--R           3       q        2     q
--R   (258)  ?  + (2%F  + 2%F)?  + %F  + %F
--RType: SparseUnivariatePolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2))
--E 258
--S 259 of 350
minimalPolynomial(a)
--R
--R
--R           3      q 2
--R   (259)  ?  + 2%F ?  + %F
--RType: SparseUnivariatePolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2))
--E 259

--S 260 of 350
Frobenius(a)
--R
--R
--R            q
--R   (260)  %F %K
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2),?^3+(2*%F^q+2*%F)*?^2+(%F^q+%F))
--E 260
--S 261 of 350
linearAssociatedOrder(a)
--R
--R
--R           3      q
--R   (261)  ?  + 2%F  + 2%F
--RType: SparseUnivariatePolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2))
--E 261
--S 262 of 350
linearAssociatedLog(a)
--R
--R
--R            q 2
--R   (262)  %F ?
--RType: SparseUnivariatePolynomial(FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^2+2*?+2))
--E 262
--S 263 of 350
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
--R
--R          2
--R         q          q
--R   2%F %K   + 2%F %K  + 2%F %K
--R         2
--R     q  q      q  q     q
--R   %F %K   + %F %K  + %F %K
--R         2
--R     q  q
--R   %F %K
--R         2
--R     q  q
--R   %F %K
--R                                                                   Type: Void
--E 263

———- End of common finite field demonstration

3.15 normal extension of a cyclic extension

Get primitive polynomial of degree d1 over P — * —

--S 264 of 350
f1:=createPrimitivePoly(d1)$FFPOLY(P)
--R
--R
--R           2
--R   (264)  ?  + ? + 2
--R                              Type: SparseUnivariatePolynomial(PrimeField(3))
--E 264
--S 265 of 350
F1:=FFCGP(P,f1)
--R
--R
--R   (265)  FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2)
--R                                                                 Type: Domain
--E 265

———-

Get a normal polynomial of degree d2 over F1 — * —

--S 266 of 350
f2:=createNormalPoly(d2)$FFPOLY(F1)
--R
--R
--R           3     4 2
--R   (266)  ?  + %H ?  + 1
--RType: SparseUnivariatePolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2))
--E 266

———-

Construct the field — * —

--S 267 of 350
F:=FFNBP(F1,f2)
--R
--R
--R   (267)
--R  FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionBy
--R  Polynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--R                                                                 Type: Domain

--E 267

———-

This field is the same as constructed by F:=FFX(F1,d2)

3.16 demonstration of common finite field functions

The finite field domain is in variable F. Take some random elements — * —

--S 268 of 350
size()$F
--R
--R
--R   (268)  729
--R                                                     Type: NonNegativeInteger
--E 268
--S 269 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R                2
--R            2  q
--R   (269)  %H %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 269
--S 270 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R             2
--R            q      1  q     4
--R   (270)  %L   + %H %L  + %H %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 270

———-

Simple arithmetic — * —

--S 271 of 350
a+b
--R
--R
--R                2
--R            3  q      1  q     4

--R   (271)  %H %L   + %H %L  + %H %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 271
--S 272 of 350
a-b
--R
--R
--R                2
--R            5  q      5  q
--R   (272)  %H %L   + %H %L  + %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 272
--S 273 of 350
a*b
--R
--R
--R                2
--R            7  q      q     6
--R   (273)  %H %L   + %L  + %H %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 273
--S 274 of 350
a/b
--R
--R
--R                2
--R            2  q      5  q     6
--R   (274)  %H %L   + %H %L  + %H %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 274
--S 275 of 350
a**1234
--R
--R
--R            q     4
--R   (275)  %L  + %H %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 275
--S 276 of 350
a**(-1)
--R
--R
--R            6  q     2
--R   (276)  %H %L  + %H %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))

--E 276
--S 277 of 350
g := generator()$F
--R
--R
--R   (277)  %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 277
--S 278 of 350
(definingPolynomial()$F::SUP(F)).g
--R
--R
--R   (278)  0
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 278

———-

3.17 functions concerning the multiplicative cyclic group

— * —

--S 279 of 350
order(a)
--R
--R
--R   (279)  52
--R                                                        Type: PositiveInteger
--E 279
--S 280 of 350
g:=primitiveElement()$F
--R
--R
--R            1  q     2
--R   (280)  %H %L  + %H %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 280
--S 281 of 350
discreteLog(a)
--R
--R
--R   (281)  98
--R                                                        Type: PositiveInteger
--E 281

--S 282 of 350
g**% - a
--R
--R
--R   (282)  0
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 282

———-

The next may fail — * —

--S 283 of 350
discreteLog(b,a)
--R
--R
--R   (283)  574
--R                                          Type: Union(NonNegativeInteger,...)
--E 283

———-

3.18 special finite field functions

— * —

--S 284 of 350
extensionDegree()$F
--R
--R
--R   (284)  3
--R                                                        Type: PositiveInteger
--E 284
--S 285 of 350
degree(a)
--R
--R
--R   (285)  3
--R                                                        Type: PositiveInteger
--E 285

--S 286 of 350
normalElement()$F
--R
--R
--R   (286)  %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 286
--S 287 of 350
definingPolynomial()$F
--R
--R
--R           3     4 2
--R   (287)  ?  + %H ?  + 1
--RType: SparseUnivariatePolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2))
--E 287
--S 288 of 350
minimalPolynomial(a)
--R
--R
--R           3     6 2     6
--R   (288)  ?  + %H ?  + %H
--RType: SparseUnivariatePolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2))
--E 288
--S 289 of 350
Frobenius(a)
--R
--R
--R            2
--R   (289)  %H %L
--RType: FiniteFieldNormalBasisExtensionByPolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2),?^3+%H^4*?^2+(1))
--E 289
--S 290 of 350
linearAssociatedOrder(a)
--R
--R
--R           3     4
--R   (290)  ?  + %H
--RType: SparseUnivariatePolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2))
--E 290 of 350
--S 291 of 350
linearAssociatedLog(a)
--R
--R
--R            2 2
--R   (291)  %H ?

--RType: SparseUnivariatePolynomial(FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^2+?+2))
--E 291
--S 292 of 350
for d in divisors extensionDegree()$F repeat
        print(norm(a,d::PI)::OUTFORM)
        print(trace(a,d::PI)::OUTFORM)
--R
--R         2
--R     2  q      2  q     2
--R   %H %L   + %H %L  + %H %L
--R         2
--R     2  q      2  q     2
--R   %H %L   + %H %L  + %H %L
--R         2
--R     2  q
--R   %H %L
--R         2
--R     2  q
--R   %H %L
--R                                                                   Type: Void
--E 292

———-

End of common finite field demonstration

3.19 finite field homomorphisms demonstration

— * —

--S 293 of 350
P3:= PF 3
--R
--R
--R   (293)  PrimeField(3)
--R                                                                 Type: Domain
--E 293

———-

Create a irreducible, a normal and a primitive polynomial — * —

--S 294 of 350
fi:=createIrreduciblePoly(6)$FFPOLY(P3)
--R
--R
--R           6

--S 295 of 350
fn:=createNormalPoly(6)$FFPOLY(P3)
--R
--R
--R           6     5    3
--R   (295)  ?  + 2?  + ?  + 1
--R                              Type: SparseUnivariatePolynomial(PrimeField(3))
--E 295
--S 296 of 350
fp:=createPrimitivePoly(3)$FFPOLY(P3)
--R
--R
--R           3
--R   (296)  ?  + 2? + 1
--R                              Type: SparseUnivariatePolynomial(PrimeField(3))
--E 296

———-

3.20 coercions between field with the same defining polynomials

— * —

--S 297 of 350
F:=FFP(P3,fn)
--R
--R
--R   (297)  FiniteFieldExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--R                                                                 Type: Domain
--E 297
--S 298 of 350
N:=FFNBP(P3,fn)
--R
--R
--R   (298)
--R   FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--R                                                                 Type: Domain
--E 298
--S 299 of 350
a:=index(size()$F quo 3)$F
--R

--R
--R            5
--R   (299)  %M
--R        Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 299
--S 300 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R            4      2
--R   (300)  %M  + 2%M  + %M + 2
--R        Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 300
--S 301 of 350
an:=coerce(a)$FFHOM(F,P3,N)
--R
--R
--R             4      3
--R            q      q      q
--R   (301)  %N   + %N   + %N  + 2%N
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 301
--S 302 of 350
bn:=coerce(b)$FFHOM(F,P3,N)
--R
--R
--R             3      2
--R            q      q       q
--R   (302)  %N   + %N   + 2%N  + 2%N
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 302
--S 303 of 350
cn := an*bn
--R
--R
--R              5       4      3
--R             q       q      q      q
--R   (303)  2%N   + 2%N   + %N   + %N
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 303
--S 304 of 350
coerce(cn)$FFHOM(F,P3,N)
--R
--R
--R            5      3      2

--R   (304)  %M  + 2%M  + 2%M
--R        Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 304

———-

Should be the same as — * —

--S 305 of 350
c:=a*b
--R
--R
--R            5      3      2
--R   (305)  %M  + 2%M  + 2%M
--R        Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 305

———-

3.21 coercion between fields with different extension polynomials

— * —

--S 306 of 350
F:=FFP(P3,fi)
--R
--R
--R   (306)  FiniteFieldExtensionByPolynomial(PrimeField(3),?^6+?+2)
--R                                                                 Type: Domain
--E 306
--S 307 of 350
N:=FFNBP(P3,fn)
--R
--R
--R   (307)
--R   FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--R                                                                 Type: Domain
--E 307
--S 308 of 350
a:=index(size()$F quo 3)$F
--R
--R
--R            5
--R   (308)  %O
--R                Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^6+?+2)

--E 308
--S 309 of 350
b:=index(size()$F quo 7)$F
--R
--R
--R            4      2
--R   (309)  %O  + 2%O  + %O + 2
--R                Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^6+?+2)
--E 309
--S 310 of 350
an:=coerce(a)$FFHOM(F,P3,N)
--R
--R
--R              5      4       3      2
--R             q      q       q      q      q
--R   (310)  2%N   + %N   + 2%N   + %N   + %N
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 310
--S 311 of 350
bn:=coerce(b)$FFHOM(F,P3,N)
--R
--R
--R              3      2
--R             q      q
--R   (311)  2%N   + %N
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 311
--S 312 of 350
cn := an*bn
--R
--R
--R              5      4      3      2
--R             q      q      q      q      q
--R   (312)  2%N   + %N   + %N   + %N   + %N  + 2%N
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 312
--S 313 of 350
coerce(cn)$FFHOM(F,P3,N)
--R
--R
--R             5      4     3     2
--R   (313)  2%O  + 2%O  + %O  + %O  + %O + 1
--R                Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^6+?+2)
--E 313

———-

Should be the same as — * —

--S 314 of 350
c:=a*b
--R
--R
--R             5      4     3     2
--R   (314)  2%O  + 2%O  + %O  + %O  + %O + 1
--R                Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^6+?+2)
--E 314

———-

3.22 coercion between fields of different extension degree

— * —

--S 315 of 350
C:=FFCGP(P3,fp)
--R
--R
--R   (315)  FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^3+2*?+1)
--R                                                                 Type: Domain
--E 315
--S 316 of 350
N:=FFNBP(P3,fn)
--R
--R
--R   (316)
--R   FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--R                                                                 Type: Domain
--E 316
--S 317 of 350
a:=index(size()$C quo 3)$C
--R
--R
--R            8
--R   (317)  %P
--R   Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^3+2*?+1)
--E 317
--S 318 of 350
b:=index(size()$C quo 7)$C
--R

--R
--R            2
--R   (318)  %P
--R   Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^3+2*?+1)
--E 318
--S 319 of 350
an:=coerce(a)$FFHOM(C,P3,N)
--R
--R
--R              4       3
--R             q       q       q
--R   (319)  2%N   + 2%N   + 2%N  + 2%N
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 319
--S 320 of 350
bn:=coerce(b)$FFHOM(C,P3,N)
--R
--R
--R              5       2
--R             q       q
--R   (320)  2%N   + 2%N
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 320
--S 321 of 350
cn := an+bn
--R
--R
--R              5       4       3       2
--R             q       q       q       q       q
--R   (321)  2%N   + 2%N   + 2%N   + 2%N   + 2%N  + 2%N
--RType: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^6+2*?^5+?^3+1)
--E 321
--S 322 of 350
coerce(cn)$FFHOM(C,P3,N)
--R
--R
--R            13
--R   (322)  %P
--R   Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^3+2*?+1)
--E 322

———-

Should be the same as — * —

--S 323 of 350

c:=a+b
--R
--R
--R            13
--R   (323)  %P
--R   Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^3+2*?+1)
--E 323

———-

3.23 comparison of computation times for arithmetic operations

— * —

--S 324 of 350
f:=createPrimitiveNormalPoly(5)$FFPOLY(P3)
--R
--R
--R           5     4
--R   (324)  ?  + 2?  + 1
--R                              Type: SparseUnivariatePolynomial(PrimeField(3))
--E 324
--S 325 of 350
FP:=FFP(P3,f)
--R
--R
--R   (325)  FiniteFieldExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--R                                                                 Type: Domain
--E 325
--S 326 of 350
Fc:=FFCGP(P3,f)  -- FC is a domain abbreviation
--R
--R
--R   (326)
--R   FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--R                                                                 Type: Domain
--E 326
--S 327 of 350
FN:=FFNBP(P3,f)
--R
--R
--R   (327)
--R   FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--R                                                                 Type: Domain
--E 327

--S 328 of 350
ap:=index(size()$FP quo 3)$FP
--R
--R
--R            4
--R   (328)  %Q
--R            Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 328
--S 329 of 350
ac:=coerce(ap)$FFHOM(Fc,P3,FP)
--R
--R
--R            4
--R   (329)  %R
--R Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 329
--S 330 of 350
an:=coerce(ap)$FFHOM(FN,P3,FP)
--R
--R
--R              3       2
--R             q       q       q
--R   (330)  2%S   + 2%S   + 2%S  + %S
--R Type: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 330
--S 331 of 350
bp:=index(size()$FP quo 7)$FP
--R
--R
--R            3
--R   (331)  %Q  + 2%Q + 1
--R            Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 331
--S 332 of 350
bc:=coerce(bp)$FFHOM(Fc,P3,FP)
--R
--R
--R            133
--R   (332)  %R
--R Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 332
--S 333 of 350
bn:=coerce(bp)$FFHOM(FN,P3,FP)
--R

--R
--R             4      3      2
--R            q      q      q       q
--R   (333)  %S   + %S   + %S   + 2%S
--R Type: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 333

———-

The next are to initialize the fields — * —

--S 334 of 350
ac+bc
--R
--R
--R            187
--R   (334)  %R
--R Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 334
--S 335 of 350
an*bn
--R
--R
--R             4      2
--R            q      q      q
--R   (335)  %S   + %S   + %S  + 2%S
--R Type: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 335

———-

Now we can compare

3.24 Addition

— * —

--S 336 of 350
ap+bp
--R
--R
--R            4     3
--R   (336)  %Q  + %Q  + 2%Q + 1
--R            Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 336
--S 337 of 350

an+bn
--R
--R
--R             4
--R            q      q
--R   (337)  %S   + %S  + %S
--R Type: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 337
--S 338 of 350
ac+bc
--R
--R
--R            187
--R   (338)  %R
--R Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 338

———-

3.25 Multiplication

— * —

--S 339 of 350
ap*bp
--R
--R
--R            4      2
--R   (339)  %Q  + 2%Q  + 2%Q
--R            Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 339
--S 340 of 350
an*bn
--R
--R
--R             4      2
--R            q      q      q
--R   (340)  %S   + %S   + %S  + 2%S
--R Type: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 340
--S 341 of 350
ac*bc
--R
--R
--R            137

--R   (341)  %R
--R Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 341

———-

3.26 discrete logarithms

— * —

--S 342 of 350
discreteLog(ap)
--R
--R
--R   (342)  4
--R                                                        Type: PositiveInteger
--E 342
--S 343 of 350
discreteLog(an)
--R
--R
--R   (343)  4
--R                                                        Type: PositiveInteger
--E 343
--S 344 of 350
discreteLog(ac)
--R
--R
--R   (344)  4
--R                                                        Type: PositiveInteger
--E 344

———-

3.27 Exponentiation

— * —

--S 345 of 350
ap**1234567
--R
--R
--R             4     2
--R   (345)  2%Q  + %Q  + %Q

--R            Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 345
--S 346 of 350
an**1234567
--R
--R
--R              4       2
--R             q       q       q
--R   (346)  2%S   + 2%S   + 2%S  + %S
--R Type: FiniteFieldNormalBasisExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 346
--S 347 of 350
ac**1234567
--R
--R
--R            16
--R   (347)  %R
--R Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 347

———-

3.28 computations between elements of field of different representation

— * —

--S 348 of 350
ap+bc
--R
--R
--R            187
--R   (348)  %R
--R Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 348
--S 349 of 350
an+bc
--R
--R
--R            187
--R   (349)  %R
--R Type: FiniteFieldCyclicGroupExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 349
--S 350 of 350

an+bp
--R
--R
--R            4     3
--R   (350)  %Q  + %Q  + 2%Q + 1
--R            Type: FiniteFieldExtensionByPolynomial(PrimeField(3),?^5+2*?^4+1)
--E 350
)spool
)lisp (bye)

———-

References^{[1] nothing}

81