Obliczanie wartości funkcji VMPC
(nieformalna ilustracja na przykładzie)

Tu możesz zobaczyć, jak przebiega odwracanie funkcji VMPC

Niech f oznacza 7-elementową permutację.
Mówiąc obrazowo, permutacja to ciąg kolejnych, ale potasowanych liczb.
Przykładowo:  f(1)=2,  f(2)=6,  f(3)=7,  f(4)=5,  f(5)=1,  f(6)=3,  f(7)=4,
co czytamy: "f od 1 równa się 2",  "f od 2 równa się 6", itd.

Funkcja VMPC przekształca dowolną permutację f w inną permutację g, określoną wzorem g(x)=f(f(f(x))+1), w omawianym przykładzie dla x=1,2,3,4,5,6,7.

Funkcję VMPC możemy obliczyć dla permutacji dowolnej wielkości. Permutacja może zatem mieć 7 elementów (jak tu), ale także np. 15 czy milion elementów.

Istotą funkcji VMPC jest fakt, że trudność jej odwrócenia, czyli znalezienia permutacji f na podstawie permutacji g, rośnie gwałtownie (niewielomianowo) wraz ze wzrostem wielkości permutacji. Podczas gdy dla 10-elementowej permutacji domowy komputer odwróci funkcję VMPC w mgnieniu oka, to dla 100-elementowej permutacji zajęłoby mu to już ponad 10 miliardów lat.

Istotę funkcji VMPC f(f(f(x))+1) najłatwiej dostrzec, gdy porównamy ją z funkcją f(f(f(x))).

Rysunek poniżej ilustruje funkcję f(f(f(x))) dla liczby x=1:

Na górze mamy kolejne liczby: 1 2 3 4 5 6 7.
Na dole te same liczby są potasowane: 2 6 7 5 1 3 4.

Linia pionowa | łączy w parę liczbę na górze z liczbą pod nią, np. (1:2).
Linia ukośna / łączy liczbę na górze z taką samą liczbą na dole, np. (2/2).

Aby obliczyć wartość funkcji, wystarczy podążać za niebieską linią.

Zaczynamy od liczby 1 na górze. Pod 1 leży 2.
Idziemy ukośną linią / do liczby 2 na górze. Pod 2 leży 6.
Idziemy ukośną linią / do liczby 6 na górze. Pod 6 leży 3.

I to już koniec! Funkcja f(f(f(x))) dla liczby x=1 ma wartość 3.



A teraz zobaczmy na funkcję VMPC f(f(f(x))+1) dla liczby x=1:

Pierwsze kroki są identyczne:
Zaczynamy od liczby 1 na górze. Pod 1 leży 2.
Idziemy ukośną linią / do liczby 2 na górze. Pod 2 leży 6.
Idziemy ukośną linią / do liczby 6 na górze...

Tu następuje różnica. Pojawia się jedynka, która jest istotą funkcji VMPC f(f(f(x))+1).
Do 6 dodajemy 1. Otrzymujemy 7. Pod 7 leży 4.

Gotowe! Funkcja VMPC f(f(f(x))+1) dla liczby x=1 ma wartość 4.



I to już wszystko! To jest cała funkcja VMPC.

Dalsze obliczenia są analogiczne, a niezwykłe własności funkcji są tylko konsekwencją tej niepozornej jedynki.





Obliczmy wartość funkcji f(f(f(x))) dla liczby x=2:

       Zaczynamy od liczby 2 na górze. Pod 2 leży 6, czyli (2:6).
Idziemy ukośną linią / do 6 na górze. Pod 6 leży 3, czyli (6:3).
Idziemy ukośną linią \ do 3 na górze. Pod 3 leży 7, czyli (3:7).

Pary (2:6)(6:3)(3:7) wyznaczyły, że funkcja f(f(f(x))) dla liczby x=2 ma wartość 7, czyli f(f(f(2)))=7.



A teraz obliczmy wartość funkcji VMPC f(f(f(x))+1) dla liczby x=2:

       Zaczynamy od liczby 2 na górze. Pod 2 leży 6, czyli (2:6).
