# InnerNormalBasisFieldFunctions GF¶

ffdoms.spad line 2000 [edit on github]

InnerNormalBasisFieldFunctions(`GF`

) (unexposed): This package has functions used by every normal basis finite field extension domain.

- basis: PositiveInteger -> Vector Vector GF
`basis(n)`

is undocumented. See basis

- dAndcExp: (Vector GF, NonNegativeInteger, SingleInteger) -> Vector GF
`dAndcExp(v, n, k)`

computes`v^e`

interpreting`v`

as an element of normal basis field. A divide and conquer algorithm similar to the one from`D`

.`R`

.Stinson, “Some observations on parallel Algorithms for fast exponentiation in`GF`

(2^n)”, Siam`J`

. Computation, Vol.19, No.4,`pp`

.711-717, August 1990 is used. Argument`k`

is a parameter of this algorithm.

- expPot: (Vector GF, SingleInteger, SingleInteger) -> Vector GF
`expPot(v, e, d)`

returns the sum from`i = 0`

to`e - 1`

of`v^(q^i*d)`

, interpreting`v`

as an element of a normal basis field and where`q`

is the size of the ground field. Note: for a description of the algorithm, see`T`

.Itoh and`S`

.Tsujii, “A fast algorithm for computing multiplicative inverses in`GF`

(2^m) using normal bases”, Information and Computation 78,`pp`

.171-177, 1988.

- index: (PositiveInteger, PositiveInteger) -> Vector GF
`index(n, m)`

is a index function for vectors of length`n`

over the ground field.

- lookup: Vector GF -> PositiveInteger
`lookup(x)`

is undocumented. See lookup

- minimalPolynomial: Vector GF -> SparseUnivariatePolynomial GF
`minimalPolynomial(x)`

is undocumented. See minimalPolynomial

- norm: (Vector GF, PositiveInteger) -> Vector GF
`norm(x, n)`

is undocumented. See norm

- normalElement: PositiveInteger -> Vector GF
`normalElement(n)`

is undocumented. See normalElement

- pol: Vector GF -> SparseUnivariatePolynomial GF
`pol(v)`

turns the vector`[v0, ..., vn]`

into the polynomial`v0+v1*x+ ... + vn*x^n`

.

- qPot: (Vector GF, Integer) -> Vector GF
`qPot(v, e)`

computes`v^(q^e)`

, interpreting`v`

as an element of normal basis field,`q`

the size of the ground field. This is done by a cyclic`e`

-shift of the vector`v`

.

- random: PositiveInteger -> Vector GF
`random(n)`

creates a vector over the ground field with random entries.

- repSq: (Vector GF, NonNegativeInteger) -> Vector GF
`repSq(v, e)`

computes`v^e`

by repeated squaring, interpreting`v`

as an element of a normal basis field.

- setFieldInfo: (Vector List Record(value: GF, index: SingleInteger), GF) -> Void
`setFieldInfo(m, p)`

initializes the field arithmetic, where`m`

is the multiplication table and`p`

is the respective normal element of the ground field`GF`

.

- trace: (Vector GF, PositiveInteger) -> Vector GF
`trace(x, n)`

is undocumented. See trace

- xn: NonNegativeInteger -> SparseUnivariatePolynomial GF
`xn(n)`

returns the polynomial`x^n-1`

.