From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Subject: Re: Non-linear systems in Z/Zn?
Date: 26 Dec 1999 23:16:46 GMT
Newsgroups: sci.math.symbolic
Keywords: solving polynomial systems mod n

In article <83uav0$i8a$1@nntp.itservices.ubc.ca>,
Robert Israel <israel@math.ubc.ca> wrote:
>In article <bcq26ss7ilcn9v04vfk9e8s68n7vncs8q9@4ax.com>,
>
>> : > Someone in es.ciencia.matematicas has asked for an algorithm to
>> : > solve non-linear systems in Z/Zn like this:
>> : >
>> : >    x1^3 + x1*x2 + x3 + 7 = 0 mod 10
>> : >      x1*x2*x3 - x2^4 + 3 = 0 mod 10
>> : >    x1*x2 + x2*x3 - x3*x1 = 0 mod 10
>
>> Someone said that this is NP-complete, but is there any known procedure
>> better than trying the 10^4 combinations one by one, say, for small n?
>
>Note that there is a solution mod 10 iff there are solutions mod 2 and mod 5.
>So with k variables, the number of combinations to check is at most 2^k + 5^k,
>not 10^k.
>
>Maple's Groebner package does allow computations over Ore algebras.  
>Finite fields are included.  When I tried it with your example, I didn't
>get a quick answer

Magma gets an answer almost immediately: with input
 R<x1,x2,x3>:=PolynomialRing(GF(5),3);
 I:=ideal<R| x1^3 + x1*x2 + x3 + 7,x1*x2*x3 - x2^4 + 3 ,x1*x2 + x2*x3 - x3*x1>;
 Groebner(I); print(I);
we get output
   x1 + 2*x3^16 + x3^14 + 3*x3^12 + 4*x3^9 + 2*x3^8 + 2*x3^7 + 3*x3^5 + 3*x3^4
       + 3*x3^3 + x3^2 + 3,
   x2 + 4*x3^16 + 4*x3^15 + x3^14 + 2*x3^13 + 3*x3^10 + 4*x3^8 + 4*x3^7 + 
       2*x3^6 + 3*x3^5 + 3*x3^4 + 4*x3^3 + 3*x3^2 + x3 + 1,
   x3^17 + x3^16 + 2*x3^14 + 4*x3^13 + 2*x3^12 + 2*x3^11 + 2*x3^10 + 4*x3^8 + 
       x3^6 + 4*x3^5 + 2*x3^4 + 4*x3^3 + 4*x3^2 + 4*x3 + 2
which shows that it is necessary and sufficient to solve a single polynomial
equation in one variable (x3). Well, that polynomial has no solutions in
GF(5), as is quickly found by exhaustive search or factorization (it's
equal to (x3^6+3*x3^5+2*x3^4+3*x3^2+4*x3+4)*
(x3^11+3*x3^10+4*x3^9+4*x3^8+x3^7+3*x3^6+3*x3^5+2*x3^4+3*x3^3+2*x3^2+3*x3+3)
mod 5). No solutions mod 5 means no solutions mod 10, of course.
(The situation mod 2 happens to be similar in this case except we end up
with an _irreducible_ polynomial of degree 17 in  x3 .)

When the modulus has only small prime factors I would imagine that, in general,
an exhaustive search is faster than using Groebner basis computations:
Strictly speaking, Groebner basis techniques are too fine a technique to
be "right" here -- taken as is, they compute a new basis for the ideal itself
whereas you want only a basis for the radical of this ideal; moreoever,
you don't seem to be interested in the information about extension fields
provided in this way. I'm guessing that you only intend to consider
varieties of dimension 0 (roughly: number of equations equals number of
variables) and Groebner basis computations don't make use of this
information I think. (I do note that  Magma  does include a few routines
which _do_ require the variety to be 0-dimensional.)

Also note that in addition to the Chinese-Remainder-Theorem argument used
in the previous post, one may use p-adic (Hensel) techniques to solve the
systems modulo p^r for r>1: find all solutions mod p, then for each one
change variables using the substitutions  x_i = (x_i)_0 + p y_i  and solve
mod  p^2, etc. This is covered in elementary number theory texts.