Re: Hash function

bobic wrote:
Hi, everyone. Here, I have a problem about hash function. That is, can
we construct a hash function, such that, H(x)=y, where x is a random
string, and y=p_1*...*p_k mod p, p_1,...,p_k are small primes, p is a
large prime.

Are you asking if it is possible to design a hash function that has
the above properties? Of course -- you can do whatever you want; the
thing is, will it be a good hash function from the point of view of
pre-image and collision resistance? (most likely not)

As an example: take each character (well, each block of N bits, for
a given value of N) of the input, and determine the lowest prime number
that is greater than that N-bit number; multiply them together and
then use some other trick to come up with the large prime -- use a
randomized primality test that uses a deterministic *pseudo-random*
generator that is seeded with something obtained from the data.

Hope this answers your question.

Carlos
--
.

Relevant Pages

  • Re: elisp: format-time-strings %z problem
    ... a hash function, then that hash function is reversible (ie, it is not ... randomly-chosen inputs map to the same output should be ... a one-to-one and onto map of the space of N-bit inputs to a permutation ... it really is _much_ harder to invert the hash than to ...
    (comp.lang.scheme)
  • hash/SHA-1 questions
    ... Suppose H is a hash function with N-bit output. ... to be H restricted to n-bit input, ...
    (sci.crypt)