东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

On functional decomposition of multivariate polynomials with differentiation and homogenization

ISSN号：1009-6124
期刊名称：Journal of Systems Science and Complexity
时间：0
页码：329-347
分类：O174.14[理学—数学;理学—基础数学] TP311.52[自动化与计算机技术—计算机软件与理论;自动化与计算机技术—计算机科学与技术]
作者机构：[1]Beijing Electronic Science and Technology Institute, Beijing 100070, China., [2]KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China.
相关基金：partially supported by a National Key Basic Research Project of China under Grant No. 2011CB302400;by a Grant from NSFC with Nos 60821002 and 10901156
相关项目：微分、差分方程的Galois理论及求liouvillian解的算法研究

作者： Zhao, Shangwei|Feng, Ruyong|Gao, Xiao-Shan|

关键词：多元多项式, 功能分解, 同质化, 作者, 分化, 四次多项式, 分解因子, 计算, Cryptosystem analysis, functional decomposition, homogeneous polynomials, multivariatepolynomial, right factor space.

中文摘要：

<正>This paper gives a theoretical analysis for the algorithms to compute functional decomposition for multivariate polynomials based on differentiation and homogenization which were proposed by Ye,Dai,and Lam(1999) and were developed by Faugere,Perret(2006,2008,2009).The authors show that a degree proper functional decomposition for a set of randomly decomposable quartic homogenous polynomials can be computed using the algorithm with high probability.This solves a conjecture proposed by Ye,Dai,and Lam(1999).The authors also propose a conjecture which asserts that the decomposition for a set of polynomials can be computed from that of its homogenization and show that the conjecture is valid with high probability for quartic polynomials.Finally,the authors prove that the right decomposition factors for a set of polynomials can be computed from its right decomposition factor space.

英文摘要：

This paper gives a theoretical analysis for the algorithms to compute functional decomposition for multivariate polynomials based on differentiation and homogenization which were proposed by Ye, Dai, and Lam （1999） and were developed by Faugere, Perret （2006, 2008, 2009）. The authors show that a degree proper functional decomposition for a set of randomly decomposable quartic homoge- nous polynomials can be computed using the algorithm with high probability. This solves a conjecture proposed by Ye, Dal, and Lam （1999）. The authors also propose a conjecture which asserts that the decomposition for a set of polynomials can be computed from that of its homogenization and show that the conjecture is valid with high probability for quartic polynomials. Finally, the authors prove that the right decomposition factors for a set of polynomials can be computed from its right decomposition factor space.

同期刊论文项目