Welcome to the resource topic for 2023/731
Title:
Fast Exhaustive Search for Polynomial Systems over F3
Authors: Bo-Yin Yang, Wei-Jeng Wang, Shang-Yi Yang, Char-Shin Miou, Chen-Mou Cheng
Abstract:Solving multivariate polynomial systems over finite fields is an important
problem in cryptography. For random F2 low-degree systems with equally many
variables and equations, enumeration is more efficient than advanced solvers for all
practical problem sizes. Whether there are others remained an open problem.
We here study and propose an exhaustive-search algorithm for low degrees systems
over F3 which is suitable for parallelization. We implemented it on Graphic Processing
Units (GPUs) and commodity CPUs. Its optimizations and differences from the F2
case are also analyzed.
We can solve 30+ quadratic equations in 30 variables on an NVIDIA GeForce GTX
980 Ti in 14 minutes; a cubic system takes 36 minutes. This well outperforms
existing solvers. Using these results, we compare Gröbner Bases vs. enumeration for
polynomial systems over small fields as the sizes go up.
ePrint: https://eprint.iacr.org/2023/731
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .