Loading...
Please wait, while we are loading the content...
Similar Documents
DEMOCRACY — A Heuristic for Polynomial Systems of Equations over Finite Fields ( Extended Abstract )
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bard, Gregory V. |
| Copyright Year | 2010 |
| Abstract | This paper presents a heuristic for solving polynomial systems of equations on finite fields larger than GF(2), via stochastic local search (SLS). It was inspired by the SLS-based SAT-solvers G-SAT, Walk-SAT and Tabu-SAT. Called DEMOCRACY, the equations vote on which values for a given variable will satisfy as many as possible of them. Variables, one at a time, are thusly changed from an initial random setting, until all equations are satisfied. We show that this algorithm can solve the Brent Equations, a cubic system of 64 equations and 84 unknowns, taken mod 7, in 2–8 minutes. On this system, MAGMA’s F4 algorithm crashed for lack of memory, and Singular via SAGE timed out after 10 hours. Similar results have been observed for random quadratic systems of equations also. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.gregorybard.com/papers/abstract_for_yacc.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
