Solving systems of multivariate polynomials modulo 2^32

[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 the equations.  In
> this case, the only solution is x=0, y=1, z=1 (mod 2).

There is a small optimization: modulo 2, x^n = x and thus if ``the
degrees of the polynomials are high (say 32) and the number of terms
they have is also big (for example 833, 2825 and 4708)'' it is not
more difficult to solve than degree 3 (xyz) with up to 8 terms. In
particular, the example is equivalent modulo 2 to

 x*y + z = 1
 x + y*z = 1
 x + y + z = 0

[[[ Btw, something is wrong in the example: the following program

 N = 2
 for x in range(N):
  for y in range(N):
   for z in range(N):
    if (x*y+z)%N==1 and (x**3+y**2*z)%N==1 and (x+y+z)%N==0:
     print x,y,z

outputs

 0 1 1
 1 0 1
 1 1 0

and apparently 1,0,1 is indeed a solution mod 2:

 1*0+1=1, 1+0*1=1, and 1+1+0=0
]]]

Trying all combinations is a reasonable strategy, but it is also
possible to use an iterative simplification (especially if there are,
say, 80 variables):

if y = 0 we get a linear system

 z = 1
 x = 1
 x + z = 0

that is 1,0,1 is a solution

if y = 1 we get also a linear system

 x + z = 1
 x + z = 1
 x + 1 + z = 0

that is 0,1,1 and 1,1,0 are also solutions.

Linearization (and relinearization) may also be an option.

> Step 2: Find all solutions modulo 4.  This is again easy: since we know
> x=0 (mod 2), then the only two possibilities for x mod 4 are 0 or 2.
> Likewise, there are only two possibilities for y mod 4 and z mod 4.
> Trying all 2^3 = 8 possible assignments, we find that the only two
> solutions are x=0, y=3, z=1 (mod 4) and x=2, y=1, z=1 (mod 4).

Once we solved the system modulo 2^k, doing so modulo 2^{k+1} is much
simpler than trying all possibilities for the next bit. A nice
property of multiplication is that it gives linear relation in the
non-zero bit-slice, that is if we know that

 X = x 2^k + A
 Y = y 2^k + B,

where A and B are known and k>0, then modulo 2^{k+1} we have

 X*Y = xy 2^{2k} + (Bx+Ay) 2^k + AB = (bx+ay) 2^k + AB,

where a and b are the least significant bits of A and B (A = 2A'+a).
Since A and B are known constants, the next bit of XY is a linear
function (bx + ay + AB/2^k) of the next unknown bits of X and Y.

For example, in our case once we have (0,1,1) we represent X=2x,
Y=2y+1, and Z=2z+1 and write

 2x(2y + 1) + 1 = 1
 (2x)^3 + (2y+1)^2(2z+1) = 1
 2x+(2y+1)+(2z+1) = 0

remove everything divisible by 4

 2x + 1 = 1
 2z + 1 = 1
 2x + 2y + 2z + 2 = 0

and divide each equation by 2 (this is possible becuase (0,1,1) was a
solution modulo 2)

 x = 0
 z = 0
 x+y+z=1,

that is (x,y,z)=(0,1,0) and thus (X,Y,Z) = (0,3,1) modulo 4.

> We see that this requires performing 32 of these steps.  On average, we
> expect about one feasible solution to remain possible after each step
> (though this number may vary).  Each step requires testing 8 possible
> assignments, times the number of assignments from the prior step.  Thus,
> on the average case we can expect this to run very fast.

Btw, the matrix (and thus its rank) depends only on the LSB of the
current solution, thus for each solution modulo 2, there is either a
split on each new step (if the rank is not maximal and the system is
consistent on this step), or no splits at all (if it is maximal).

-- 
Regards,
ASK


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com