Giesbrecht's algorithm, the HFE cryptosystem and Ore's p^s-polynomials

MaRDI QIDQ4550787zbMATH OpenFDO

Authors Robert S. Coulter, George Havas, Marie Henderson

Publication date 10 February 2003

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

zbMATH Keywords

factoring polynomialsskew-polynomial ringhidden field equation cryptosystemimplementation of Giesbrecht's algorithm

Mathematics Subject Classification ID

Cryptography (94A60) Group rings (16S34)

Abstract: We report on a recent implementation of Giesbrecht's algorithm for factoring polynomials in a skew-polynomial ring. We also discuss the equivalence between factoring polynomials in a skew-polynomial ring and decomposing $p^s$-polynomials over a finite field, and how Giesbrecht's algorithm is outlined in some detail by Ore in the 1930's. We end with some observations on the security of the Hidden Field Equation (HFE) cryptosystem, where $p$-polynomials play a central role.

Recommendations

• Advances in Cryptology - CRYPTO 2003
• Publication:4941844
• Public Key Cryptography - PKC 2005
• The degree of regularity of HFE systems
• scientific article; zbMATH DE number 1617932

Cited in

(3)

• Why you cannot even hope to use Ore algebras in cryptography
• Algebraic Condition for Decomposition of Large-Scale Linear Dynamic Systems
• An isomorphism test for modules over a non-commutative PID. Applications to similarity of Ore polynomials.

This page was built for publication: Giesbrecht's algorithm, the HFE cryptosystem and Ore's $p^s$-polynomials

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