Dalvir's profile - activity

Is there a way to check that a multivariate system of polynomial equations does indeed have a solution(or not)? The context i am using this in is as follows: say i have a system of multivariate polynomial equations over a finite field, i then put values in for some of the variables, and then i need to check if the resulting system in the remaining unassigned variables has a solution or not? If not, then i will reassign different values to the other variables until a system with a solution is yielded. Of course because the assigning of these values is random there is a high chance the system has a solution anyway, but in the event that it does not is where i need a way to check whether a solution exists or not.

I have had a look at that but i don't really understand what is going on there because it doesn't seem to provide a solution, also i need to do it for a polynomial system. They define a polynomial system with the following

sr = mq.SR(1,1,1,4, gf2=True, polybori=True, order='lex')

F,s = sr.polynomial_system()and i don't really get what kind of polynomial system has actually been implemented there :/

I need to implement the XL algorithm in sage, which i can use to solve over-determined systems of polynomial equations (more equations than variables). Any help on how to do this?

How do i get the matrix representation of an affine transformation and it's inverse in sage?

I am more so interested in doing this for random affine transformations as i am using them in a multivariate cryptography scheme but for example the following affine transformation over GF(3)

      [1 0 0 2 0 2]     [1]
      [2 2 1 1 2 0]     [1]
      [2 0 0 2 2 2]     [0]
x |-> [2 2 0 1 1 1] x + [1]
      [1 0 2 0 2 0]     [0]
      [0 0 0 2 0 2]     [2]

After trying this it says that The dimension of the ideal is 2, but it should be 0 ...i require the dimension to be zero so finitely many solutions though, is there a way around this? When i check what the ideal of s is i get the following: Ideal (0, 0) of Multivariate Polynomial Ring in x4, x5 over Finite Field of size 31

I am trying to multiple a symbolic 1x1 matrix with one element in it, by a square matrix over a finite field. for example

[-9*x0^2 - 11*x0*x1 - 5*x1^2 - 11*x0*x2 - 4*x1*x2 + 7*x2^2 + 13*x1*x3 + 8*x2*x3 + 4*x3^2 - 6*x0*x4 - 4*x1*x4 - 15*x2*x4 + 9*x0*x5 - 8*x1*x5 - 5*x2*x5 - 3*x3*x5]

to be multiplied with them matrix

[18 23 14  1  6 21]
[24  3  3  0  2  0]
[17 25  2 16 23  8]
[ 8 21 16  5  1  9]
[14 28  8 17 12 12]
[ 6 24 18 19  3  1]

however when i try this i get the following error:

TypeError: unsupported operand parent(s) for *: 'Full MatrixSpace of 1 by 1 dense matrices over Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5 over Finite Field of size 31' and 'Full MatrixSpace of 6 by 6 dense matrices over Finite Field of size 31'

Is there a way to do this?

The error occurs after running [phi(f) for f in List]. And in answer to your question above about why in the definition of eqn i have [[f], [[g]], this is because the equations are actually formed from the following: eqn =[tp1*P[i]*tp1.transpose() for i in range(o)] where tp1=matrix(P.gens()) and tp1. transpose is just the transpose of that matrix and the central matrix P[i] is a square nxn matrix of values in GF(q) that i have determined. This multiplication when n=6looks like [x0, x1, x2, x3, x4, x5]*P[i]*[x0, x1, x2, x3, x4, x5].transpose and this yields a matrix with 1 element, and that element is the multivariate equation, and that is why the equations in the list eqn are of the form: 1x1 dense matrices over Multivariate Polynomial Ring in x0,...,x5 over GF(q)

I have a list of multivariate equations, there are o multivariate equations in the list where o is an integer and v = 2o, the variables that make up the equations are the generators of P = PolynomialRing(K,'x',n) where n = v + o so for example if o = 2 then v = 4 and n = 6 so the variables that make up the multivariate equations in the list would be P.gens() = (x0, x1, x2, x3, x4, x5). Now i need to substitute in random values from GF(q) for the first v variables in each of the multivariate equations in the list so in the example above where v = 4 random values from GF(q)would be substituted in for the variables x0, x1, x2, x3in each of the multivariate equations in the list, leaving equations in only two variables x4 and x5. I have tried to implement this but i don't really know where to start as i know i am doing something wrong but what i have is the following. If the list of multivariate equations is called eqn for example.

for i in range(v): 
xi = var('x'+str(i)) 
eqnsub0 = eqn[i].subs({x[i]:GF(q).random_element()})

I already know this is very wrong as the indexing will already go out of bounds since v > o but i don't really know where to start with this. Any help would be great, thanks.

Thanks for your help i have edited the question to be more specific with what i require as i realize my initial question was not as precise. If you can help with that that would be great.

I need to create a symbolic matrix in terms of the variables xi with one row of n elements for a given integer n, so for example if n=5 i would need to compute the matrix [x0, x1, x2, x3, x4]

As a follow on from this i then need to substitute in random values from a finite field say GF(q) for the first v number of variables in the matrix for a given integer v < n . So for example if v = 3 then i would need to substitute in random values from GF(q) for the first x0, x1, x2 variables of the matrix to get something like [GF(q).random_element(), GF(q).random_element(), GF(q).random_element(), x3, x4 ] of course i need to be able to do this for any integers n and v i choose. Any help about how to do this in sage would be great, thanks.

EDIT: I need to substitute in random values from a finite field say GF(q) for the first v number of variables for a given integer v < n into each of the multivariate equations in a list. So for example, if my list of multivariate equations is given by eqn where eqn looks like the following: [[10*x0^2 + 11*x0*x1 - 12*x1^2 - 14*x0*x2 + 8*x1*x2 + 6*x2^2 - 15*x0*x3 - 13*x1*x3 - 7*x2*x3 + 9*x3^2 - 13*x0*x4 + 11*x1*x4 + 6*x2*x4 - 15*x3*x4 + 11*x4^2 - 13*x0*x5 + 12*x1*x5 + 6*x2*x5 - 8*x4*x5 + x5^2], [4*x0^2 + 8*x0*x1 - 3*x1^2 - 8*x0*x2 - 3*x1*x2 - 10*x2^2 + 5*x0*x3 - 14*x1*x3 - 5*x2*x3 - 12*x3^2 - 10*x0*x4 + 8*x1*x4 - 10*x2*x4 - 4*x3*x4 + 6*x4^2 - 11*x0*x5 - 3*x1*x5 - 9*x2*x5 + 9*x3*x5 + 4*x4*x5 - 11*x5^2]] when o = 2 then i need to substitute random values from GF(q) into the first v variables, to obtain a list of multivariate equations in only the remaining variables that have not been substituted.