• Article
  • | |
  • Metrics
  • |
  • Reference [10]
  • |
  • Related [20]
  • |
  • Cited by [5]
  • | |
  • Comments
    Abstract:

    Based on extended Dixon resultants, a new algorithm DR (Dixon resultants) is proposed to solve the system of multivariate polynomial equations. The basic idea of DR is to apply the extended Dixon resultants method to the system of multivariate polynomial equations, by taking x1,x2,…,xn-1 as variables and xn as parameter. The time complexity of DR technique is evaluated. It seems to be polynomial when the system is sparse and m=n, and the mixed volume is polynomial. Moreover, DR technique is compared with Buchberger’s algorithm and XL technique in this paper. It is shown that DR is far more efficient than Buchberger’s algorithm and XL when m=n. DR is a quite efficient algorithm and makes a good use of the sparsity of the sparse system. Besides its efficiency, another advantage of DR is that its complexity is easy to determine.

    Reference
    [1]Murphy S,Robshaw MJB.Essential algebraic structure within the AES.In:Moti Y,ed.Proc.of the 22nd Annual Int'l Cryptology Conf.on Advances in Cryptology.London:Springer-Verlag,2002.1-16.
    [2]Patarin J.Hidden fields equations (HFE) and isomorphisms of polynomials (IP):Two new families of asymmetric algorithms.LNCS 1070,Springer-Verlag,1996.33-48.http://www.minrank.org/#courtois/hfe.ps
    [3]Wadams W,Loustaunau P.An Introduction to Grobner Bases.New York:American Mathematical Society,1994.
    [4]Faugére J-C.A new efficient algorithm for computing Gr?bner bases F4.Journal of Pure and Applied Algebra,1999,139(1-3):61-88.
    [5]Courtois N,Klimov A,Patarin J,Shamir A.Efficient algorithms for solving overdefined systems of multivariate polynomial equations.In:Prened B,ed.Proc.of the EUROCRYPT 2000.LNCS 1807,Berlin,Heidelberg:Springer-Verlag,2000.392-407.
    [6]Kapar D,Saxena T,Yang L.Algebraic and geometric reasoning using dixon resultants.In:Proc.of the ISSAC.1994.99-107.
    [7]Gelfand IM,Kapranov MM,Zelevinsky AV.Discriminants,Resultants,and Multidimensional Determinants.Boston:Birkhauser,1994.
    [8]Cox D,Little J,O'Shea D.Using Algebraic Geometry.New York:Springer-Verlag,1998.
    [9]Greuel GM,Pfister G,Schonemann H.Singular 3.0.Centre for Computer Algebra A Computer Algebra System for Polynomial Computations:University of Kaiserslautern,2001.http://www.singular.uni-kl.de/
    [10]Courtois N,Goubin L,Patarin J.Second updated version of sflash specification (sflash-v2).2001.http://www.minrank.org/sflash
    Comments
    Comments
    分享到微博
    Submit
Get Citation

唐樨瑾,冯勇. Dixon结式在密码学中的应用.软件学报,2007,18(7):1738-1745

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:October 09,2005
  • Revised:April 17,2006
You are the first2038604Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063