Solving systems of multivariate polynomials modulo 2^32

[Ariel Waissbein]

Hi Danilo,

Maybe you should use some other function in Mathematica. Symbolic
solving polynomial equations is a very difficult task (e.g.,
doubly-exponential worst case time complexity). But in this case it
shouldn't take that much time.


Let me notice that Z_{2^32} is not the same as F_{2^32} the field of
2^32 elements. I presume that you mean the former, which is not a field!
If you mean the latter, then you are using the wrong domain
specification in Reduce.

If you meant the field of 2^32 elements, then you should check how to
specify this in Mathematica.

For option Z_{2^32} you could try to solve the system (with elimination)
over the rationals, and once you eliminated variables "look at
everything in the integers" (multiplying by the LCM of the denominators)
and then simply take modulo 2^32 over all the solutions! If the system
of 3 polynomials in 3 variables is generic-enough it should have only
finite solutions.

If you want to continue using Mathematica, you can try your luck with
functions such as Solve or GroebnerBasis. There exist alternatives to
Groebner basis which I prefer personally, such as the Kronecker solver
(http://www.math.uvsq.fr/~lecerf/software/kronecker/) which comes as a
Magma package.

I hope this helps.

Cheers,

Ariel


Danilo Gligoroski wrote:
> 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
> 



-- 
Ariel Waissbein
RESEARCHER
CORE SECURITY TECHNOLOGIES

Tel./Fax: (54-11) 5556-2673
Humboldt 1967, 2do piso
Capital Federal,
Argentina

http://www.coresecurity.com/corelabs




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