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

asked 2022-03-03 19:24:52 +0200

Katoptriss
13 ●2 ●6

updated 2022-03-03 20:59:01 +0200

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?

edit retag flag offensive close merge delete

add a comment

answered 2022-03-03 22:19:21 +0200

Emmanuel Charpentier
7057 ●6 ●46 ●137

updated 2022-03-03 22:41:34 +0200

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,

edit flag offensive delete 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 ( 2022-03-03 22:45:43 +0200 )edit

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 ( 2022-03-03 22:56:15 +0200 )edit

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

Katoptriss ( 2022-03-03 23:18:13 +0200 )edit

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

slelievre ( 2022-03-04 16:59:12 +0200 )edit

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). edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

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