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.

A few bits from the Rohonc Codex

Here, without any particular system of organization, are some suggested decipherments from the Rohonc Codex. (Note--I have updated this post with better images and added more discussion. As usual, the original was written late at night and I was very tired.)

I feel like the Rohonc Codex is a more "honest" text than the Voynich. For one thing, the scribe made mistakes in the RC, and struck through them or drew pictures over them. In the VM it seems there are no mistakes like this. The existence of a mistake implies a difference between correct and incorrect text, which lends weight to the idea that the text is not a hoax (since in a hoax there is no difference between correct and incorrect text).

In addition, the RC has apparent cultural features. It seems that all major figures depicted in the text can be identified based on their headgear, suggesting a tradition of stylized iconography. Christ can always be identified by his beard and striped turban, for example.

In some images, the figures are given names, which is where my suggested decipherments begin. Here is Jesus:

Jesus

This name is frequently followed, in the text, by another formula, which I think is probably Christ. For example, in the caption above an image of the Magi bearing gifts:

Jesus Christ

(Note 2/25/2014: Delia Huegel reads these characters the same way. See her post on Divine Designators.)

In one image, Jesus meets a seated figure wearing a crown who is mentioned frequently in the surrounding text. I think he may be Pontius Pilate:

Jesus and Pilate?

Pontius Pilate?

The reason I think this is Pilate is that they are surrounded by Roman soldiers (with pointed caps, as I mentioned in my first post), and the Pilate figure is seated on a throne with a crown. This individual is mentioned very frequently in some sections of the text, which makes me wonder if those portions aren't drawn from the apocryphal Acts of Pilate.

There are several depictions of the crucifixion, some of which show a board above Christ's head. In the images that I have, the board is difficult to read, but not impossible. Here are the best two:

INRI

Though the images here are not great, something bearing a strong resemblance to this formula can be found on a page where Pilate's name also appears frequently:

INRI in context with Pilate's name

What is interesting about the passage above is that it contains nearly the same text repeated twice, with apparent numbers before each repetition.

Is there a dialogue between Jesus and Pilate in the Acts of Pilate or Gospel of Nicodemus (or somewhere else) where Pilate asks Jesus more than once whether he is the King of the Jews? If so, that could be the underlying text here.

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.