Declare diagonal matrix with unknown variables in GF(2).

Katoptriss
13 ●2 ●6

I have an equation of the form $AXB = V$ , that I am trying to solve using Sage. All matrixes are in $GF(2)$ , $A$ and $X$ are of size 32x32, and $B$ and $V$ column vectors of size 32.

My unknown matrix $X$ consists in zeros, except on the diagonal where I'd like to have 32 unknowns (representing each bit of a unknown 32-bits integer). I first tried to declare an array of variables like this:

vars_list = list(var("x_%d" % i) for i in range(32)) which throws me a "TypeError: x_0 is not a variable of Univariate Polynomial Ring in X over Finite Field of size 2 (using GF2X)". Looking at Sage documentation, I didn't find a way to declare them in $GF(2)$ .

Using this link, I tried to declare my variables like this: x_1 = SR(GF(2)(1)) * var("x1") which gave me this time a "TypeError: positive characteristic not allowed in symbolic computations".

How should I setup $X$ so I can solve my equation?

add a comment

answered 3 years ago

Emmanuel Charpentier
7814 ●8 ●53 ●156

updated 3 years ago

A slight syntax error... Try :

sage: vars_list=[var("x_%d"%u) for u in range(32)]
sage: print(vars_list)
[x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9, x_10, x_11, x_12, x_13, x_14, x_15, x_16, x_17, x_18, x_19, x_20, x_21, x_22, x_23, x_24, x_25, x_26, x_27, x_28, x_29, x_30, x_31]

But SR (too) general methods for solving equations are highly inneficient in this case ; you should try to use Sage's methods for working on polynomials over GF(2). How ?

Simple :

sage: R1 = PolynomialRing(GF(2),32,"u") ; R1
Multivariate Polynomial Ring in u0, u1, u2, u3, u4, u5, u6, u7, u8, u9, u10, u11, u12, u13, u14, u15, u16, u17, u18, u19, u20, u21, u22, u23, u24, u25, u26, u27, u28, u29, u30, u31 over Finite Field of size 2
sage: X=diagonal_matrix(R1.gens()) ; print(X)
[ u0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0  u1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0  u2   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0  u3   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0  u4   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0  u5   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0  u6   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0  u7   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0  u8   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0  u9   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0 u10   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0 u11   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0 u12   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0 u13   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0 u14   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u15   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u16   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u17   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u18   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u19   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u20   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u21   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u22   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u23   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u24   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u25   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u26   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u27   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u28   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u29   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u30   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u31]

and work in R1 thereafter ; for example, Sys = R1(A)*X*R1(B)-R1(V) will give you a list of 32 polynomials describing your problem, and R1.ideal(Sys) will be a complete description of its solution...

I strongly recommend this book (freely available), whose chapter 9 (IIRC) will give you a nice overview of the possbilities of Sage, as well as the textbook this chapter points to.

HTH,

link

Comments

Thank you for the answer and the reference, I'll be sure to check it. A last question if I may: your answer worked fine, but it seems that if I declare a second matrix with a second set of 32 unknowns, operations like addition are impossible? I wanted to construct a small linear system with the unknowns being those 32x32 diagonal matrixes.

Katoptriss ( 3 years ago )

If I understand you correctly, you have 64 unknowns ; work in R1=PolynomialRing(GF(2), 64, "u"), setup your matrices as the upper-left and lower-right 32x32 matrices of uhe 64x64 iagonal matrix of your variables, and proceed accordingly...

Emmanuel Charpentier ( 3 years ago )

Indeed, it wasn't very complex... Thank you for your help.

Katoptriss ( 3 years ago )

Suggestion: make the example more readable using 4 instead of 32.

slelievre ( 3 years ago )

add a comment

Declare diagonal matrix with unknown variables in GF(2).

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Declare diagonal matrix with unknown variables in GF(2). savecancel

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Declare diagonal matrix with unknown variables in GF(2).