A neat footnote on function difficulty

In my last post, I argued that the difficulty of the most difficult functions in F increases in proportion to N² (where F is the set of binary functions that operate on values in [0..N-1]).

I was trying to think of a way to test this conclusion for a specific case, when I remembered an earlier post where I argued that these functions can all be represented as polynomials, as long as N is prime. This gives us a perfect test-case, because polynomials can be described as programs in the context of the previous post, where the instruction set consists of addition and multiplication.

So let's take the case where N = 23. The most complex polynomial representing a function in F will have 23² terms. In reality, the most efficient way to evaluate the function would be to preprocess x²..x²² and y²..y²². This wasn't something I accounted for in my model, but let's run with it anyway. Preprocessing would require 22 operations for x and 22 for y.

There would be 23² = 529 terms in the polynomial, and for each term we would need to perform two multiplications, so 1058 multiplications. We would need 528 additions to add the terms together.

In total, that would mean 22 + 22 + 1058 + 528 = 1630 operations would be required for the most complex function in F.

How does that compare to our prediction? For N = 23 and A = 2, the lower limit for the difficulty of functions in F would be (23² ln 23 - ln (23+2)) / (ln 4 + ln 2 + ln (23+2)) = 312.45.

So, in this test case, it seems the conclusion is right, since 1630 > 312.45. The general case for any prime N can be easily shown, where the difficulty for this particular case is d' = 2(N-1) + 3N² - 1.

The other thing that is interesting about this is that, for this particular instruction set, we can say something about the makeup of the function space in terms of difficulty. There are N^N2 functions in the set, of which (N-1)^N2 fall into the "most difficult" category. In other words, difficult functions vastly outnumber easy ones, with the ratio of "most difficult" functions to all others being 1 - ((N - 1)/N)^N2.

Difficulty of functions

This weekend I have been thinking about abstract ways to measure how difficult it is to evaluate functions given a hypothetical computer with a specific instruction set.

In particular, I want to see if I can find a lower limit of difficulty for the most difficult functions of a particular type. I thought I had it nailed last night, but as soon as I went to bed I realized I was wrong.

Imagine a computer with the following properties:

1. The computer's only data type is an integer in the set [0..N-1], called an int.

2. The computer's programs represent functions that take two ints and returns an int. The set of all such functions is F.

3. The computer has an instruction set composed of A <= N+2 functions drawn from F. The computer can easily evaluate every function in its instruction set.

4. The computer's programs are finite function trees, so each program has a root function drawn from the instruction set, which takes two parameters. The two parameters of the root function may be function trees, constant ints, or the special symbols x and y which evaluate to the program's two input parameters. There is no recursion.

5. The difficulty of a program is the average number of operations required to evaluate the program for any possible input values x and y.

For simplicity, we initially assume that there is no lazy evaluation.

Given a computer like this, can we put a lower limit on the difficulty of the most difficult function in F?

If there is no lazy evaluation, then the difficulty of a function is proportional to the number of instructions. Given that there are N^N2 functions in F, if you could write maximally efficient programs to represent each of those functions, how big would the largest such efficient program need to be?

There are p₀ = N+2 distinct programs that could be written with zero instructions. These would be the programs that returned a constant value, or else x or y with no modification.

The number of distinct programs that can be written with one instruction is p₁ = A*(p₀ * p₀) = A(N+2)². That is, there are A possible instructions, which must take a program with zero instructions for each parameter.

The number of distinct programs that can be written with two instructions is p₂ = A*(p₀ * p₁ + p₁ * p₀) = 2A²(N+2)³. That is, the first parameter may be a zero-instruction tree, in which case the second parameter must be a 1-instruction tree, or vice-versa.

The number of distinct programs that can be written with three instructions is p₃ = A*(p₀ * p₂ + p₁ * p₁ + p₂ * p₀) = 5A³(N+2)⁴. The progression we are seeing here is that p_n = s_nAⁿ(N+2)ⁿ⁺¹, where s_n is the number of different trees that can be formed with n binary functions.

