Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Class of Easily Implemented Hash Functions

IP.com Disclosure Number: IPCOM000046336D
Original Publication Date: 1983-Jul-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Carter, JL: AUTHOR [+3]

Abstract

This article desribes a universal class of hash functions which utilize multiplication over a finite field. These functions are easy to implement in hardware and have good 'randomizing' properties.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Class of Easily Implemented Hash Functions

This article desribes a universal class of hash functions which utilize multiplication over a finite field. These functions are easy to implement in hardware and have good 'randomizing' properties.

In an earlier article, J. L. Carter and M. N. Wegman 1 introduced the notion of a universal2 family of hash functions and gave some examples. This concept has proven to be very important in a number of situations. The scheme described subsequently produced such universal2 families of hash functions.

The basic scheme is as follows: Let F be a finite field, let A be a subgroup of the additive group of F, and let B=F/A be the set of cosets of A in F. For any x in F, we will denote the coset containing x by FxJ. For each a in F, we define the hash function ha which maps from F to B by ha(x)=Oa*xJ, where * is the multiplicative operation of the field. Let H(F,A)=Lha a is in F1. It turns out that H(F,A) is universal2 for all choices of F and A. A method is now described which can be used to implement this scheme in hardware.

The easiest fields to work with on a digital computer are those of characteristic 2. The elements of the field GF(2n) -a field of characteristic 2 with 2n elements- will be the polynomials with 0,1 coefficients and degree less than n. Each such polynomial is represented in a computer simply as the n-element Boolean vector of the coefficients. To define the field operations, it is necessary to have a polynomial of degree n with 0,1 coefficients which is irreducible over GF(2). Such polynomials exist for all nJ0. Some are listed in the table on the next page. Given such a polynomial Q(X), the field operations can be defined easily: addition is just component-wise mod 2 addition (that is, the exclusive-OR operation), and multiplication corresponds to polynomial multiplication modulo the polynomial Q(X). Hardware implementations of this multiplication are already known (see reference [2], chapter 2, for example).

For certain choices of the subgroup A...