Timings over cyclic codes creation

This issue presents the method used to create a cyclic code from the defining set, and some timings on the different steps.

Some notations (which miss LaTeX. A lot):

Let Fp be a finite prime field, Fp^m be an extension field of Fp and Fp^m^s an extension field of Fp^m.

I want to build a cyclic code of some given length n,over Fp^m, from the defining set D of the code. I need to do the following:

compute s, the smaller integer such that n divides (p^m)^s - 1
go to the extension field Fp^m^s
pick a primitive element beta over Fp^m^s
"split" the elements of D into cyclotomic cosets
compute gs, polynomial over Fp^m^s s.t. gs = product(x - beta ^ i), where i runs through all the representative elements of the cyclotomic cosets.
"convert" each coefficient of gs back to Fp^m, to form a new polynomial called g
g is the generator polynomial of the code

Problem: in Sage, there is no way to create a "real" extension field over an extension field. Namely, if I say Fp^m^s is an extension field of Fp^m of degree s, Sage will do Fp^m^s is an extension field of Fp with degree m^s. It is thus impossible to easily perform step 6).

Solution: let q = p^m. We compute a new element alpha which is a primitive element over Fq. Then, we compute all powers of alpha from 0 to q - 1 and store these values in a dictionary, where the values are the powers (from 0 to q-1) and the keys are the associated alpha (alpha ^ power). Then, we compute gs and compare the value of gs to the computed alphas to find the matchingalpha, and do the conversion from Fq^s to Fq this way.

I timed the following steps:

computation of s
creation of Fq^s (called Fsplit)
computation of the dictionary of the powers of alpha
computation of the cyclotomic cosets
computation of gs -computation of g from gs

I got the following:

For a code of length 201 over F2^8, D = {0...199}, s =33

Computation of s: 0.024407
Computation of the Fsplit: 0.227664
Computation of the dictionary: 0.025201
Computation of the cosets: 0.019901
Computation of gs: 5.821944
Computation of g: 0.018168

Some extra timings is of course needed (changing the length of D, the value of n, the value of s) but it gives a good idea of which step takes time...

Comments (9)