On functional decomposition of multivariate polynomials with differentiation and homogenization

DOI10.1007/S11424-012-1144-8MaRDI QIDQ488898zbMATH OpenOpenAlexFDO

Authors Ruyong Feng, Xiao-Shan Gao, Shangwei Zhao

Publication date 27 January 2015

Published in Journal of Systems Science and Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.5545

zbMATH Keywords

cryptosystem analysisfunctional decompositionhomogeneous polynomialsmultivariate polynomialright factor space

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60)

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$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.

Recommendations

• On Multivariate Homogeneous Polynomial Decomposition
• On decompositions of multivariate functions
• scientific article; zbMATH DE number 745314
• scientific article; zbMATH DE number 2125607
• Homogenization and the polynomial calculus
• scientific article; zbMATH DE number 1670882
• On multivariate rational function decomposition
• Functional decomposition of polynomials: the wild case
• Une décomposition des fonctions lisses par rapport à un polynôme quasi-homogène

Cites work

• Cryptanalysis of 2R− Schemes
• Decomposition of generic multivariate polynomials
• Functional decomposition of polynomials: the tame case
• Functional decomposition of polynomials: the wild case
• scientific article; zbMATH DE number 1107704 (Why is no real title available?)
• scientific article; zbMATH DE number 1418302 (Why is no real title available?)
• scientific article; zbMATH DE number 3409447 (Why is no real title available?)
• Inherently improper surface parametric supports
• Matrix multiplication via arithmetic progressions
• Multivariate polynomial decomposition
• Proper reparametrization for inherently improper unirational varieties
• The proper parametrization of a special class of rational parametric equations

Cited in

(6)

• High order derivatives and decomposition of multivariate polynomials
• Decomposition of generic multivariate polynomials
• On Multivariate Homogeneous Polynomial Decomposition
• Algorithms for the Functional Decomposition of Laurent Polynomials
• scientific article; zbMATH DE number 1263355 (Why is no real title available?)
• DME: A Full Encryption, Signature and KEM Multivariate Public Key Cryptosystem

This page was built for publication: On functional decomposition of multivariate polynomials with differentiation and homogenization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q488898)