Re: bug in BCHCode

[David Joyner]

Thanks for the bug report!

On Tue, Mar 22, 2016 at 7:51 PM, Barry M Trager <b...@us.ibm.com> wrote:
> Hi David,
> I am trying to use the BCHCode function in Sage version 7.0.
> Since you included your email address in the code, I hope its ok to sent
> this bug note to you.
> It seems that it doesn't work properly when the finite field argument is not
> a prime field, for example:
> codes.BCHCode(65,56,GF(8,"c"),38)
> returns:
> Linear code of length 65, dimension 0 over Finite Field in c of size 2^3
> But the code actually has dimension 4.
> The problem is the way you compute the polynomial g as a product of calls to
> minpoly()
> In this case, they are giving the minpoly of elements over GF(2) instead of
> the minpoly over GF(8).
>
> One way to fix it is to directly compute the polynomial over the bigger
> field, and then map it back.
>
> from sage.rings.finite_rings.hom_finite_field import
> FiniteFieldHomomorphism_generic
> q = F.order()
> R = IntegerModRing(n)
> m = R(q).multiplicative_order()
> FF = GF(q**m,"z")
> z = FF.gen()
> e = z.multiplicative_order()/n
> a = z**e # order n
> #P = PolynomialRing(F,"x")
> #x = P.gen()
> # new code
> f = FiniteFieldHomomorphism_generic(Hom(F, FF));
> PP = PolynomialRing(FF,"x")
> x = PP.gen()
> cosetlist = reduce(operator.add, R.cyclotomic_cosets(q,
> range(b,b+delta-1)))
> g = reduce(operator.mul, [x + a^j for j in
> cosetlist]).map_coefficients(f.section(), F)
>
> I am rather new to Sage, so perhaps this isn't the best way to do this,
> another way is to represent
> FF as an explicit extension of F by factoring the minpoly of a (or z),
> however since you
> have all the cyclotomic cosets, it seems simplest to just construct the
> polynomial which has
> those powers of "a" as roots, and then map this back to a poly over F. I
> don't know if you want
> to special case the situation when F is a prime field for efficiency. If you
> do, I should point out that
> even in the primefield case, the old code was calling minpoly for each
> element of the cosets and then
> calling lcm, but if you just call minpoly on the first element of each
> coset, the resulting polynomials
> are relatively prime to each other so you can just multiply them instead of
> calling lcm.
> (i.e. minpoly on each element of a coset returns the same polynomial, in the
> case of a primefield)
>
>
> Barry Trager
>
>
>

[david...@inria.fr]

Hello,

I'm working on a project which aims to vastly enhance the coding theory library of Sage.
I developed a new implementation of Cyclic codes and BCH codes, as separate classes that generate a Cyclic/BCH codes which is considered as is by Sage, and no longer as a generic Linear code.
For now, I only put my Cyclic codes implementation in a ticket, see ticket #20100).

In Sage, there is no mechanism to map the elements of a non-prime finite field into one of its subfields - except if the subfield is the prime field.
For instance, this:

F = GF(2^8, 'a')
a = F.gen()
Fsub = GF(2^4, 'aa')
Fsub(a)

fails.

It is quite an issue when you're dealing with cyclic and BCH codes, as you might need to coerce the coefficients of the polynomials from the big field to the small field - which is not necessary the prime field.

I developed a class to take care of this embedding in ticket #20039 (which is related to subfield subcodes).
To get my Cyclic codes in Sage, I need peer-reviewing for both #20039 and #20100 - which might take some time!

So, if you want, I can open a new ticket for BCH codes, and put my implementation in it (which takes care of the bug you reported). It probably won't enter Sage any time soon, but you will be able to get the Git branch associated to this new ticket and merge it with your local version of Sage to get a fixed and upgraded version of BCH codes.

Best,

David Lucas

[Vincent Delecroix]

On 23/03/16 11:23, david...@inria.fr wrote:
> In Sage, there is no mechanism to map the elements of a non-prime finite
> field into one of its subfields - except if the subfield is the prime field.
> For instance, this:
> F = GF(2^8, 'a')
> a = F.gen()
> Fsub = GF(2^4, 'aa')
> Fsub(a)
>
> fails.

In your example, the generator of GF(2^8) is not part of any subfield.
Though you can do the reverse (map the generator of GF(2^4) into
GF(2^8)) using algebraic closures of finite fields:

sage: K = GF(2).algebraic_closure()
sage: K4, phi4 = K.subfield(4)
sage: z4 = K4.gen()
sage: psi = K.inclusion(4,8)
sage: psi
Ring morphism:
From: Finite Field in z4 of size 2^4
To: Finite Field in z8 of size 2^8
Defn: z4 |--> z8^7 + z8^4 + z8^3
sage: psi(z4)
z8^7 + z8^4 + z8^3

You can also go from GF(2^8) to GF(2^4) as follows

sage: K8, phi8 = K.subfield(8)
sage: z8 = K8.gen()
sage: psi.section()(z8^7 + z8^4 + z8^3)
z4

Vincent