Computing the value of the VMPC function

This description is intended to be intelligible for readers without mathematical background.

The idea of the VMPC function F(F(F(x))+1) is best illustrated when compared to a "standard" function F(F(F(x))).

Please, don't get scared if you are not a mathematician! It's just reading numbers and following the blue line. Nothing more.
Give it a shot and believe me, you will have fun!

Formally (if you are not a mathematician, simply ignore this) the diagram contains some permutation F in two-line notation.

Let's see how F(F(F(1))) is evaluated:


Following the blue line we read from the diagram that:
(1 2) (below number 1 lies number 2, formally F(1)=2)
(2 6) (below number 2 lies number 6, formally F(2)=6)
(6 3) (below number 6 lies number 3, formally F(6)=3)
And that's it!
we have just evaluated that F(F(F(1)))=3.

Now, by contrast, let's see how the VMPC function F(F(F(1))+1) is evaluated:


Just like above, following the blue line, we read from the diagram that
(1 2) (below number 1 lies number 2, formally F(1)=2)
(2 6) (below number 2 lies number 6, formally F(2)=6)

And here comes the tricky part, which is the essence of the VMPC function:

We increase 6 by 1. We get 6 + 1 = 7.

Only now do we check in the diagram that
(7 4) (below number 7 lies number 4, formally F(7)=4)

And so we get the value of the VMPC function: F(F(F(1))+1)=4.

And that's about it! Simple, isn't it?
All about the VMPC function is just to add 1 at the right place! Nothing more!

What is astounding or almost magical, are the consequences of this innocent +1 operation.

Normally each function has its inverse. For example, if we add 10 + 5 = 15, then to get back from 15 to 10, we need to just subtract 15 - 5 = 10. Subtraction is the inverse of addition. However the VMPC function appears to be the first function in the world which has no inverse!

It means that if we hide the numbers in the bottom row of the diagram, we cannot recover them from the values of the VMPC function! Even despite the fact that these values are so easy to evaluate!

The cool part is that to actually understand why it happens, you still don't need to be a mathematician! It is so simple! So I hope you will follow up reading!

The hard part was to prove it formally. And this took me over 14 years from publishing the function at the FSE 2004 conference in India. And I am almost done.

By the way if you are here, you have already mastered permutations and permutation compositions! Maths isn't so scary, is it? :-)

Let's first evaluate all the remaining values, just like we did above by following the blue line.

Let's evaluate F(F(F(2)))


Following the blue line we read from the diagram that:
(2 6) (below number 2 lies number 6, formally F(2)=6)
(6 3) (below number 6 lies number 3, formally F(6)=3)
(3 7) (below number 3 lies number 7, formally F(3)=7)
We have just evaluated that
F(F(F(2)))=7

And now let's evaluate VMPC: F(F(F(2))+1)


(2 6) (below number 2 lies number 6, formally F(2)=6)
(6 3) (below number 6 lies number 3, formally F(6)=3)
The VMPC trick: 3 + 1 = 4
(4 5) (below number 4 lies number 5, formally F(4)=5)

We get the value of the VMPC function: F(F(F(2))+1)=5

Let's evaluate F(F(F(3)))


(3 7), formally F(3)=7
(7 4), formally F(7)=4
(4 5), formally F(4)=5

So we get F(F(F(3)))=5

And now VMPC: F(F(F(3))+1)


(3 7), formally F(3)=7
(7 4), formally F(7)=4
VMPC trick: 4 + 1 = 5
(5 1), formally F(5)=1

We get another VMPC value: F(F(F(3))+1)=1

Let's evaluate F(F(F(4)))


(4 5), formally F(4)=5
(5 1), formally F(5)=1
(1 2), formally F(1)=2

So we get F(F(F(4)))=2

And now VMPC: F(F(F(4))+1)


(4 5), formally F(4)=5
(5 1), formally F(5)=1
VMPC trick: 1 + 1 = 2
(2 6), formally F(2)=6

We get another VMPC value: F(F(F(4))+1)=6

Let's evaluate F(F(F(5)))


(5 1), formally F(5)=1
(1 2), formally F(1)=2
(2 6), formally F(2)=6

So we get F(F(F(5)))=6

And now VMPC: F(F(F(5))+1)


(5 1), formally F(5)=1
(1 2), formally F(1)=2
VMPC trick: 2 + 1 = 3
(3 7), formally F(3)=7

We get another VMPC value: F(F(F(5))+1)=7

Let's evaluate F(F(F(6)))


(6 3), formally F(6)=3
(3 7), formally F(3)=7
(7 4), formally F(7)=4

So we get F(F(F(6)))=4

