Solving systems of multivariate polynomials modulo 2^32

[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 procedure in C in order to get
more speed in the computation.

I was trying to figure out what algorithms are used in
the "Reduce" function of Mathematica (reading Wolfram
web pages) but I couldn't find any specific
information for the algorithms they are using for
solving multivariate polynomials modulo 2^32.

I found several papers that are dealing with solving
univariate or multivariate polynomials in finite
fields such as:

1. Lauder :
http://www.maths.ox.ac.uk/~lauder/papers/LauderManyVarSept16.pdf
2. van de Woestijne :
http://www.math.leidenuniv.nl/~cvdwoest/maths/ober.pdf
and 
http://www.math.leidenuniv.nl/~cvdwoest/maths/issac2005.pdf
3.  Barreto and Voloch:
http://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf
4. Ding, Gower and Schmidt:
http://eprint.iacr.org/2006/038.pdf

but the algorithms there are for soving polynomials
over finite fields GF(p) or GF(p^n) which is different
than just solving polynomials (univariate or
multivariate) modulo 2^32.

I will appreciate any hint or coment.

Regards,
Danilo Gligoroski

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