Variety of multivariate ideals

defund / coppersmith

Coppersmith's method for multivariate polynomials

155 stars 11 forks source link

Variety of multivariate ideals #1

Open defund opened 3 years ago

defund commented 3 years ago

Currently, I'm using Sage's variety method to solve systems of multivariate polynomials. However, the Singular backend is extremely slow in some cases. Currently, I see two alternatives worth implementing:

Polynomial resultants. Wikipedia says that past two variables, this method starts to introduce "spurious solutions". However, Coppersmith's will always have relatively few variables (and hence polynomials), so I think this is a non-issue.
A library published about a week ago: https://msolve.lip6.fr/. The Sage interface is crude, but I'm curious about its performance.

maple3142 commented 2 years ago

A crude implementation using msolve: https://gist.github.com/maple3142/c3ef210c5eae4d86680a65f774c96afc It makes solving Special Gift Revenger much faster

Sage will have a msolve implementation too: https://github.com/sagemath/sage/blob/develop/src/sage/rings/polynomial/msolve.py

defund commented 2 years ago

Oh this looks great! Do you know when this will be released in Sage?

maple3142 commented 2 years ago

The branch name said 9.7.beta5, so it will probably be released in Sage 9.7

hellman commented 1 year ago

You can also bruteforce solutions bit-by-bit. See the recover function in https://gist.github.com/hellman/a8c9a09b1ce6959226f9d75cf94b805f

The integer coeffiients of polys from Coppersmitth are crazy large, so reducing them mod a reasonable power of 2 and then doing bit-by-bit recovery is often much faster and predictable.