Computer Science – Cryptography and Security
Scientific paper
2010-11-25
Computer Science
Cryptography and Security
Scientific paper
In this paper, we give a theoretical analysis for the algorithms to compute functional decomposition for multivariate polynomials based on differentiation and homogenization which are proposed by Ye, Dai, Lam (1999) and Faug$\mu$ere, Perret (2006, 2008, 2009). We 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). We also propose a conjecture such that the decomposition for a set of polynomials can be computed from that of its homogenization with high probability. Finally, we prove that the right decomposition factors for a set of polynomials can be computed from its right decomposition factor space. Combining these results together, we prove that the algorithm can compute a degree proper decomposition for a set of randomly decomposable quartic polynomials with probability one when the base field is of characteristic zero, and with probability close to one when the base field is a finite field with sufficiently large number under the assumption that the conjeture is correct.
Feng Ruyong
Gao Xiao-Shan
Zhao Shangwei
No associations
LandOfFree
On Functional Decomposition of Multivariate Polynomials with Differentiation and Homogenization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Functional Decomposition of Multivariate Polynomials with Differentiation and Homogenization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Functional Decomposition of Multivariate Polynomials with Differentiation and Homogenization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-587234