Odwracanie funkcji VMPC
(nieformalna ilustracja na przykładzie)

Tu możesz zobaczyć, jak przebiega obliczanie wartości funkcji VMPC

Co właściwie oznacza, że funkcja jest jednokierunkowa?

Spójrzmy na funkcję "+1". Znając jej wartość (np. 8), wiemy, że argumentem było 7 (bo 7+1=8).

Funkcję "+1" łatwo jest odwrócić, a więc znaleźć argument (7) na podstawie wartości (8).

Funkcja jednokierunkowa to taka, której nie da się łatwo odwrócić, a więc
znając wartość funkcji jednokierunkowej trudno jest znaleźć argument, z którego wartość ta powstała.

Jak dotąd na świecie nie jest znana żadna funkcja, której jednokierunkowość byłaby udowodniona.

VMPC ma szansę być pierwszą taką funkcją.



Aby dostrzec, dlaczego funkcja VMPC f(f(f(x))+1) jest trudna do odwrócenia,
zobaczmy najpierw, jak łatwo można odwrócić funkcję f(f(f(x))).

Przypomnijmy, jak pary wyznaczały wartości funkcji f(f(f(x))):



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

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



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

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



Zauważmy, że pary (2:6)(6:3) są wspólne - wystąpiły w obydwu wartościach: f(f(f(1))) oraz f(f(f(2))).

Czy to przypadek?
Zbierzmy wszystkie siedem wartości funkcji f(f(f(x))):

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



Pary w funkcji f(f(f(x))) układają się według schematu:

(X:A)(A:B)(B:Y)

Wynika z niego, że pary (A:B)(B:Y) z prawej strony wiersza (_:A)(A:B)(B:Y)
pojawią się również z lewej strony w wierszu (A:B)(B:Y)(Y:_).

Na przykład:
(1:2)(2:6)(6:3)
(2:6)(6:3)(3:7)

Własność ta pozwoli łatwo odwrócić funkcję f(f(f(x))).

Odwrócenie tej funkcji polega na odtworzeniu par mając dane wartości f(f(f(x)))=y.
Oznacza to uzupełnienie poniższego szablonu według schematu (X:A)(A:B)(B:Y):

(1:_)(_:_)(_:3)
(2:_)(_:_)(_:7)
(3:_)(_:_)(_:5)
(4:_)(_:_)(_:2)
(5:_)(_:_)(_:6)
(6:_)(_:_)(_:4)
(7:_)(_:_)(_:1)



Do dzieła! Przed nami 4 identyczne kroki.

  Załóżmy, że pierwszy wiersz jest nam już znany: (1:2)(2:6)(6:3).
Wiemy więc, że wiersz (2:_)(_:_)(_:7) ma postać (2:6)(6:3)(_:7).  
(ponieważ przenieśliśmy pary (2:6)(6:3) z prawej strony na lewą).

Znając schemat (X:A)(A:B)(B:Y) wiemy, że brakującą liczbą jest B=3: (2:6)(6:3)(3:7),
co ujawnia nową parę (3:7).



Znajdźmy kolejną parę - (7:4)

W poprzednim kroku odtworzyliśmy wiersz (2:6)(6:3)(3:7). 
  Wiemy więc, że wiersz (6:_)(_:_)(_:4) ma postać (6:3)(3:7)(_:4).

Według schematu (X:A)(A:B)(B:Y) brakującą liczbą jest B=7: (6:3)(3:7)(7:4), co ujawnia parę (7:4).



Teraz znajdźmy parę (4:5)

W poprzednim kroku odtworzyliśmy wiersz (6:3)(3:7)(7:4). 
  Wiemy więc, że wiersz (3:_)(_:_)(_:5) ma postać (3:7)(7:4)(4:5), co ujawnia parę (4:5).



A teraz znajdźmy parę (5:1)

W poprzednim kroku odtworzyliśmy wiersz (3:7)(7:4)(4:5). 
  Wiemy więc, że wiersz (7:_)(_:_)(_:1) ma postać (7:4)(4:5)(5:1), co ujawnia parę (5:1).



Gotowe!
Funkcja f(f(f(x))) została odwrócona.
Znaleźliśmy siedem par: (1:2), (2:6), (3:7), (4:5), (5:1), (6:3), (7:4),
które pasują do szablonu zgodnie ze schematem funkcji f(f(f(x))) - (X:A)(A:B)(B:Y):

(1:2)(2:6)(6:3)
(2:6)(6:3)(3:7)
(3:7)(7:4)(4:5)
(4:5)(5:1)(1:2)
(5:1)(1:2)(2:6)
(6:3)(3:7)(7:4)
(7:4)(4:5)(5:1)

