27.11.2018







Projekt VMPC:


Badania nad funkcją VMPC i problemem matematycznym "czy P=NP?"
pieknafunkcja.pl



Aplikacja do szyfrowania danych VMPCrypt
szyfrowanie.com



Gra Permutu na bazie funkcji VMPC
permutu.pl







Zobacz także:


Gra komputerowa Urban



Multimedialne kursy do nauki języka angielskiego
ADL Publishing



Próbujemy rozwiązać wielką zagadkę matematyki:
projekt badawczy "Funkcja jednokierunkowa VMPC - czy P=NP?"


Jeśli czegoś nie da się zrobić, potrzebny jest ktoś, kto o tym nie wie i on to zrobi.
Albert Einstein.


Harmonogram projektu:

1. Praca została ukończona dnia 12 lipca 2016.
     Spisanie wyników na czysto zajęło półtora roku i 70 stron A4.
2. Dopracowanie szczegółów - do końca 2018 / początku 2019.
3. Publikacja w międzynarodowym czasopiśmie matematycznym - 2019.
4. Weryfikacja wyników przez Clay Mathematics Institute - 2021.

Nieformalny blog z przebiegu pisania pracy

Film z mojego wystąpienia na konferencji TEDx Wrocław 2015, gdzie przystępnym językiem opowiadam o projekcie:

Zagadnienie "czy P=NP?" jest jedną z największych nierozwiązanych zagadek matematyki. To pytanie, czy istnieje problem, którego rozwiązanie jest trudne do znalezienia, ale łatwe do zweryfikowania. Clay Mathematics Institute (USA) zaliczył ten problem jako jeden z siedmiu tzw. Problemów Milenijnych, a za rozwiązanie każdego z nich ufundował nagrodę w wysokości miliona dolarów.

Przez dziesięciolecia nie znaleziono żadnego takiego problemu. Ale i nie udowodniono, że nie istnieje.

Jednym ze sposobów na rozwiązanie zagadki jest odkrycie funkcji jednokierunkowej - przekształcenia, które jest łatwo wykonać, ale którego nie da się odwrócić. Innymi słowy, znając wartość funkcji, nie da się znaleźć liczby (ściślej - argumentu), z jakiego ta wartość powstała.

Otoczeni jesteśmy przez funkcje niejednokierunkowe. Dla przykładu - jak odwrócić funkcję +1? Jeśli nawet czytelnikowi, który nienawidzi matematyki, powiem, że wartość tej funkcji to 11, to i tak odejmie on jedynkę od 11 i uzyska prawidłowy wynik: 10. Wykorzystaliśmy tu (intuicyjnie) fakt, że odejmowanie jest funkcją odwrotną do dodawania. A teraz wyobraźmy sobie świat, gdzie po "dodaniu jedynki", nie jesteśmy w stanie potem tej jedynki odjąć... To jest właśnie świat funkcji jednokierunkowych.

Funkcja taka miałaby upragnioną cechę - rozwiązanie problemu (odwrócenie funkcji) byłoby trudne, ale zweryfikowanie rozwiązania (obliczenie wartości funkcji) byłoby łatwe. Istnienie takiej funkcji rozwiązałoby wprost problem "czy P=NP?" stwierdzeniem, że P ≠ NP.

Nie wiadomo jednak, czy funkcje jednokierunkowe w ogóle istnieją.

Dotychczas na świecie nie udowodniono jednokierunkowości żadnej funkcji. Niektóre funkcje (jak np. problem faktoryzacji liczb, będący fundamentem algorytmu szyfrowania RSA, stosowanego np. do podpisów cyfrowych) są uznawane za jednokierunkowe w praktyce - jeśli operują na gigantycznych liczbach, np. 100-cyfrowych - ale nawet wtedy nie ma formalnego dowodu ich jednokierunkowości.

W 1998 roku odkryłem nową funkcję matematyczną, którą nazwałem "VMPC". Zgodnie moją najlepszą wiedzą - jest ona właśnie funkcją jednokierunkową, której jednokierunkowość da się formalnie udowodnić.

W 2004 roku zostałem zaproszony do zaprezentowania funkcji VMPC na międzynarodowej konferencji kryptograficznej FSE w Indiach. Mój wyjazd na tę konferencję był współfinansowany przez Kancelarię Prezydenta Rzeczpospolitej Polskiej, Aleksandra Kwaśniewskiego oraz przez Prezydenta Wrocławia, Rafała Dutkiewicza.

