Hash function implementation in Prolog

Question

I am new to Prolog, and I want to know can we implement this in Prolog:

a = hash(first).

And, one who knows first can calculate a, but one who knows a can't calculate first.

These are actually two unrelated questions: (1) how to implement a unidirectional hashing function, and (2) how to do it in Prolog. If you'll post your answer to (1), people will be able to answer (2). — Little Bobby Tables
– Little Bobby Tables, Commented Feb 14, 2011 at 12:23
@All: Actually hash is a function which I want to implement in prolog. The property of hash function is that it is oneway computable. For eg. Plus(X,Y,Z) gives the sum of X and Y in Z and if you know Z and any one of X and Y, you can calculate other. Similarly In Hash function we provide a single input and it will generate output like a = hash(input). Now using input one can generate output a but using a he can't generate input. the input and a both are then numbers. Hope I am able to explain and if still some query is there I can explain in more better way. — anilonwebs
– anilonwebs, Commented Feb 14, 2011 at 13:26
The Prolog way of doing things, generally speaking, is to write a predicate hash/2 such that the call to hash(First,A) with First given as a "ground" term (integer?) succeeds by binding A to what you were denoting a = hash(first). — hardmath
– hardmath, Commented Feb 14, 2011 at 14:16
@hardmath: I was also thinking for the same but we have to provide one more functionality that by knowing First one can derive A. I was unable to visualize this thing. — anilonwebs
– anilonwebs, Commented Feb 14, 2011 at 17:00

score 1 · Accepted Answer · 2011-04-13 10:31:21Z

Typicall a hash function is not injective in general. Means that for any value a there is most often a first1 and a first2 such that:

a = hash(first1)
a = hash(first2)

So one cannot say for sure what was the argument to the hash function. But since a hash is supposed to be a small value that can be easily used in search etc., it typically gives some information about the domain of arguments.

If you want a hash where it is difficult to make backward deductions to the argument, you should use a digest. Digest is typically a value generated by some cryptographic algorithm and it is practically infeasible to make deductions about the argument.

I guess the predicates term_hash/2 or so usually found in Prolog systems qualify as hash and not as digest. But you can also implement your own hash function easily. Something along the lines:

my_hash(X,N) :- atom(X), !, atom_codes(X,L), my_hash_codes(L,N).
my_hash(X,N) :- X=..[F|L], my_hash(F,M), my_hash_args(L,R), my_hash_codes([M|R],N).

my_hash_codes([],0).
my_hash_codes([X|Y],N) :- my_hash_codes(Y,M), N is (X+M*31) mod 65531.

my_hash_args([],[]).
my_hash_args([X|Y],[M|N]) :- my_hash(X,M), my_hash_args(Y,N).

The helper predicate my_hash_codes/2 sends a list of numbers to a new number. The helper predicate my_hash_args/2 computes the hash of each list element and builds a new list. The predicate my_hash works for atoms and compounds, but it could be also extended to numbers.

Bye

Collectives™ on Stack Overflow

Hash function implementation in Prolog

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related