Revision history [back]
 | 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.
