Solving systems of multivariate polynomials modulo 2^32

[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.  Then, for
each mod-2 solution, you try to extend it to a solution modulo 4.  Then,
for each mod-4 solution, you extend it to a solution modulo 8.  And so on.
This is sometimes known under the name "Hensel lifting".

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).

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).

Step 3. Find all solutions modulo 8.  First, take the mod-4 solution
x=0, y=3, z=1 (mod 4) and try extending it all 2^3 possible ways, to
see which of them lead to mod-8 solutions.  Then, take the other mod-4
solution x=2, y=1, z=1 (mod 4) and try extending it all 2^3 possible
ways, too.  The result is the set of mod-8 solutions.

Step 4. Find all solutions modulo 16.  etc.

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.

Note that this only works for Z_{2^32}.  It doesn't work for GF(2^32).

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