Common composites of triangular polynomial systems and hash functions. (January 2016)

• Record Type: Journal Article
• Authors: Gómez-Pérez, Domingo; Gutierrez, Jaime; Ostafe, Alina
• Is Part Of: Journal of symbolic computation. Volume 72(2016)
• Page Start: 182
• Page End: 195
• Publication Date: 2016-01
• Subjects: Polynomial systems -- Composition -- Collision; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.02.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We study common composites of triangular polynomial and rational function systems with favorable effects under composition: polynomial degree growth. We construct classes of such systems that do not have common composites. This property makes them suitable for the construction of a recently proposed hash function. We give estimates for the number of collisions of this hash function using these systems. We also mention as future work the study of common composites of systems with sparse representation and pose an open problem related to their usability as hash functions.