Solving systems of multivariate polynomials modulo 2^32

Danilo Gligoroski gligoroski at
Mon Aug 14 06:36:10 EDT 2006

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 :
2. van de Woestijne :
3.  Barreto and Voloch:
4. Ding, Gower and Schmidt:

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.

Danilo Gligoroski

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list