And now VMPC: F(F(F(6))+1)


(6 3), formally F(6)=3
(3 7), formally F(3)=7
VMPC trick: 7 + 1 = 8 = 1
We got an 8, but we only use numbers from 1 to 7, so we reset this 8 into 1 (analogously to addition modulo 8).
(1 2), formally F(1)=2

We get another VMPC value: F(F(F(6))+1)=2

Let's evaluate F(F(F(7)))


(7 4), formally F(7)=4
(4 5), formally F(4)=5
(5 1), formally F(5)=1

So we get F(F(F(7)))=1

And now VMPC: F(F(F(7))+1)


(7 4), formally F(7)=4
(4 5), formally F(4)=5
VMPC trick: 5 + 1 = 6
(6 3), formally F(6)=3

We get another VMPC value: F(F(F(7))+1)=3

Now let's collect all the 7 values of F(F(F(x))) which we have just evaluated above

(1 2)(2 6)(6 3) determined that F(F(F(1)))=3
(2 6)(6 3)(3 7) determined that F(F(F(2)))=7
(3 7)(7 4)(4 5) determined that F(F(F(3)))=5
(4 5)(5 1)(1 2) determined that F(F(F(4)))=2
(5 1)(1 2)(2 6) determined that F(F(F(5)))=6
(6 3)(3 7)(7 4) determined that F(F(F(6)))=4
(7 4)(4 5)(5 1) determined that F(F(F(7)))=1

Look closer at all the pairs of numbers on the left, like (1 2)(2 6)(6 3). You might notice that when we take the 2 leftmost pairs, (1 2)(2 6), then we can find those exactly pairs, as 2 rightmost pairs in some other row! Here in row 5: (5 1)(1 2)(2 6).

You can try to do the same with any other row you like...

In fact, with the F(F(F(x))) function you can do it with any row you want! The 2 leftmost pairs will always fit as 2 rightmost pairs in some other row.

Both the 2 leftmost and the 2 rightmost pairs have the same general form (A B)(B C). That's why it is always possible to find two rows where the 2 leftmost pairs in one row are the same as the 2 rightmost pairs in the other row.

This enables to perform a deducing chain, where such pairs of rows are consecutively found revealing one new element of F at each step until the whole F is revealed (i.e. the F(F(F(x))) function is inverted).

Now let's try VMPC:

First, like above, let's collect all the 7 values of the VMPC function F(F(F(x))+1)

(1 2)(2 6)(7 4) determined that F(F(F(1))+1)=4
(2 6)(6 3)(4 5) determined that F(F(F(2))+1)=5
(3 7)(7 4)(5 1) determined that F(F(F(3))+1)=1
(4 5)(5 1)(2 6) determined that F(F(F(4))+1)=6
(5 1)(1 2)(3 7) determined that F(F(F(5))+1)=7
(6 3)(3 7)(1 2) determined that F(F(F(6))+1)=2
(7 4)(4 5)(6 3) determined that F(F(F(7))+1)=3


We can see that whichever row we take, the 2 leftmost pairs cannot be fitted as 2 rightmost pairs in any other row. This happens because of the "+1" operation. The 2 leftmost pairs take a general form (A B)(B C). The 2 rightmost pairs take a general form (A B)(B+1 C). And B+1 cannot be equal to B. Thus the 2 leftmost pairs can never become 2 rightmost pairs in any other row.

This simple fact has severe consequences for inverting the VMPC function. As a result of this fact it impossible to perform the deducing chain, as described above for the F(F(F(x))) function. In VMPC to achieve a situation where 2 given pairs occur in one row, we must usually take those pairs from 2 other different rows. This complicates the inverting process severely.

This simple to observe feature is the conceptual reason why VMPC has the "magical" power of being impossible to invert. Or in other words - one-way.

To invert VMPC, it is necessary to first guess about 1/8 of all the elements of F, plus 2 more. Only then is it possible to match the guessed pairs into some rows, deduce some new elements from these rows, match the deduced ones into further rows and so on until all the elements of F are recovered.

Guessing means searching through all the possible values of the guessed elements. For an example 16-element permutation this results in a computational effort of about 3000 operations. To really a lot. This number however grows rapidly as the size of the permutation increases. For a 32-element permutation it is about 17,000,000 operations. Inverting the VMPC function for a 256-element permutation is beyond the computational power of all the computers in the world combined. The number of operations to perform is about 10⁷⁸, which is a "1" followed by 78 zeros. Or in other words over a trillion trillions trillions trillions trillions trillions operations.

Permutation size	Number of guessed elements	Average number of operations
16	4	103
32	6	107
64	10	1016
128	18	1035
256	34	1078