$SPAD/src/input ffx72.input

Timothy Daly December 3, 2016

Abstract

Contents

2

1 License

— license —

--Copyright The Numerical Algorithms Group Limited 1991.

———-

— * —

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

———-

2 Finite Fields

This file demonstrates some calculations with the finite field of 49 elements. It is built as a degree 2 extension of the Galois field with 7 elements.

— * —

--S 1 of 13
gf72 := FF(7, 2)
--R
--R
--R   (1)  FiniteField(7,2)
--R                                                                 Type: Domain
--E 1

———-

x^{2} + 1 is irreducible over PF 7 — * —

--S 2 of 13
u: UP(x,PF 7) := x**2 + 1
--R
--R
--R         2
--R   (2)  x  + 1
--R                                  Type: UnivariatePolynomial(x,PrimeField(7))
--E 2
--S 3 of 13

factor u
--R
--R
--R         2
--R   (3)  x  + 1
--R                        Type: Factored(UnivariatePolynomial(x,PrimeField(7)))
--E 3

———-

But factors over FF(PF 7, 2)

— * —

--S 4 of 13
u2 : UP(x,gf72) := u
--R
--R
--R         2
--R   (4)  x  + 1
--R                               Type: UnivariatePolynomial(x,FiniteField(7,2))
--E 4
--S 5 of 13
factor u2
--R
--R
--R   (5)  (x + %A)(x + 6%A)
--R                     Type: Factored(UnivariatePolynomial(x,FiniteField(7,2)))
--E 5

———-

The following is the irreducible polynomial used in the representation of GF(7**2) over PF 7. It will be the same every time this field is used.

— * —

--S 6 of 13
definingPolynomial()$gf72
--R
--R
--R         2
--R   (6)  ?  + 1
--R                              Type: SparseUnivariatePolynomial(PrimeField(7))
--E 6

———-

e is a randomly chosen element — * —

--S 7 of 13

e := index(size()$gf72 quo 3)$gf72
--R
--R
--R   (7)  2%A + 2
--R                                                       Type: FiniteField(7,2)
--E 7
--S 8 of 13
norm e
--R
--R
--R   (8)  1
--R                                                          Type: PrimeField(7)
--E 8
--S 9 of 13
trace e
--R
--R
--R   (9)  4
--R                                                          Type: PrimeField(7)
--E 9

———-

The order of an element is the minimum positive integer to which it can be raised to yield 1.

— * —

--S 10 of 13
order e
--R
--R
--R   (10)  8
--R                                                        Type: PositiveInteger
--E 10

———-

We can display all the nonzero elements in the field — * —

--S 11 of 13
allElts := [index(i :: PI)$gf72 for i in 1..48]
--R
--R
--R   (11)
--R   [1, 2, 3, 4, 5, 6, %A, %A + 1, %A + 2, %A + 3, %A + 4, %A + 5, %A + 6, 2%A,
--R    2%A + 1, 2%A + 2, 2%A + 3, 2%A + 4, 2%A + 5, 2%A + 6, 3%A, 3%A + 1,
--R    3%A + 2, 3%A + 3, 3%A + 4, 3%A + 5, 3%A + 6, 4%A, 4%A + 1, 4%A + 2,
--R    4%A + 3, 4%A + 4, 4%A + 5, 4%A + 6, 5%A, 5%A + 1, 5%A + 2, 5%A + 3,

--R    5%A + 4, 5%A + 5, 5%A + 6, 6%A, 6%A + 1, 6%A + 2, 6%A + 3, 6%A + 4,
--R    6%A + 5, 6%A + 6]
--R                                                 Type: List(FiniteField(7,2))
--E 11

———-

We can sum over them — * —

--S 12 of 13
reduce(+,allElts)
--R
--R
--R   (12)  0
--R                                                       Type: FiniteField(7,2)
--E 12

———-

And we can determine the order of each of them. Each element of order 48 generates the multiplicative group of non-zero elements.

— * —

--S 13 of 13
[order e for e in allElts]
--R
--R
--R   (13)
--R   [1, 3, 6, 3, 6, 2, 4, 24, 48, 48, 48, 48, 24, 12, 48, 8, 16, 16, 8, 48, 12,
--R    48, 16, 24, 24, 16, 48, 12, 48, 16, 24, 24, 16, 48, 12, 48, 8, 16, 16, 8,
--R    48, 4, 24, 48, 48, 48, 48, 24]
--R                                                  Type: List(PositiveInteger)
--E 13
)spool
)lisp (bye)

———-

References^{[1] nothing}

7