**3. Reader-friendly explanation of the VMPC one-way function**

The name of the function is an abbreviation of
*Variably Modified Permutation Composition*.
Its popular definition is F(F(F(x))+1)
The idea of the VMPC function
**F(F(F(x))+1)**
is best illustrated when compared to a "standard" function **F(F(F(x)))**.

**Formally** 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.
This took me over 14 years from publishing the function at the FSE 2004 conference in India.
And I am **almost** done.

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^{78}, which is a "1" followed by 78 zeros.
Or in other words over a trillion trillions trillions trillions trillions trillions operations.