Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!think.com!linus!nixbur!nixpbe!peun33!gla
From: gla@peun33.sni.de (Glaschick)
Newsgroups: comp.theory
Subject: Re: Hash function (for hardware) ?
Message-ID: <gla.664633446@peun33>
Date: 23 Jan 91 12:24:06 GMT
References: <1991Jan22.150415.14974@lth.se>
Sender: news@nixpbe.sni.de
Reply-To: glaschick.pad@nixdorf.com
Lines: 22

In <1991Jan22.150415.14974@lth.se> glenn@dit.lth.se (Glenn Jennings) writes:

>Please, can anyone help ?
> We need a "good" hardware hashing function, with these specifications:

>*  20 bits in
>*  13 bits out
>*  executable in one or two clock cycles    (makes division hard...)
>*  if possible, avoiding large multipliers

For purposes like this, I use modular arithmetic, like making pseudo-
random numbers:
	OUT = IN * 9877 + 13
Look into KNUTH for conditions for the multiplier (must be some
residue mod 8), but do some tests.

I normally use this scheme (iterated) to make checkdigits/letters
to Symbols; and it works well.
--
Rainer Glaschick, SIEMENS-NIXDORF Informationssysteme AG, Paderborn, Germany
EMail: glaschick.pad@nixdorf.com (US) or  glaschick.pad@nixdorf.de (EU)
Tel. +49 5251 14 6150 (office) +49 5254 6238  (home) Fax: +49 5251 14 6476