1 | initial version |

To construct your matrix **A** you can do

```
sage: m = matrix(ZZ, 4, [2,3,1,1,1,2,3,1,1,1,2,3,3,1,1,2])
sage: x = polygen(GF(2))
sage: K = GF(2^8, 'a', modulus=x^8 + x^4 + x^3 + x + 1)
sage: A = matrix(K, 4, lambda i,j: K.fetch_int(m[i,j]))
sage: A
[ a a + 1 1 1]
[ 1 a a + 1 1]
[ 1 1 a a + 1]
[a + 1 1 1 a]
```

The method **fetch_int** used above is exactly what you are describing in your question, converting integers into vectors of bits. Now the question is how to compute the quantity $B(A) = min_a (weight(a) + weight(aA))$. The naive loop will never terminate ($2^{32}$ element in the vector space)

```
sage: V = VectorSpace(K, 4)
sage: min((A*v + v).hamming_weight() for v in V if v) # don't do this
```

Though, you can compute A*v + v for any vector in v

```
sage: for _ in range(10):
....: v = V.random_element()
....: print (A*v + v).hamming_weight()
4
4
4
4
4
4
4
4
4
4
```

You now have to come up with a better algorithm than looping through all elements of **V** to compute this minimum.

2 | No.2 Revision |

To construct your matrix **A** you can do

```
sage: m = matrix(ZZ, 4, [2,3,1,1,1,2,3,1,1,1,2,3,3,1,1,2])
sage: x = polygen(GF(2))
sage: K = GF(2^8, 'a', modulus=x^8 + x^4 + x^3 + x + 1)
sage: A = matrix(K, 4, lambda i,j: K.fetch_int(m[i,j]))
sage: A
[ a a + 1 1 1]
[ 1 a a + 1 1]
[ 1 1 a a + 1]
[a + 1 1 1 a]
```

The method **fetch_int** used above is exactly what you are describing in your question, converting integers into vectors of bits. Now the question is how to compute the quantity $B(A) = min_a (weight(a) + weight(aA))$. The naive loop will never terminate ($2^{32}$ element in the vector space)

```
sage: V = VectorSpace(K, 4)
sage:
```~~min((A*v ~~min((v*A + v).hamming_weight() for v in V if v) # don't do this

Though, you can compute A*v + v for any vector in v

```
sage: for _ in range(10):
....: v = V.random_element()
....: print
```~~(A*v ~~(v*A + v).hamming_weight()
4
4
4
4
4
4
4
4
4
4

You now have to come up with a better algorithm than looping through all elements of **V** to compute this minimum.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.