收稿日期: 2013-12-27
修回日期: 2014-02-21
网络出版日期: 2014-11-15
基金资助
国家自然科学基金(11271363)资助
Triangular set algorithms for polynomial equations solution in finite fields
Received date: 2013-12-27
Revised date: 2014-02-21
Online published: 2014-11-15
王成龙 , 陈玉福 . 有限域上多项式方程组求解的三角列算法[J]. 中国科学院大学学报, 2014 , 31(6) : 721 -730 . DOI: 10.7523/j.issn.2095-6134.2014.06.001
A top-down quasi triangular set algorithm and a triangular set algorithm for polynomial equations solution in finite fields are proposed and the complexity analysis for the first algorithm is given. Both of the algorithms are implemented in F3 and the experimental results show effectiveness of the algorithms.
Key words： triangular set; polynomial equations; finite field; algorithm
[1] Lidl R, Niederreiter H, Chon P M. Finite fields[M]. London: Cambridge University Press, 1997.
[2] Katz J, Lindell Y. Introduction to modern cryptography[M]. Boca Raton: CRC PRESS, 2007.
[3] Wang H Z, Zhang H G, Guan H M, et al. Multivariable algebra theory and its application in cryptography[J]. Journal of Beijing University of Technology, 2010, 36(5): 627-634(in Chinese). 王后珍, 张焕国, 管海明,等. 多变量代数理论及其在密码学中的应用[J]. 北京工业大学学报, 2010, 36(5): 627-634.
[4] Aubry P, Lazard D, Moreno Maza M. On the theories of triangular sets[J]. Journal of Symbolic Computation, 1999, 28: 105-124.
[5] Aubry P, Moreno Maza M. Triangular sets for solving polynomial systems: a comparative implementation of four methods[J]. Journal of Symbolic Computation, 1999, 28: 125-154.
[6] Wu W T. Basic principles of mechanical theorem-proving in elementary geometries[J]. Journal of Automated Reasoning, 1986, 2(3): 221-252.
[7] Wu W T. On zeros of algebraic equations: an application of Ritt principle[J]. Kexue Tongbao, 1986, 31(1): 1-5.
[8] Lazard D. A new method for solving algebraic systems of positive dimension[J]. Discrete Applied Mathematics, 1991, 33(1-3): 147-160.
[9] Li B. An algorithm to decompose a polynomial ascending set into irreducible ones[J]. Acta Analysis Functionalis Applicata, 2005, 7(2): 97-105.
[10] Dahan X,Moreno Maza M,Schost E, et al. Lifting techniques for triangular decompositions[C]//Proc ISSAC'05. New York: ACM Press, 2005: 108-115.
[11] Lin D D, Liu Z J. Some results on theorem proving in geometry over finite fields[C]//Proc ISSAC'93. New York: ACM Press, 1993: 292-300.
[12] Gao X S, Chai F, Yuan C. A characteristic set method for solving boolean equations and applications in cryptanalysis of stream ciphers[J]. Journal of Systems Science and Complexity, 2008, 21(2): 191-208.
[13] Gao X S, Huang Z. A characteristic set method for equation solving in finite fields[J]. Journal of Symbolic Computation, 2012, 47(6): 655-679.
[14] Li X L, Mou C Q, Wang D M. Decomposing polynomial sets into simple sets over finite fields: the zero-dimensional case[J]. Computers and Mathematics with Applications,2010, 60(11): 2 983-2 997.
[15] Mou C Q, Wang D M, Li X L. Decomposing polynomial sets into simple sets over finite fields: the positive-dimensional case[J]. Theoretical Computing Science, 2013, 468: 102-113.
[16] Bardet M, Faugère J C, Salvy B. Complexity of Grebner basis computation for semi-regular overdetermined sequences over F2 with solutions in F2, INRIA report RR-5049[R]. 2003.
[17] Brickenstein M, Dreyer A. PolyBoRi: a freamwork for Grbner basis computations with boolean polynomials[J]. Journal of Symbolic Computation, 2009, 44(9): 1 326-1 345.
[18] Faugère J C. A new efficient algorithm for computing Grebner bases(F4)[J]. Journal of Pure and Applied Algebra, 1999, 139(1-3): 61-88.
[19] Faugère J C. A new efficient algorithm for ccomputing Grebner bases without reduction to zero(F5)[C]//Proc ISSAC'02. NewYork: ACM Press, 2002: 75-83.
[20] Courtois N, Klimov A, Patarin J, et al. Efficient algorithms for solving overdetermined systerms of multivariate polynomial equations[C]//Proc EUROCRYPT'00. Verlag Berlin, Heidelberg: Springer, 2000: 392-407.
[21] Kapur D, Wan H K. Refutational proofs of geometry theorems via characteristic set computation[C]//Proc ISSAC'90. New York: ACM Press, 1990: 277-284.
[22] Wang D M. An elimination method for polynomial systems[J]. Symbolic Computation, 1993, 16(2): 83-114.
/
| 〈 |
|
〉 |
