Symbolic inverse in finite field

[Subrata Nandi]

My research area is symmetric key cryptology. I need an efficient algorithm for solving inverse of symbolic matrix of size 512 x 512 in GF(2). Can anyone share
Idea regarding that?

[Emmanuel Charpentier]

Spoke too fast. Sorry for the noise...

[Emmanuel Charpentier]

One can check that Sage's built-in methods can invert such a GF(2) maytrix in reasonable time:

sage: MS=MatrixSpace(GF(2),512,512)

sage: while True:

....:     M=MS.an_element()

....:     if M.is_unit(): break

....:     

sage: %time IM=M^-1

CPU times: user 2.99 ms, sys: 243 µs, total: 3.23 ms

Wall time: 113 ms

sage: bool(IM*M==diagonal_matrix(GF(2),[GF(2)(1)]*512))

True

But, being totally ignorant of your domain, I have trouble seeing how to use this result for boolean logic. A glimpse at the relevant documentation hints that I should refrain from commenting further...

HTH, nevertheless,

Le jeudi 31 octobre 2019 10:51:27 UTC+1, Subrata Nandi a écrit :

[Subrata Nandi]

Thanks Emmanuel Charpentier for your reply. But the entry of my matrix is only symbolic variables. For example I am giving one short matrix.

y=[

    [x0           x1           x2           x3           x4           x5           x6           x7           x8           x9]
    [x1           x2           x3           x4           x5           x6           x7           x8           x9      x0 + x3]
    [x2           x3           x4           x5           x6           x7           x8           x9      x0 + x3      x1 + x4]          
[x3           x4           x5           x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5]
[          x4           x5           x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6]
[          x5           x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7]
[          x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8]
[          x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8      x6 + x9]
[          x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8      x6 + x9 x0 + x3 + x7]
[          x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8      x6 + x9 x0 + x3 + x7 x1 + x4 + x8]

]

[Subrata Nandi]

On Thursday, November 7, 2019 at 9:13:17 PM UTC+5:30, Subrata Nandi wrote:

Thanks Emmanuel Charpentier for your reply. But the entry of my matrix is only symbolic variables. For example I am giving one short matrix.

       R.<x0, x1, x2, x3, x4, x5, x6, x7, x8, x9>=Boolean PolynomialRing() 

y=[

    [x0           x1           x2           x3           x4           x5           x6           x7           x8           x9]
    [x1           x2           x3           x4           x5           x6           x7           x8           x9      x0 + x3]
    [x2           x3           x4           x5           x6           x7           x8           x9      x0 + x3      x1 + x4]          
    [x3           x4           x5           x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5]
    [x4           x5           x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6]
    [x5           x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7]
    [x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8]
    [x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8      x6 + x9]
    [x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8      x6 + x9 x0 + x3 + x7]
    [x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8      x6 + x9 x0 + x3 + x7 x1 + x4 + x8]

]

This is a 10 x 10 matrix where each xi in GF(2). I need to find (0,0,0,0,0,0,0,0,0,1)*y^(-1). This is a small example of what I need. In actual case, n=512. Can you help me to find the inverse. Thanks in advance man.

[Nils Bruin]

On Thursday, November 7, 2019 at 7:50:00 AM UTC-8, Subrata Nandi wrote:

On Thursday, November 7, 2019 at 9:13:17 PM UTC+5:30, Subrata Nandi wrote:

Thanks Emmanuel Charpentier for your reply. But the entry of my matrix is only symbolic variables. For example I am giving one short matrix.

       R.<x0, x1, x2, x3, x4, x5, x6, x7, x8, x9>=Boolean PolynomialRing() 

y=[

    [x0           x1           x2           x3           x4           x5           x6           x7           x8           x9]
    [x1           x2           x3           x4           x5           x6           x7           x8           x9      x0 + x3]
    [x2           x3           x4           x5           x6           x7           x8           x9      x0 + x3      x1 + x4]          
    [x3           x4           x5           x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5]
    [x4           x5           x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6]
    [x5           x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7]
    [x6           x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8]
    [x7           x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8      x6 + x9]
    [x8           x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8      x6 + x9 x0 + x3 + x7]
    [x9      x0 + x3      x1 + x4      x2 + x5      x3 + x6      x4 + x7      x5 + x8      x6 + x9 x0 + x3 + x7 x1 + x4 + x8]

]

This is a 10 x 10 matrix where each xi in GF(2). I need to find (0,0,0,0,0,0,0,0,0,1)*y^(-1). This is a small example of what I need. In actual case, n=512. Can you help me to find the inverse. Thanks in advance man.

Note that in boolean polynomial rings, all elements except 0,1 are zero-divisors, so I think matrices with a determinant different from 1 are not going to be invertible.

Another problem: a 512x512 matrix might still be workable, but if you also have 512 variables, then entries could easily be sums of something like 2^512 terms; so that's probably not going to fit in memory.