Schemat funkcji f(f(f(x))) (X:A)(A:B)(B:Y) gwarantował nam, że dwie pary (w tym jedna nowo ujawniona) z jednego wiersza pojawią się wspólnie w innym wierszu ujawniając kolejną nową parę i tak wkoło aż do ujawnienia wszystkich par.

Gdyby liczb było o 100 więcej, kroków też by było o 100 więcej. Liczba operacji potrzebna do odwrócenia funkcji f(f(f(x))) rośnie liniowo - jedna dodatkowa operacja na każdą dodatkową liczbę.

Funkcja f(f(f(x))) jest więc łatwa do odwrócenia niezależnie od ilości liczb.^*1

[*1]  W pierwszym kroku założyliśmy, że znamy pierwszy wiersz (1:2)(2:6)(6:3). Oznacza to, że zgadliśmy w nim dwie pary (1:2) i (2:6), a trzecią parę (6:3) odczytaliśmy zgodnie ze schematem (X:A)(A:B)(B:Y). Istotą łatwości odwrócenia funkcji f(f(f(x))) jest fakt, że po zgadnięciu dwóch par możliwe jest odtworzenie wszystkich pozostałych par bez względu na ilość liczb w tabeli (zakładając, że liczby w tabeli tworzą permutację jednocyklową; jeśli cykli jest więcej, odwrócenie funkcji f(f(f(x))) jest tylko nieco trudniejsze). Przedstawiony tu sposób na odwracanie funkcji f(f(f(x))) został wybrany jako najlepiej oddający istotę jednokierunkowości funkcji VMPC f(f(f(x))+1).

Teraz spróbujmy odwrócić funkcję VMPC



Odwróciliśmy funkcję f(f(f(x))).
Zobaczmy teraz, dlaczego odwrócenie funkcji VMPC f(f(f(x))+1) jest trudne.

Czy dodanie liczby jeden (+1) może powodować skutki na miarę ilości atomów we Wszechświecie...?

Przypomnijmy, jak pary wyznaczały wartości funkcji VMPC f(f(f(x))+1):



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

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



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

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



Tylko jedna para (2:6) jest tu wspólna - wystąpiła w obydwu wartościach: f(f(f(1))+1) oraz f(f(f(2))+1).

Dlaczego tylko jedna?
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



Przypomnijmy, że pary w funkcji f(f(f(x))) układały się według schematu:

(X:A)(A:B)(B:Y)

Na przykład:
(1:2)(2:6)(6:3)
(2:6)(6:3)(3:7)

Pary (A:B)(B:Y) z prawej strony wiersza (_:A)(A:B)(B:Y)
pojawiały się również z lewej strony w wierszu (A:B)(B:Y)(Y:_).
Własność tę wykorzystaliśmy do szybkiego odwrócenia funkcji f(f(f(x))).



Ale w funkcji VMPC f(f(f(x))+1) pary układają się według innego schematu:

(X:A)(A:B)(B+1:Y)

Na przykład:
(1:2)(2:6)(7:4)
(2:6)(6:3)(4:5)

Wynika z niego, że pary (A:B)(B+1:Y) z prawej strony wiersza (_:A)(A:B)(B+1:Y) 
nigdy nie pojawią się z lewej strony w wierszu (A:B)(B:Y)(Y+1:_).

Oznacza to, że w funkcji VMPC dwa wiersze zwykle mogą mieć tylko jedną wspólną parę.

Własność ta jest źródłem jednokierunkowości funkcji VMPC,
a jest konsekwencją wystąpienia niewinnej jedynki w definicji funkcji VMPC f(f(f(x))+1).

Zobaczmy teraz, jak przebiega proces odwracania funkcji VMPC.
Odwrócenie tej funkcji polega na odtworzeniu par mając dane wartości f(f(f(x))+1)=y.
Oznacza to uzupełnienie poniższego szablonu według schematu (X:A)(A:B)(B+1:Y):

(1:_)(_:_)(_:4)
(2:_)(_:_)(_:5)
(3:_)(_:_)(_:1)
(4:_)(_:_)(_:6)
(5:_)(_:_)(_:7)
(6:_)(_:_)(_:2)
(7:_)(_:_)(_:3)




Spróbujmy znaleźć pierwszą parę (4:5)...


Spójrzmy jeszcze raz na wszystkie pary tworzące wartości funkcji VMPC:

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

Załóżmy, że pierwszy wiersz (1:2)(2:6)(7:4) jest nam już znany.
Spróbujmy znaleźć inny wiersz, który używa dwóch spośród par (1:2), (2:6), (7:4)...

