![]()
| |||||
|
Formalna definicja funkcji VMPC i problemu jej odwracania
VMPC to skrót od Variably Modified Permutation Composition
(Zmiennie Modyfikowane Złożenie Permutacji).*1
Co to znaczy, że funkcja jest jednokierunkowa? Ogólnie - jej odwrócenie,
a więc znalezienie argumentów (permutacji P) na podstawie wartości (permutacji V),
jest obliczeniowo niewykonalne.
K=N! / (N*0,875)! Powtórzmy, jest to wzór przybliżony, który oddaje istotę zjawiska i rząd wielkości liczby K. Wzór jest określony dla N podzielnych przez 8.![]() Jednokierunkowość funkcji precyzyjniej definiujemy następująco: Funkcja VMPC byłaby jednokierunkowa, gdyby średnia ilość obliczeń niezbędna do odtworzenia N-elementowej losowo wybranej permutacji P na podstawie permutacji V była niewielomianowym przekształceniem liczby N. Obrazowo - przekształcenie niewielomianowe to takie, którego wartości gwałtownie rosną. Intuicyjnie sens definicji jest taki, że funkcja jednokierunkowa to taka, której trudność odwrócenia (mierzona ilością obliczeń) rośnie gwałtownie (niewielomianowo) ze wzrostem wielkości zadania (u nas - ze wzrostem rozmiaru permutacji P mierzonego liczbą N). Gdyby odwrócenie funkcji wymagało średnio np. N100 obliczeń, to mimo że jest to liczba ogromna, funkcja taka nie byłaby jednokierunkowa, gdyż N100 jest przekształceniem wielomianowym. Dopiero gdyby odwrócenie funkcji wymagało średnio np. 2N albo N! obliczeń, funkcja taka byłaby jednokierunkowa, bowiem funkcja potęgowa (2N) czy silnia (N!) są przekształceniami niewielomianowymi. Zawsze da się znaleźć odpowiednio duże N, dla którego wartość przekształcenia niewielomianowego (np. N!) jest większa niż wartość przekształcenia wielomianowego Na. ![]() Szacowana średnia ilość obliczeń niezbędna do odwrócenia funkcji VMPC K=N!/(N*0,875)! jest przekształceniem niewielomianowym. Aby to zilustrować, porównajmy jego wartości z wartościami przykładowego wielomianowego przekształcenia Y=N100. Wzór K=N! / (N*0,875)! opisuje iloczyn N/8 kolejnych liczb: N*(N-1)*(N-2)*...*(N*7/8+1). Dla małych N liczba Y będzie znacznie większa od K: Dla N=16 mamy: Y=16100=10120,4, natomiast K=16!/14!=16*15=240 Wartość Y to ponad 1 i 120 zer, a nasze "wielkie niewielomianowe" K ma wartość zaledwie 240. Zwiększmy jednak N:Dla N=808 mamy: Y=808100=10290,7, natomiast K=808!/707!=808*807*...*708=10290,8 Dla N=808 wartość K=10290,8, która jest tu iloczynem 101 liczb, przewyższyła już wartość Y=10290,7 (będącą zawsze iloczynem 100 liczb). Jeśli zwiększymy N jeszcze bardziej:Dla N=1000 mamy: Y=1000100=10300, natomiast K=1000!/875!=1000*999*...*876=10371,4 Dla N=1000 wartość K jest już 1071,4 (ponad sto biliardów kwadryliardów kwadryliardów) razy większa niż Y. K jest tu iloczynem 125 liczb, a Y wciąż pozostaje iloczynem 100 liczb. Niewielomianowa wartość K będzie się coraz bardziej oddalać od wielomianowego Y dla coraz większych N.![]() Wyniki symulacji odwracania funkcji VMPC wykonanych przy pomocy różnych algorytmów ostatecznie prowadzą do takich samych wyników, zaprezentowanych w tabeli poniżej. Tabela pokazuje ilości elementów permutacji P, których zgadnięcie jest konieczne, oraz wynikające z nich średnie ilości obliczeń niezbędne do odwrócenia funkcji VMPC dla kilku przykładowych rozmiarów permutacji:
Średnie ilości obliczeń wynikające z symulacji (kolumna L w tabeli) są nieco większe od wartości szacowanych niewielomianowym wzorem K=N! / (N*0,875)!. Wynika to z faktu, że wzór nie uwzględnia pierwszych dwóch zgadywanych elementów P (np. dla N=8 wzór zwraca wartość K=8, co odpowiada jednemu zgadywanemu elementowi, podczas gdy wg symulacji dla N=8 zgadywane są 3 elementy P). W wyniku tego uproszczenia wzór ma klarowniejszą postać, a odwrócenie funkcji jest jeszcze trudniejsze niż wzór podaje. ![]() Obecne badania są bardzo blisko osiągnięcia ostatecznego celu, którym jest udowodnienie, że funkcja VMPC jest jednokierunkowa. Dowód będzie stwierdzał, że średnia ilość obliczeń niezbędna do odwrócenia funkcji VMPC jest niewielomianowym przekształceniem liczby N bez względu na zastosowany algorytm odwracania funkcji. Będzie to oznaczać rozwiązanie problemu "czy P=NP" przez wykazanie, że P ≠ NP, co jest konsekwencją istnienia funkcji jednokierunkowej. Jak dotąd nie jest bowiem znana na świecie żadna funkcja jednokierunkowa - taka, której jednokierunkowość byłaby udowodniona, a nie tylko domniemana. Funkcja VMPC byłaby pierwszą taką funkcją. ![]() *1. Skąd pochodzi nazwa funkcji VMPC - Variably Modified Permutation Composition (Zmiennie Modyfikowane Złożenie Permutacji)?
|
|
||||||||||||||||||||||||||||||||||||||||||
Copyright © 1999-2017 by Bartosz Żółtak & OHTON EXPO
Okna Wrocław
Aktualizacja: 16.04.2018 |