On enumeration of polynomial equivalence classes  

作　　者：WANG TianZe LIN DongDai 

机构地区：[1]State Key Laboratory of Information Security,Institute of Software,Chinese Academy of Sciences,Beijing 100190,China [2]Graduate University of Chinese Academy of Sciences,Beijing 100149,China

出　　处：《Science China Mathematics》2012年第6期1137-1152,共16页中国科学：数学（英文版）

基　　金：supported by National Basic Research Program of China (973 Program)(Grant No. 2011CB302400);National Natural Science Foundation of China (Grant No. 60970152);Grand Project of Institute of Software (Grant No. YOCX285056)

摘　　要：The isomorphism of polynomials （IP）, one of the hard problems in multivariate public key cryptography induces an equivalence relation on a set of systems of polynomials. Then the enumeration problem of IP consists of counting the numbers of different classes and counting the cardinality of each class that is highly related to the scale of key space for a multivariate publi9 key cryptosystem. In this paper we show the enumeration of the equivalence classes containing ∑n-1 i=0 aiX^2qi when char（Fq） = 2, which implies that these polynomials are all weak IP instances. Moreover, we study the cardinality of an equivalence class containing the binomial aX2qi ＋ bX2qj （i ≠ j） over Fqn without the restriction that char（Fq） = 2, which gives us a deeper understanding of finite geometry as a tool to investigate the enumeration problem of IP.The isomorphism of polynomials(IP),one of the hard problems in multivariate public key cryptography induces an equivalence relation on a set of systems of polynomials.Then the enumeration problem of IP consists of counting the numbers of different classes and counting the cardinality of each class that is highly related to the scale of key space for a multivariate public key cryptosystem.In this paper we show the enumeration of the equivalence classes containing ∑n-1 i=0 aiX2qi when char(Fq) = 2,which implies that these polynomials are all weak IP instances.Moreover,we study the cardinality of an equivalence class containing the binomial aX 2q i + bX 2qj(i=j) over Fqn without the restriction that char(Fq) = 2,which gives us a deeper understanding of finite geometry as a tool to investigate the enumeration problem of IP.

关 键 词：enumerative problem isomorphism of polynomials finite geometry 

分 类 号：O175.12[理学—数学] TP301.6[理学—基础数学]