For a set of values N, I wanted to find out how many functions existed with the following properties:

**f(f(a, b), c) = f(f(a, c), b)**

**∃ g : g(a, f(a, b)) = b**

**where**

**a, b, c ← N**

Now I have an answer, but maybe not enough time to explain it. The number of such functions is:

**(|N|)! * (|N|-1)! * (|N|-2)! * ... * (1)! / (|N|-1)**

So, for example, I determined experimentally that there were

**96**such functions for**|N| = 4**, and this works out as**4! * 3! * 2! * 1! / 3 = 96**.
In the process of working this out, I realized that these functions have the interesting property that there is always a value

**i**such that**f(x, i) = x**. I also worked out (for the heck of it) a way to derive the truth table for the**nth**function. I ought to write it down somewhere, or I will almost certainly forget it, but I don't have time at the moment.
The reason I was interested in this question is that this type of function could be used in establishing a shared secret for cryptography. For example, I could publish a function

**f**, a value**a**,**and a value****f(a, b)**, then you could publish**f(a, c)**. I could take your value and generate**f(f(a, c), b)**, while you could take mine and generate the same value as**f(f(a, b), c)**. The resulting value would be our shared secret, provided the inverse function**g**is difficult to discover.
## No comments:

## Post a Comment