From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.num-analysis
Subject: Re: Syst. of eq. based on arith. modular
Date: 26 Jul 1998 03:50:10 GMT

In article <6pcrv0$cji$3@aven.infini.fr>,
Thierry Abaléa <news.thierry.abalea@iname.com> wrote:
>    I am interested in the resolution of systems of equations of the type :
...
>|    (EQ1)    A = [  (R1 +   R3)  *  (R2 +   R4)   +   R1  ]    mod m
>|    (EQ2)    B = [  (R1 + 2*R3)  *  (R2 + 2*R4)   +   R2  ]    mod m
>|    (EQ3)    C = [  (R1 + 3*R3)  *  (R2 + 3*R4)   +   R3  ]    mod m
>|    (EQ4)    D = [  (R1 + 4*R3)  *  (R2 + 4*R4)   +   R4  ]    mod m
>|
>|    R1, R2, R3, R4 are always the unknown factors and belong to the
>|    set ZZm.
>|    A, B, C, D known are also in the set ZZm (what is obligatory if
>|    one wants solutions).
>|    m is some positive integer (I am interested more particularly in
>|    m = 2^8 = 256, in this case, we are in a "finished field" : Z/2^8,
>|    N.B :    in french : "corps fini").

That's  "finite field", actually, but I assume you do _not_ mean to
take the finite field of  m  elements, but rather the finite (cyclic) ring
Z/m. (The particular set of equations is really quite easy over the
_fields_ with  2^s  elements!)

To solve equations mod  m=2^s, work by induction on  s: solve them
first mod 2 to get each  R_i = r_i, say. Then set R_i = r_i + 2*R'_i, 
expand, and reduce mod 4; you'll get four equations of the form
2*(something) = 0 mod 4, which amount to four _linear_ equations mod 2
in the four variables  R'_i. Solve to get the solutions  r_i  for the
R_i  mod 4. Then repeat this process to get solutions  r_i  which are
correct mod 8, and so on. At every stage after the first one, the equations
are linear and mod 2, so quite easy to solve.

At each stage you may find multiple solutions, so your solution process
may branch; at each stage it is also possible that the equations are
inconsistent, so you may prune the branches.

dave