An efficient algorithm for factoring polynomials over algebraic extension field  

作　　者：SUN Yao WANG DingKang 

机构地区：[1]SKLOIS, Institute of Information Engineering, Chinese Academy of Sciences [2]KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences

出　　处：《Science China Mathematics》2013年第6期1155-1168,共14页中国科学：数学（英文版）

基　　金：supported by National Key Basic Research Project of China (Grant No.2011CB302400);National Natural Science Foundation of China (Grant Nos. 10971217, 60970152 and 61121062);IIE'S Research Project on Cryptography (Grant No. Y3Z0013102)

摘　　要：An efficient algorithm is proposed for factoring polynomials over an algebraic extension field defined by a polynomial ring modulo a maximal ideal. If the maximal ideal is given by its CrSbner basis, no extra Grbbner basis computation is needed for factoring a polynomial over this extension field. Nothing more than linear algebraic technique is used to get a characteristic polynomial of a generic linear map. Then this polynomial is factorized over the ground field. From its factors, the factorization of the polynomial over the extension field is obtained. The algorithm has been implemented in Magma and computer experiments indicate that it is very efficient, particularly for complicated examples.An efficient algorithm is proposed for factoring polynomials over an algebraic extension field defined by a polynomial ring modulo a maximal ideal. If the maximal ideal is given by its Grbner basis, no extra Grbner basis computation is needed for factoring a polynomial over this extension field. Nothing more than linear algebraic technique is used to get a characteristic polynomial of a generic linear map. Then this polynomial is factorized over the ground field. From its factors, the factorization of the polynomial over the extension field is obtained. The algorithm has been implemented in Magma and computer experiments indicate that it is very efficient, particularly for complicated examples.

关 键 词：algorithm FACTORIZATION algebraic extension field 

分 类 号：O153[理学—数学]