Re: Solving systems of multivariate polynomials modulo 2^32

2006-08-27 Thread Alexander Klimov
On Mon, 14 Aug 2006, David Wagner wrote: > Here's an example. Suppose we have the equations: > x*y + z = 1 > x^3 + y^2 * z = 1 > x + y + z = 0 > > Step 1: Find all solutions modulo 2. This is easy: you just have to try > 2^3 = 8 possible assignments and see which one satisfy

Re: Solving systems of multivariate polynomials modulo 2^32

2006-08-21 Thread Danilo Gligoroski
Ariel wrote: >A root that you lift using Hensel to Z_{p^n} looks >like a_0 + a_1 p + a_2 p2 +... +a_n p^n where a_i is >in Z_p. What will happen in your case >is that at first, in (Z_2)3 you can have at most 8 >roots, once you lift to Z_{22} some of these roots can >be "split" into more roots

Re: Solving systems of multivariate polynomials modulo 2^32

2006-08-20 Thread Ariel Waissbein
Hi Danilo, the information you can extract from the system relies largely in the hypoteses. If you don't bound the degree then the polynomials can define the zero function, while they are not the zero polynomial. Say, the univariate 2^{31}X(X+1) defines the zero function in Z_{232}. Also notice th

Re: Solving systems of multivariate polynomials modulo 2^32

2006-08-16 Thread Danilo Gligoroski
Danilo Gligoroski writes: >[...] solve a system of 3 polynomials of order 3 >with 3 variables x1, x2 and x3 in the set Z_{2^32} and >coeficients also in Z_{2^32} [...] David Wagner wrote: >Here is a trick that should solve these kinds of >equations extremely quickly. First, you solve the >system

Solving systems of multivariate polynomials modulo 2^32

2006-08-14 Thread David Wagner
Danilo Gligoroski writes: >[...] solve a system of 3 polynomials of order 3 >with 3 variables x1, x2 and x3 in the set Z_{2^32} and >coeficients also in Z_{2^32} [...] Here is a trick that should solve these kinds of equations extremely quickly. First, you solve the system of equations modulo 2.

Re: Solving systems of multivariate polynomials modulo 2^32

2006-08-14 Thread Ariel Waissbein
Hi Danilo, Maybe you should use some other function in Mathematica. Symbolic solving polynomial equations is a very difficult task (e.g., doubly-exponential worst case time complexity). But in this case it shouldn't take that much time. Let me notice that Z_{2^32} is not the same as F_{2^32} the

Solving systems of multivariate polynomials modulo 2^32

2006-08-14 Thread Danilo Gligoroski
Hi, In order to solve a system of 3 polynomials of order 3 with 3 variables x1, x2 and x3 in the set Z_{2^32} and coeficients also in Z_{2^32} I used the Mathematica 5.1 function Reduce[...,{x1,x2,x3},Modulus->2^32]. It is giving the solutions but it is not very fast. I wanted to programe a procedu