There will be a lot of overlap in the program space, meaning there will be multiple programs that can evaluate to the same function. This means we can't say that n instructions can always represent p_n functions, but we can say that they will represent no more than p_n functions. Thus, for p_n = |F| = N^N2, we can be certain that the most complex program representing a function in F can be no smaller than n instructions.

So the lower limit d on the difficulty of the most difficult function in F is calculated as follows:

p_d > N^N2.
s_dA^d(N+2)^d+1 > N^N2.

For large values of d, I think 3^d < s_d < 4^d. This needs to be proven, though. If it is true, we could fudge a bit and say

4^dA^d(N+2)^d+1 > N^N2.
d ln 4 + d ln A + d ln (N+2) + ln (N+2) > N² ln N.
d ln 4 + d ln A + d ln (N+2) > N² ln N - ln (N+2).
d > (N² ln N - ln (N+2)) / (ln 4 + ln A + ln (N+2)).

Of course, there is a lot more to gnaw on here, like operation laziness and pre-evaluation, which might be real game-changers. But as we have it now, the difficulty of the most difficult functions in F increases in proportion to N².

Borrowing associative and commutative properties

I was trying to come up with a set of functions that had associative and commutative properties last week, and I found a way to "borrow" those properties from addition.

Start out with a function f(x) in Z_N that acts as a permutation of the elements [0..N-1]. Since f(x) is a permutation, there exists the inverse f^-1(x).

From these, generate a function F(x, y) = f(f^-1(x) + f^-1(y)). The new binary function F(x, y) has associative and commutative properties, which it has borrowed from addition. The commutative property is obvious, because f(f^-1(x) + f^-1(y)) = f(f^-1(y) + f^-1(x)), so F(x, y) = F(y, x). The associative property works like this:

F(F(x, y), z) = F(x, F(y, z))

Rewrite in terms of f(x) and f^-1(x):

f(f^-1(f(f^-1(x) + f^-1(y))) + f^-1(z)) = f(f^-1(x) + f^-1(f(f^-1(y) + f^-1(z))))

Since f^-1(f(x)) = x, we can simplify both sides as follows:

f(f^-1(x) + f^-1(y) + f^-1(z)) = f(f^-1(x) + f^-1(y) + f^-1(z))

The number of these functions is N!, i.e. the number of permutations of [0..N-1]. These functions have a zero value i, such that F(x, i) = x. Since F is associative, for simplicity we can write F(x, y, z) for either F(F(x, y), z) or F(x, F(y, x)).

Suppose you try to build a multiplication-like function G from F, such that, for example, G(x, 4) = F(x, x, x, x). The resulting function is simply G(x, y) = f(y * f^-1(x)). Interestingly, this multiplication-like function is not guaranteed to be associative or commutative. In fact, it ends up being more like an exponent than multiplication.

If someone someday figures out how to calculate the discrete logarithm in polynomial time, and thereby break a number of existing cryptographic schemes, I wonder if other exponent-like functions could prove to be less easy to break.

Complexity of functions and their inverses

I'm interested in the question of trapdoor functions. I want to get a general idea of how common it is to have a function that is easy to calculate, whose inverse is difficult to calculate.

