"p vs np"被認為是計算機科學領域最為重要的未解決的問題，克雷數學研究所也將這個問題列為7個千禧年數學難題之一，可見其在計算機科學和數學領域的重要性和難度，不過，P與NP這個命題為何重要，《可能與不可能的邊界：P/NP問題趣史》一書就以科普的筆法講清了P/NP問題的歷史、現實意義，普通小白讀完這本書應該也能弄懂它的含義，近年來，也不斷有人站出來號稱自己證明了p != np或者p = np，然而結論最終都經不起審核或推敲，在我看來，無論是p != np或p = np，要想完整給出結論，必然需要構造一個特定的演算法才行，也即數學里講到的構造性證明（一切非構造性的證明都是耍流氓），比如你想證明p=np，你得構造出一個特定的演算法將某一個NPC問題歸約為P的問題；如果你想證明p!=np，你也得構造出一個問題，且能夠證明該問題不能在多項式時間內找到問題的解，最近，筆者在researchgate上找到一篇名為《Eagle: A new symmetric encryption algorithm against any linear attacks and differential attacks (The existence of one-way function means P!=NP)》的文章，在文中，作者首先構造了一種加密演算法，其特征在于給定任何的明文-密文對，密鑰空間中的任意密鑰，都能找到合理的加密、解密方式，這就相當于，任何的鑰匙都能開鎖，從而攻擊者根本就沒有任何辦法找到正確的鑰匙（密鑰），這一點跟我們現在通常所使用的對稱加密演算法的機制有著本質的區別，如AES、DES等，只要明文-密文對一旦確定，密鑰是唯一確定的（只是確定密鑰在經驗上是非常困難的，目前還沒有辦法在理論上證明它是困難的），攻擊者難于破解的秘訣就在于密碼學中常用的兩大技巧（擴散與混淆）的使用，事實上，線性攻擊、差分攻擊等攻擊方式還是對這種加密機制構成了威脅，而在上面的文章中，作者所構造的加密機制，引入了不可見引數，僅根據明文-密文對，滿足加密條件的密鑰為整個密鑰空間，也就是說，對于某確定的明文，用確定的密鑰加密后的密文表現出完全隨機的性質；并且用任意不同的密鑰加密，也有可能得到相同的密文，這一特征與現有的分組加密機制是根本上不同的，且這一特征能在本質上消除線性攻擊和差分攻擊對于這種加密機制的威脅，在文章的最后，作者構造了一種難以破解的加密機制，并在理論上證明了其滿足單向函式的性質，也即證明了不能在多項式時間內找到密鑰，但是驗證一個密鑰的正確性卻是多項式時間復雜度的，從而根據“單向函式存在即p!=np”這一經典結論，也就證明了p不等于np，根據我的經驗，作者的整個加密演算法的構造程序是巧妙的，且結論是正確的，關于最后單向函式的構造也是合理的，從而我更相信，這次應該是真的證明了p!=np，https://www.researchgate.net/publication/348992129_Eagle_A_new_symmetric_encryption_algorithm_against_any_linear_attacks_and_differential_attacks_The_existence_of_one-way_function_means_PNP
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/264481.html
標籤：其他
上一篇：歡迎進入四年IT夢回首的脫發空間