Funkcja VMPC jest prostym przekształceniem permutacji wg następującego wzoru. Kluczowym jej elementem jest właśnie dodanie liczby 1, ale podczas składania permutacji (permutacja to tylko ciąg potasowanych liczb).

VMPC: f(f(f(x))+1)

Działanie funkcji VMPC można zilustrować na schemacie:





Od roku 2015 pracuję nad zapisaniem formalnego dowodu jednokierunkowości funkcji VMPC. Sam dowód tworzyłem na brudno w latach 2004-2015. Tak wygląda kompletny brudnopis zawierający wyniki mojej pracy. Nic wielkiego, ot słoik notatek:




Przełożenie tego na formalny język matematyki i zapisanie na czysto w pracy naukowej jest bardzo mozolnym i czasochłonnym zadaniem. Proces ten jest już jednak na ukończeniu. Praca na czysto ma obecnie ponad 70 stron A4. Zapisywanie głównego toku rozumowania zostało ukończone w połowie 2016. Od tamtego czasu trwa etap szlifowania pracy, którego dominującym elementem jest formalne uściślanie wszystkich użytych w dowodzie faktów dotyczących funkcji VMPC.

Tutaj można znaleźć prowadzony przeze mnie od 2015 roku

nieformalny blog z przebiegu pisania pracy.

Dowód opisuje szereg zjawisk kombinatorycznych wynikających z konstrukcji funkcji VMPC, które pozwalają wyznaczyć maksymalną wartość prawdopodobieństwa, z jakim dowolny algorytm odwrócić funkcję. Jednocześnie prawdopodobieństwo to jest ekstremalnie niskie (ściślej - jest niewielomianowe, zgodnie z wymogiem definicji funkcji jednokierunkowej).

Mówiąc ilustracyjnie, dowód określa maksymalną "wydajność" jakiegokolwiek algorytmu odwracania funkcji. Podobnie, jak nie możemy przekroczyć prędkości światła, tak żaden algorytm nie może odwrócić funkcji VMPC z wyższym prawdopodobieństwem niż to wykazane w dowodzie.

Dowód ten, jeśli zostanie uznany za prawidłowy, będzie oznaczał rozwiązanie problemu "czy P=NP" przez wykazanie, że P ≠ NP, co jest konsekwencją istnienia funkcji jednokierunkowej.

Funkcja VMPC byłaby pierwszą udowadnialną funkcją jednokierunkową na świecie, a rozwiązanie problemu "czy P=NP?" byłoby tylko (pozytywnym!) efektem ubocznym tego faktu.

Więcej szczegółów:



Jak przebiega obliczanie wartości funkcji VMPC

Jak przebiega odwracanie funkcji VMPC

Dla ekspertów: Formalna definicja funkcji VMPC i problemu jej odwracania



Dotychczasowe praktyczne zastosowania funkcji VMPC:

Funkcja VMPC leży u źródła całego projektu VMPC. Została zastosowana w Technologii Szyfrowania VMPC jako element algorytmu szyfrowania. Znalazła jednocześnie zastosowanie w aplikacji do szyfrowania danych VMPCrypt, która z tej Technologii korzysta. Na bazie funkcji VMPC powstała także gra Permutu. Mechanika gry w Permutu jest odzwierciedleniem procesu odwracania funkcji VMPC.



Jeśli chcesz, możesz wesprzeć badania:




Rejestrując aplikację
VMPCrypt
za dowolną kwotę
vmpcrypt.pl

Kupując grę
Permutu

permutu.pl

Kupując grę
komputerową Urban

permutu.pl/urban

Wdrażając Technologię Szyfrowania VMPC

szyfrowanie.com

Pomagasz w ten sposób wykonać o jeden mały krok więcej
w kierunku rozwiązania wielkiego problemu matematycznego "czy P=NP?".




FSE 2004
Publikacja na konferencji Międzynarodowego Stowarzyszenia Badań Kryptologicznych (IACR) FSE 2004


Konferencje Enigma
Publikacje na Krajowej Konferencji Zastosowań Kryptografii Enigma w Warszawie


WCTT
Nagroda Wrocławskiego Centrum Transferu Technologii przy Politechnice Wrocławskiej


Software Developer's Journal
Rekomendowany projekt magazynu Software Developer's Journal


Copyright © 1999-2018 by Bartosz Żółtak
Aktualizacja: 27.11.2018