A time-memory tradeoff in Faug?re's algorithm for computing Gr?bner bases
Date Issued
2010
Date
2010
Author(s)
Huang, Yun-Ju
Abstract
Solving multivariate systems of polynomial equations is an important problem both as a subroutine in algebraic cryptanalysis and in its own right. Currently, the most efficient solvers are the Gröbner-basis solvers, which include the XL algorithm, as well as Faugère''s F4 and F5 algorithms.
The F4 algorithm is an advanced algorithm for computing Gröbner basis. However, the algorithm has exponential space complexity. This poses a serious challenge when we want to use it to solve instances of sizes of practical interest. For example, if we are going to solve a multivariate polynomial system of 40 equations in 40 variables, then most of today''s computers will run out of memory before the execution of the algorithm finishes. Furthermore, the original F4 algorithm does not provide much flexibility in terms of controlling memory usage.
In this thesis, we set out to address this shortcoming by starting with the following questions about F4''s memory consumption.
1. Can F4 , or any variant of it, be executed under any memory limitation?
2. If not, at least how much memory is necessary for F4 to be successfully executed?
3. Can we make the modified F4 algorithm run faster when given more memory?
Throughout the process of answering these questions, we observe the memory usage in each part of the F4 algorithm, based on which we propose modifications to the algorithm.
Our modified F4 algorithm uses less memory than the original algorithm. More importantly, our modified F4 algorithm runs faster than the original algorithm using the same amount of memory. Our modified F4 algorithm controls its memory consumption by dividing the work into chucks of smaller working sets and executing them one at a time. This in effect trades time for memory because it involves more computation, some of which might even be carried out repeatedly. We will show that such a trade-off makes sense in terms of time-memory product and is extremely flexible by showing the following.
1. Our modification on average yields smaller time-memory products than the original F4 algorithm.
2. Our modified F4 algorithm allows the Gröbner basis be computed using an arbitrary amount of memory as long as it is above the minimum amount of memory required to solve the instance.
3. The more memory our modified F4 algorithm uses, the faster it runs.
We have implemented a prototype of the proposed modified F4 algorithm and conducted an extensive set of experiments with it. The experiment results demonstrate that the proposed modification does achieve the three goals listed above over a broad set of parameters and problem sizes. As an example showcase, it is possible to solve certain instances using only 10% of the memory in less than twice as much time than the original F4 algorithm.
Subjects
Cryptography
algebraic cryptanalysis
system solver
Groebner basis
Faugere’s F4 algorithm
time-memory trade-off
File(s)![Thumbnail Image]()
Loading...
Name
ntu-99-R96221042-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):90b6c9125f18c5b04f0df759570bf1cf