**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)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]