High Order Derivatives and Decomposition of Multivariate Polynomials
Ludovic Perret (Lip 6 - Paris 6)
Thursday 29 January 2009, 15.00, b-it 1.25 (cosec meeting room)
In this talk, we will present a new algorithm for decomposing a set of multivariate polynomials. This problem, also known as the Functional Decomposition Problem (FDP), is classical in computer algebra. This works was initially motivated by a cryptographic application, namely the security analysis of a cryptographic scheme called 2R− . We will show that we can to use high order partial derivatives to improve a recent algorithm proposed in [1].
[1] J.-C. Faugère, and L. Perret. ``An Efficient Algorithm for Decomposing Multivariate Polynomials and its Applications to Cryptography". Special Issue of JSC on "Gröbner Bases techniques in Coding Theory and Cryptography". To appear. This is a joint work with J.C. Faugère.