Idziemy ukośną linią / do 6 na górze. Pod 6 leży 3, czyli (6:3).
Idziemy ukośną linią \ do 3 na górze...

Do 3 dodajemy 1. Otrzymujemy 4. Pod 4 leży 5, czyli (4:5).

Pary (2:6)(6:3)(4:5) wyznaczyły, że funkcja VMPC f(f(f(x))+1) dla liczby x=2 ma wartość 5, czyli f(f(f(2))+1)=5.





Funkcja f(f(f(x))) dla liczby x=3:

Pary (3:7)(7:4)(4:5) wyznaczyły, że f(f(f(3)))=5.



Funkcja VMPC f(f(f(x))+1) dla liczby x=3:

Pary (3:7)(7:4)(5:1) wyznaczyły, że VMPC f(f(f(3))+1)=1.





Funkcja f(f(f(x))) dla liczby x=4:

Pary (4:5)(5:1)(1:2) wyznaczyły, że f(f(f(4)))=2.



Funkcja VMPC f(f(f(x))+1) dla liczby x=4:

Pary (4:5)(5:1)(2:6) wyznaczyły, że VMPC f(f(f(4))+1)=6.





Funkcja f(f(f(x))) dla liczby x=5:

Pary (5:1)(1:2)(2:6) wyznaczyły, że f(f(f(5)))=6.



Funkcja VMPC f(f(f(x))+1) dla liczby x=5:

Pary (5:1)(1:2)(3:7) wyznaczyły, że VMPC f(f(f(5))+1)=7.





Funkcja f(f(f(x))) dla liczby x=6:

Pary (6:3)(3:7)(7:4) wyznaczyły, że f(f(f(6)))=4.



Funkcja VMPC f(f(f(x))+1) dla liczby x=6:

7+1=8. Ale w tabeli mamy liczby od 1 do 7. Co zrobić?
Dodawanie faktycznie odbywa się "modulo 8", co oznacza, że zamiast liczby 8 przyjmujemy liczbę 1.

Pary (6:3)(3:7)(1:2) wyznaczyły, że VMPC f(f(f(6))+1)=2.





Funkcja f(f(f(x))) dla liczby x=7:

Pary (7:4)(4:5)(5:1) wyznaczyły, że f(f(f(7)))=1.



Funkcja VMPC f(f(f(x))+1) dla liczby x=7:

Pary (7:4)(4:5)(6:3) wyznaczyły, że VMPC f(f(f(7))+1)=3.





Zbierzmy wszystkie siedem wartości funkcji f(f(f(x))), które obliczyliśmy:

Pary (1:2)(2:6)(6:3) wyznaczyły, że f(f(f(1)))=3
Pary (2:6)(6:3)(3:7) wyznaczyły, że f(f(f(2)))=7
Pary (3:7)(7:4)(4:5) wyznaczyły, że f(f(f(3)))=5
Pary (4:5)(5:1)(1:2) wyznaczyły, że f(f(f(4)))=2
Pary (5:1)(1:2)(2:6) wyznaczyły, że f(f(f(5)))=6
Pary (6:3)(3:7)(7:4) wyznaczyły, że f(f(f(6)))=4
Pary (7:4)(4:5)(5:1) wyznaczyły, że f(f(f(7)))=1




A tu zbierzmy wszystkie siedem wartości funkcji VMPC f(f(f(x))+1):

Pary (1:2)(2:6)(7:4) wyznaczyły, że f(f(f(1))+1)=4
Pary (2:6)(6:3)(4:5) wyznaczyły, że f(f(f(2))+1)=5
Pary (3:7)(7:4)(5:1) wyznaczyły, że f(f(f(3))+1)=1
Pary (4:5)(5:1)(2:6) wyznaczyły, że f(f(f(4))+1)=6
Pary (5:1)(1:2)(3:7) wyznaczyły, że f(f(f(5))+1)=7
Pary (6:3)(3:7)(1:2) wyznaczyły, że f(f(f(6))+1)=2
Pary (7:4)(4:5)(6:3) wyznaczyły, że f(f(f(7))+1)=3




Zobacz teraz, jak przebiega odwracanie funkcji VMPC