**On Functional Decomposition of Multivariate Polynomials with Differentiation and Homogenization**

*Shangwei Zhao,Ruyong Feng and Xiao-Shan Gao*

**Abstract: **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Ă¨re, 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 odd
number under the assumption that the conjecture is correct.

**Category / Keywords: **public-key cryptography / cryptanalysis

**Date: **received 24 Nov 2010, last revised 24 Nov 2010

**Contact author: **zhaoshangwei at amss ac cn

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20101125:064352 (All versions of this report)

**Short URL: **ia.cr/2010/604

[ Cryptology ePrint archive ]