d125q's profile - activity

Thank you!

Consider the following code:

sage: F = GF(17)
sage: R.<x, y> = PolynomialRing(F)
sage: MS = MatrixSpace(F, 5, 4)
sage: x, y = R.gens()
sage: MS.random_element() * x  # Good.
sage: MS.random_element() * y  # Good.
# So far, so good.  Now watch.
sage: R.<x, y> = PolynomialRing(F, order='lex')
sage: x, y = R.gens()
sage: MS.random_element() * x
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-12-928a7b216caf> in <module>()
----> 1 MS.random_element() * x

sage/structure/element.pyx in sage.structure.element.Matrix.__mul__ (/build/sagemath/src/sage-6.9/src/build/cythonized/sage/structure/element.c:23250)()

sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel_cache_maps.bin_op (/build/sagemath/src/sage-6.9/src/build/cythonized/sage/structure/coerce.c:9739)()

TypeError: unsupported operand parent(s) for '*': 'Full MatrixSpace of 5 by 4 dense matrices over Finite Field of size 17' and 'Multivariate Polynomial Ring in x, y over Finite Field of size 17'

Does anybody know if this is intentional? In my opinion it shouldn't happen because lex ordering is already the implicit default. The bug does not seem to occur with degrevlex ordering, which is also weird. The bug also does not occur with square matrices, which is even weirder.

SageMath Version 6.9, Release Date: 2015-10-10

Okay, I found the solution. Finite vector spaces support iteration, so one can simply do:

particular_soln = A.solve_right(b)
for homogeneous_soln in A.right_kernel():
    particular_soln + homogeneous_soln

Assume I have a matrix $A$ and a vector $b$, both over some finite field $\mathrm{GF}(q)$. I would like to enumerate _all_ solutions to $A x = b$ (there are only finitely many).

I can generate a particular solution using A \ b and I can generate the nullspace of $A$ using A.right_kernel(), but how should I combine the two to enumerate all solutions?

I would like to use SageMath to solve a system of multivariate quadratic (MQ) equations. The goal is to provide an implementation of the Kipnis--Shamir attack on the MinRank problem (see here, pp. 29--31).

Basically, I have matrices $M_j$ over some finite field and I need for form and solve a system of equations that looks like this: $$ \left(\sum\limits_{j = 1}^{k} y_j M_j\right) \begin{bmatrix} 1 & 0 & \cdots & 0 \ 0 & 1 & \cdots & 0 \ \vdots & \vdots & \vdots & \vdots \ 0 & 0 & \cdots & 1 \ x_1^{(1)} & x_1^{(2)} & \cdots & x_1^{(n - r)} \ \vdots & \vdots & \vdots & \vdots \ x_r^{(1)} & x_r^{(2)} & \cdots & x_r^{(n - r)} \end{bmatrix} = \mathbf{0} $$ Where the $y$'s and the $x$'s are unknowns.

How should I go about achieving this? Thanks in advance.