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. > >> On Monday, November 4, 2019 at 12:20:50 AM UTC+5:30, Emmanuel Charpentier >> wrote: >>> >>> 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 >>> <http://doc.sagemath.org/html/en/reference/logic/index.html> hints that >>> I should refrain from commenting further... >>> >>> HTH, nevertheless, >>> >>> >>> Le jeudi 31 octobre 2019 10:51:27 UTC+1, Subrata Nandi a écrit : >>>> >>>> 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? >>> >>> -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/4fc70729-f5b6-422b-a46e-e7d6b90747e8%40googlegroups.com.