Before I go any further, I want to point out that in this blog post I'm only talking about calculating functions as polynomials. It's possible that a function that is difficult to calculate as a polynomial (using multiplication and addition as primitives) could be easy to calculate using other operators (like XOR, SHIFT, or exotic operators we've never used before). In another post I'll outline the parameters that I believe cover every possible set of primitives for modular calculations.

But for now, I'm just talking about traditional modular polynomials. For a set of invertible functions with inputs and outputs in Z_P, what is the relationship between the complexity of the function and the complexity of its inverse?

For the purpose of this short post, I've looked at P=5 and invertible functions f(x,y) with an inverse g(x,z) such that g(x, f(x, y)) = y. Note that I am not looking for the commutative property that f(f(x, y), z) = f(f(x, z), y).

I'm measuring the complexity of each function as a measure of the estimated processing time for its polynomial, counting the number of terms minus one plus the sum of all of the exponents. (That is, counting the number of additions and multiplications required). So, for example, 3x⁴y² + 17y would have a complexity if 2 terms - 1 + 4 + 2 + 1 = 8, reflecting the 7 multiplications and one addition.

In Z₅ there are a total of 5⁵² = 298,023,223,876,953,152 functions that take two parameters. Of these, (5!)⁵ = 24,883,200,000 are invertible as I described. All I have is a little laptop and a few hours here and there, so I can't even conceive of exploring this entire function space exhaustively.

For this short post, I took 1000 random samples from the function space for testing. It turns out that the complexity of every function was exactly the same as the complexity of its inverse. 799 of the samples had a complexity of 124, and 199 of the samples had a complexity of 123. Two samples had a complexity of 115.

So, when treated as polynomials, a function and its inverse seem to require the same processing time.

Nifty functions

About a month ago, I worked out how many functions had the following properties:

Since then, I've figured out how to write out pretty equations in Google Docs. (Can you tell?) The number of such functions, expressed prettily, is:

This type of function probably has a proper name, but I don't know what it is. For the purpose of this blog post, I'll call these "nifty functions". A month ago, I thought I had figured out how to generate the truth table for the nth nifty function, but it turns out I was wrong. Painfully wrong.

A couple weeks ago, I wrote some code that will take a truth table and solve for the simplest modular polynomial that would generate the truth table. I thought it would be neat to see what the nifty functions looked like as polynomials.

That's where I realized I was painfully wrong about how easy it would be to generate the truth table for the nth nifty function. While it appears I was right about the number of these functions, generating the truth table turned out to be far more complicated than I thought. However, I have emerged tired but victorious. I can now list out polynomials that represent the nifty functions for a given (mod P).

Naturally, quite a bit of processing is required relative to P, so I am only exploring small primes at the moment. I'm interested in two questions:

1. If you have a polynomial expression that is nifty in (mod P_a), is it also nifty in (mod P_b)?
2. Are there nifty functions where f() can be processed in polynomial time, but its inverse g() cannot be?

Given the tools I have developed so far, I should be able to test these questions experimentally for small P. In the mean time, I leave you with one of the most complex nifty polynomials for (mod 5).

Discrete logarithm as a polynomial

I finally had time to retool my "solver" so it could work on polynomials with multiple indeterminates. Much debugging was required, but in the process I discovered a number of ways to make it run more quickly.

Once I had it running correctly, I wanted to start exploring the modular logarithm function. I immediately ran into trouble because the modular exponent is not a permutation, so for some values there may be multiple valid logarithms, and for other values there may be none. I'll have to figure out how to make that work properly.

In the meantime I managed to put in place some manual workarounds. The solutions have a strange kind of beauty, but I'm not sure how to present them, and I think I should find the proper way to handle the shortcomings I noted above.

How long would it take to calculate the logarithm (mod N) as a polynomial?  Looking at sample solutions for N=3 through N=11, I think the calculation could be done in roughly 2N³ operations (multiplications and additions--provided unlimited memory to cache precalculated values).  Given that the brute force approach would only require a maximum of 2N multiplications and comparisons, I think it's fair to say that the discrete logarithm probably cannot be calculated in polynomial time with any kind of polynomial expression.

Multiplicative inverse

I was thinking about the conclusions I came to in my last post, and it occurred to me that I could build a little problem solver. You could feed part of a truth table into it, and it would generate the simplest polynomial that would explain the truth table.

I actually managed to write the thing, and it works. I have never written anything like this before, so it was an interesting experiment.

Of course, to write it, I had to write a function to calculate the multiplicative inverse of a number in [1..N-1] (mod N), so naturally the first thing I wanted to do with it when I was done is see what polynomial generates the multiplicative inverse.

My solver only works for prime values of N, and the result was interesting:

x^-1 = x (mod 3)

x^-1 = x³ (mod 5)

x^-1 = x⁵ (mod 7)

x^-1 = x⁹ (mod 11)

The pattern here, of course, is that x^-1 = x^N-2 (mod N). The Wikipedia article on modular multiplicative inverse mentions that this precise formula works, but only for prime values of N.

My current solver only works for polynomials of a single indeterminate, but I ought to be able to write one that works for multiple indeterminates. If I get the time to do it, the first thing I'm going to look at is the inverses of the exponent function.

Solution to the polynomial question

In answer to the question that was bugging me in my last post, It turns out that every function operating on values [0..N-1] can be represented as a polynomial.  The proof is that you can generate the polynomial from the function's truth-table. (I'm not sure if that's a proof that a real mathematician would accept, but it works for me.)

The basic building block for this is the following expression, which returns a value of f(a) for x = a, and a value of 0 for all other values of x:

To build the polynomial for a function that takes only one argument, you sum up the polynomials for all possible values of x. So, you can say:

From there, it is just a hop, skip and a jump to functions with multiple arguments. For f(x,y), you can do this hideous thing:

Not necessarily practical, but it does prove the point that every possible function (mod N) can be represented as a polynomial.

(Note added 12/23/2013--I just realized this only works if N is prime, otherwise we don't have a modular multiplicative inverse for all (a-i), (i-j), (h-j). That suggests that for non-prime values of N there might be some functions that couldn't be expressed as polynomials, which is interesting.)

Polynomial Puzzle

Think about a set of integer values [0..N-1].  The total number of functions that can take two values from this set and return a third value from the same set is N^N2 (i.e. the number of distinct truth tables that can be built for those values).  This is the same as the number of polynomials of the following form (where k_fij is also drawn from [0..N-1]):

So the question bugging me is this:  Can every function that takes a pair of values in [0..N-1] and returns a value in [0..N-1] be represented by one of these polynomials?

I think it can, but I'm having a hard time proving it to myself.

If so, this gives us another (perhaps more meaningful) way to represent functions as numbers.  Any function f(a, b) like the one above could be encoded as a number as:

In this system, addition would always be encoded as N+1, and multiplication would be encoded as N^N+1.

For what it's worth.

Figured it out

This morning (or last night...it was dark, I was sleepy) I figured out the answer to the question that started this whole function/number thing.

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.

Quickly: How to turn a number into a function

In these recent posts, I have been talking about hunting for functions with certain properties. I decided to try an exhaustive search of a particular function space to find the functions I was looking for, by identifying a 1:1 relationship between numbers and functions, then iterating through all of the numbers and testing the corresponding function.

In brief, I treated the number as an efficient encoding of the truth table for the function. By "efficient", I mean I used an encoding system in which every number in the range represented a valid and distinct truth table, and all possible functions were represented in the range. Since I'm talking about functions that operate on discrete, finite sets of values, the number of truth tables is finite.

First, I used a system I came up with a while ago to represent permutations as numbers. I originally devised this as a way to encode every possible shuffled state of a deck of cards, but it really works for any permutation. Encode the permutation f_a as follows:

R_p(f_a) = N! (f_a:0(0)/N! + f_a:1(1)/(N-1)! + f_a:2(2)/(N-2)! ... f_a:3(N-1)/1!)

Where f_a:n returns the zero-based index of f_a(n) within the ordered set of values returned by f_a(x) where x >= n.

So, for example, the permutation f_a(x) = x + 2 (modulo 4) can be represented as the number 10.  Here's how the encoding works:

f_a:0 returns the zero-based index of f_a(0) in the set [0, 1, 2, 3].  That is, it returns 2, since f_a(0) = 2, and 2 is found at position 2 in the set.

f_a:1 returns the zero-based index of f_a(1) in the set [0, 1, 3].  That is, it returns 2, since f_a(1) = 3, and 3 is found at position 2 in the set.

f_a:2 returns the zero-based index of f_a(2) in the set [0, 1].  That is, it returns 0, since f_a(2) = 0, and 0 is found at position 0 in the set.

f_a:3 returns the zero-based index of f_a(3) in the set [1].  That is, it returns 0, since f_a(3) = 1, and 1 is found at position 0 in the set.

So:

R_p(λx → x + 3) = 4! (2/4! + 2/3! + 0/2! + 0/1!) = 10

In my last post, I treated the function f(a, b) as selecting permutation f_a from an indexed set, and applying it to value b. The N permutations required for distinct values of a can all be encoded together in a single number, as follows:

R_f(f) = R_p(f₀)(N!)⁰ + R_p(f₁)(N!)¹ + ... + R_p(f_N-1)(N!)^N-1

So the function f(x, y) = x + y (modulo 4) can be encoded as follows, given that R_p(f₀) = 0, R_p(f₁) = 1, R_p(f₂) = 10, R_p(f₃) = 3.

R_f(λx, y → x + y) = 0(4!)⁰ + 1(4!)¹ + 10(4!)² + 3(4!)³ = 0 + 24 + 5760 + 41472 = 47256

For my function-space exploration, I simply reversed this process for each number to generate the truth table, and I used the truth table to test for the properties I was looking for.  However, for the fun of it, here is how you would apply the function to a set of values.  Given the function above, you would apply it to the values 2 and 3 as follows:

R_p(f₂) = floor(R_f(f) / (4!)²) % 4! =  floor(47256 / 576) % 4 = 10

f_2:0(0) = floor(4! R_p(f₂) / 4!) % 4 = 2, therefore f₂(0) = 2 (i.e. zero-indexed value 2 from [0, 1, 2, 3])

f_2:1(1) = floor(3! R_p(f₂) / 4!) % 3 =  2, therefore f₂(1) = 3 (i.e. zero-indexed value 2 from [0, 1, 3])

f_2:2(2) = floor(2! R_p(f₂) / 4!) % 2 =  0, therefore f₂(2) = 0 (i.e. zero-indexed value 0 from [0, 1])

f_2:3(3) = floor(1! R_p(f₂) / 4!) % 1 =  0, therefore f₂(3) = 1 (i.e. zero-indexed value 0 from [1])

So 2 + 3 (modulo 4) = 1.

The looooooong way.

Representing functions with numbers

In my last hurried post, I mentioned that I carried out a brute-force exploration of the function-space I was looking at, looking for functions with certain properties. I'm sure the technique I used is well-known, and there are probably better ways to do it, but I thought I would describe what I did anyway.

The functions I was looking at were invertible, so if there was a function f (a, b), then there had to exist another function g (a, c) such that g (a, f (a, b)) = b. In this case, all values are drawn from the set N.

Because of the invertibility requirement, we can say that any function f_a (b) = f (a, b) is a permutation of |N| values, so the number of distinct functions f_a is |N|!.  If we think of f (a, b) as selecting a function f_a from a table of values using the index a and applying that function to the value b, then the number of distinct tables of |N| functions drawn from a set of size |N|! is (|N|!)^|N|.

That means for |N| = 4, for example, I needed to check (4!)⁴ = 331776 functions for those that had the additional commutative property I was looking for.

In order to check all of the functions exhaustively, I came up with a 1:1 relationship between every number in [0..331775] and every function in the set. Then I iterated through each number, generated the function from the number, and tested the function for the property I was looking for.

But parenting duties call again, so I'll have to finish this later.

Functions with certain properties

I've been trying to figure out the general answer to this question. It seems like I should be able to sort it out, but I've just got a mental block.

For a set of values N, how many functions f exist, such that the following are true? (Forgive me if I make mistakes with the notation...I'm not a mathematician.)

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

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

where a, b, c ← N

I've been able to determine the answer through brute-force exploration of the function space for the following sizes of N:

For |N| = 2, there are 2 functions with these properties.

For |N| = 3, there are 6 functions with these properties.

For |N| = 4, there are 96 functions with these properties.

It seems like it ought to be easy to say, for a given size |N|, how many of these functions there are. But I can't see it yet.

Note 12/3/2013: I figured it out.