- edited description
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 thatn
divides(p^m)^s - 1
- go to the extension field
Fp^m^s
- pick a primitive element
beta
overFp^m^s
- "split" the elements of
D
into cyclotomic cosets - compute gs, polynomial over
Fp^m^s
s.t.gs = product(x - beta ^ i)
, wherei
runs through all the representative elements of the cyclotomic cosets. - "convert" each coefficient of
gs
back toFp^m
, to form a new polynomial calledg
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
(calledFsplit
) - computation of the dictionary of the powers of
alpha
- computation of the cyclotomic cosets
- computation of
gs
-computation ofg
fromgs
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)
-
reporter -
Can you make the text in the timings and the informal description more close to each other ? For instance use the term dictionary in the description.
Can you give the size of the defining set ?
-
reporter - edited description
-
reporter Size of the defining set is given, it's 200.
-
It's the multiplication (of individual field elements) over the big field's polynomial ring that's, for reasons I don't understand, very slow over extension fields.
The following code to implement the multiplication (untested) gave me a massive speed-up on everything but prime fields:
ls = [ F.one() ] for p in pows: c = -a**p sls = [ F.zero() ] + ls cls = [ c*e for e in ls ] + [F.zero()] ls = [ sls[i] + cls[i] for i in range(len(sls)) ]
-
reporter Nice, thanks! I'm currently investigating on how Sage manages the different libraries for polynomials, maybe it will unveil some things...
-
<dramatic music in background, leading up to grand finale>....
-
reporter <Ended up in a chaos, screaming "What in the world is happening in here??">...
-
reporter - changed status to resolved
- Log in to comment