Binary fields

asked 2014-06-05 23:05:40 +0100

Blackadder
121 ●5 ●9 ●18

updated 2014-06-06 06:18:12 +0100

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

Define a polynomial and solve the polynomial over a binary field.
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 ( 2014-06-05 23:41:49 +0100 )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 ( 2014-06-06 00:03:26 +0100 )edit

add a comment

3

answered 2014-06-06 05:52:25 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

updated 2014-06-06 06:18:14 +0100

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

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 ( 2014-06-06 06:19:32 +0100 )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 ( 2014-06-06 21:50:14 +0100 )edit

add a comment

2

answered 2014-06-06 10:56:19 +0100

niles
4529 ●23 ●72 ●133 http://nilesjohnson.net/

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

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 ( 2014-06-08 21:22:53 +0100 )edit

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

Blackadder ( 2014-06-08 23:33:14 +0100 )edit

add a comment

1

answered 2014-06-29 12:58:14 +0100

vdelecroix
7645 ●20 ●85 ●168 http://www.labri.fr/pe...

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

add a comment

Binary fields

Comments

3 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Binary fields edit

Comments

3 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Binary fields