Nie ma takiego!

Znaleźć możemy najwyżej wiersz, który używa jednej spośród naszych par, na przykład wiersz (2:6)(6:3)(4:5).

Podczas odwracania funkcji widzimy ten wiersz jako: (2:_)(_:_)(_:5).
Możemy wstawić do niego tylko jedną z naszych par - (2:6).
Zgodnie ze schematem (X:A)(A:B)(B+1:Y) wiersz przyjmie postać: (2:6)(6:_)(_:5).

Aby móc kontynuować, musimy zgadnąć, jaką postać ma para (6:_).
Zgadując mamy niewielkie szanse, że trafimy w prawidłową wartość...

Zgadnijmy prawidłowo: (6:3). Teraz wiersz przyjmuje postać (2:6)(6:3)(_:5).

Zgodnie ze schematem (X:A)(A:B)(B+1:Y) widzimy, że B=3, więc brakującą liczbą jest B+1=4
i wiersz ostatecznie przyjmuje postać (2:6)(6:3)(4:5), co ujawnia parę (4:5).

Znalezienie pary (4:5) kosztowało nas jednak zgadnięcie pary (6:3).



Znajdźmy teraz kolejną parę - (3:7)

W funkcji VMPC zwykle dopiero zestawienie par z dwóch różnych wierszy pozwala dobrać
dwie pary - tu (1:2), (6:3) - które występują wspólnie w którymś nowym wierszu - tu (6:3)(3:7)(1:2).

Z poprzedniego kroku znamy wiersze (1:2)(2:6)(7:4) oraz (2:6)(6:3)(4:5).
Dopiero teraz wiemy, że nowy wiersz (6:_)(_:_)(_:2) ma postać (6:3)(_:_)(1:2).

Możemy go uzupełnić według schematu (X:A)(A:B)(B+1:Y), widząc, że A=3 oraz B+1=1, więc B=7
(B=7, gdyż pamiętamy, że dodawanie wykonujemy modulo 8, więc zamiast 7+1=8 przyjmujemy 7+1=1).

Wiersz ostatecznie przyjmuje postać: (6:3)(3:7)(1:2), co ujawnia parę (3:7).



Znajdźmy ostatnią parę - (5:1)

Z poprzednich kroków znamy wiersze (1:2)(2:6)(7:4) oraz (6:3)(3:7)(1:2).
Wiemy więc, że nowy wiersz (3:_)(_:_)(_:1) ma postać (3:7)(7:4)(_:1).

Możemy go uzupełnić według schematu (X:A)(A:B)(B+1:Y), widząc, że B=4, zatem B+1=5.

Wiersz ostatecznie przyjmuje postać: (3:7)(7:4)(5:1), co ujawnia parę (5:1).



Gotowe!
Funkcja VMPC f(f(f(x))+1) została odwrócona, ale kosztowało nas to zgadnięcie pary (6:3).

Znaleźliśmy siedem par: (1:2), (2:6), (3:7), (4:5), (5:1), (6:3), (7:4),
które pasują do szablonu zgodnie ze schematem funkcji VMPC f(f(f(x))+1) - (X:A)(A:B)(B+1:Y):

(1:2)(2:6)(7:4)
(2:6)(6:3)(4:5)
(3:7)(7:4)(5:1)
(4:5)(5:1)(2:6)
(5:1)(1:2)(3:7)
(6:3)(3:7)(1:2)
(7:4)(4:5)(6:3)

Odwróciliśmy funkcję VMPC dla liczb 1..7 zgadując trzy pary: (1:2), (2:6) oraz (6:3).*1

Para (1:2) mogła przyjąć 7 postaci, para (2:6) - 6 postaci, a para (6:3) - 5 postaci.^*2

Mieliśmy zatem 7*6*5 = 210 możliwych kombinacji tych trzech par. Wiedzieliśmy, która jest prawidłowa, gdyż wcześniej sami wyliczyliśmy wartości funkcji, ale podczas prawdziwego odwracania funkcji nie wiemy, która z 210 kombinacji jest prawidłowa.

Cierpliwy człowiek poradziłby sobie jednak z przetestowaniem wszystkich 210 kombinacji.

Ale co by było, gdyby liczb było nie 7, a 15? Wówczas nawet po zgadnięciu jednej pary nie można kontynuować odwracania funkcji. Wciąż nie można bowiem łatwo znaleźć dwóch par występujących wspólnie w nowym wierszu. Niezbędne jest zgadnięcie jeszcze jednej pary.

Pierwsza zgadywana para może mieć 15 postaci, druga 14, trzecia 13, czwarta 12. Wszystkich kombinacji jest więc 15*14*13*12 = 32.760.

