Ask Your Question
2

Binary fields

asked 2014-06-05 16:05:40 -0500

Blackadder gravatar image

updated 2014-06-05 23:18:12 -0500

Hello, I would like to perform the following on a binary field, i.e. GF(2^m).

  1. Define a polynomial and solve the polynomial over a binary field.
  2. Convert an element of the binary field into a bit string.

For the first, I've tried the following:

K = GF(2^7,'a');
PK.<x>=K[]; #I've also tried "x = PolynomialRing(GF(2^7,'a'),'x').gen"
f = (a^6 + a^3 + a)*x^2 + (a^6 + a^4 + a^3)*x + (a^5 + a^4 + a^3 + a^2 + 1);
print f.roots();

But the error is TypeError: unable to coerce from a finite field other than the prime subfield.

For the second, I would like to know how finite field elements are stored in SAGE, are they stored as vectors?

If you have any resources that could point me in the right direction, I'll be very thankful for your help!

edit retag flag offensive close merge delete

Comments

What version of Sage are you using exactly, and were there any other commands before this? The `a` seems to be missing.

kcrisman gravatar imagekcrisman ( 2014-06-05 16:41:49 -0500 )edit

@kcrisman The version that I'm using is 5.11. The `a` comes from the first line; it is used to generate the finite field of prime power. See http://www.math.ucla.edu/~jimc/mathnet_d/sage/reference/sage/rings/finite_rings/constructor.html

Blackadder gravatar imageBlackadder ( 2014-06-05 17:03:26 -0500 )edit

3 answers

Sort by ยป oldest newest most voted
3

answered 2014-06-05 22:52:25 -0500

tmonteil gravatar image

updated 2014-06-05 23:18:14 -0500

There is a problem since the variable a you are using in your third line seems to come from a previous computation.

At least on the last version of Sage, if you type

sage: K = GF(2^7,'a');

The python variable a does not point to the generator of K whose name is 'a'

sage: a
NameError: name 'a' is not defined

For this, you have to do:

sage: K.inject_variables()
Defining a

Then, everything seems to work:

sage: PK.<x>=K[];
sage: f = (a^6 + a^3 + a)*x^2 + (a^6 + a^4 + a^3)*x + (a^5 + a^4 + a^3 + a^2 + 1);
sage: print f.roots();
[(a^3 + a, 1), (a^5 + a^3 + a^2 + a, 1)]
edit flag offensive delete link more

Comments

That worked! I don't recall seeing that anyway on the reference manual though. But a HUGE thank you! If you could help with the second, I'll be much obliged.

Blackadder gravatar imageBlackadder ( 2014-06-05 23:19:32 -0500 )edit

That missing `a` is exactly what I was asking about! I could never even make it past defining `f`, which would give the error Thierry points out here.

kcrisman gravatar imagekcrisman ( 2014-06-06 14:50:14 -0500 )edit
2

answered 2014-06-06 03:56:19 -0500

niles gravatar image

I assume the binary string you want is the list of coefficients of a. For this, you could do the following:

  • Make an element:

    sage: K = GF(2^7,'a');
    sage: x = K.random_element(); x
    a^5 + a^4 + a^3 + a
    
  • Convert the element to a polynomial and get the list of coefficients:

    sage: x.polynomial().coeffs()
    [0, 1, 0, 1, 1, 1]
    
  • Go directly from the element to a string by joining the strings of the coefficients:

    sage: ''.join(map(str,x.polynomial().coeffs()))
    '010111'
    
edit flag offensive delete link more

Comments

This is exactly what I have in mind. Thank you so much. The reverse procedure (if anyone is interested) can be done via `K._cache.fetch_int(0x426)`

Blackadder gravatar imageBlackadder ( 2014-06-08 14:22:53 -0500 )edit

P.S. Sorry I can't accept both answers.

Blackadder gravatar imageBlackadder ( 2014-06-08 16:33:14 -0500 )edit
1

answered 2014-06-29 05:58:14 -0500

Hi,

Finite field elements are almost stored as vectors. It is actually a bit more complicated since there are several implementation and most of the time it uses external libraries (givaro, pari or ntl). You can nevertheless convert your element into a vector with

sage: K = GF(16, 'a')
sage: V = K.vector_space()
sage: K.inject_variables()
sage: V(a^2 + 3*a + 1)
sage: v =V(a^2 + a + 1)
sage: v
(1, 1, 1, 0)
sage: v.parent()
Vector space of dimension 4 over Finite Field of size 2

Vincent

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2014-06-05 16:05:40 -0500

Seen: 656 times

Last updated: Jun 29 '14