Jeśli zwiększymy rozmiar tabeli o kolejne 8 liczb, do 23, zgadnąć będzie trzeba już 5 par. Liczba ich kombinacji wyniesie 23*22*21*20*19 = 4.037.880.

4 miliony operacji to spore wyzwanie dla człowieka, ale komputerowi wciąż zajmie tylko chwilę.

A jeśli w tabeli będzie 100 liczb? Aby odwrócić funkcję VMPC, zgadnąć będzie trzeba 14 par. Ilość ich kombinacji wyniesie 100*99*98*97*96*95*94*93*92*91*90*89*88*87 = 3.852.142.155.961.424.437.432.320.000, czyli ponad 3 kwadryliardy^*3. To ponad trzy miliardy miliardów miliardów albo ponad 3-krotność liczby 1 i 27 zer.

Ta liczba na długi czas zajęłaby największe superkomputery świata.

Jeśli więc potasujemy 100 kart do gry, następnie przemieszamy je funkcją VMPC, to odtworzenie pierwotnej kolejności kart zajmie ponad 3 kwadryliardy operacji.

Trudność odwrócenia funkcji VMPC rośnie w nieskończoność: na każde osiem nowych liczb przybywa jedna zgadywana para^*4.

Gdyby w tabeli było 1000 liczb, mielibyśmy 127 par do zgadnięcia. Pary te mogą utworzyć 1000*999*998*...*874 = 10³⁷⁷ kombinacji, czyli 1 i 377 zer. To kwadryliardy kwadryliardów razy więcej niż prawdopodobna ilość atomów we Wszechświecie, szacowana na około 10¹⁰⁰.

A to wszystko przez niewinną jedynkę w definicji funkcji VMPC f(f(f(x))+1).







[*1]  W pierwszym kroku założyliśmy, że znamy pierwszy wiersz (1:2)(2:6)(7:4). Oznacza to, że zgadliśmy w nim dwie pary (1:2) i (2:6), a trzecią parę (7:4) odczytaliśmy zgodnie ze schematem (X:A)(A:B)(B+1:Y).


[*2]  W wierszu (1:2)(2:6)(7:4) para (1:2) mogła przyjąć 7 postaci: (1:1), (1:2), (1:3), (1:4), (1:5), (1:6), (1:7).
Para (2:6) mogła mieć 6 postaci: (2:1), (2:2). (2:3), (2:4), (2:5), (2:6), (2:7). Postać (2:2), czyli f(2)=2, byłaby sprzeczna z parą (1:2), czyli f(1)=2 (każdy element f musi mieć inną wartość, ponieważ f jest permutacją).
Para (7:4) została ujawniona zgodnie ze schematem (X:A)(A:B)(B+1:Y).
Para (6:3) mogła przyjąć którąś z 4 postaci niesprzecznych z poprzednimi trzema parami - (1:2), (2:6), (7:4) - czyli: (6:1), (6:3), (6:5), (6:7). Ogólnie - liczba możliwych postaci nowej pary maleje o 1 z każdą ujawnioną parą, co wynika z faktu, że f jest permutacją. Zjawisko zostało tu uproszczone dla klarowniejszego przedstawienia istoty funkcji VMPC i przyjęto, że para (6:3) miała 5 (a nie 4) możliwych postaci. Uproszczenie to nie wpływa w znaczący sposób na zilustrowaną trudność odwrócenia funkcji VMPC. Zjawisko to jest uwzględnione bez uproszczeń dopiero w badaniach naukowych.


[*3]  kwadryliard to 10²⁷, czyli 1 i 27 zer.


[*4]  Dla wnikliwych. W funkcji VMPC mogą wystąpić sytuacje, w których dwie pary użyte w jednym wierszu występują wspólnie w innym wierszu, np. (2:6)(6:3)(4:5) oraz (4:5)(5:1)(2:6). Sytuacje takie ułatwiają odwracanie funkcji poprzez ujawnienie jednej nowej pary bez konieczności zgadywania innej. Jednak o ile występowanie takich sytuacji w funkcji f(f(f(x))) było gwarantowane, co pozwoliło na łatwe jej odwrócenie, o tyle w funkcji VMPC sytuacje takie występują tylko przypadkowo i sporadycznie. Nie wpływają one w znaczący sposób na zilustrowaną trudność odwrócenia funkcji VMPC. Zostały tu pominięte, aby umożliwić klarowniejsze przedstawienie istoty funkcji VMPC. Sytuacje te są uwzględnione dopiero w badaniach naukowych.

Zobacz formalną definicję funkcji VMPC i problemu jej odwracania