摘要：介紹P vs.NP問(wèn)題的研究狀態(tài)以及P vs.NP問(wèn)題的研究對(duì)于密碼學(xué)的意義。主要內(nèi)容包括關(guān)于證明P≠NP的主要研究方法和相關(guān)工作，關(guān)于證明P=NP的主要研究方法和相關(guān)工作，關(guān)于求解NP完全問(wèn)題的相關(guān)方法，以及P vs.NP問(wèn)題研究與密碼學(xué)的關(guān)系。由于現(xiàn)代密碼學(xué)建立在未知密鑰情況下不存在有效的算法將明文消息從密文中提取出來(lái)的假定之上，因此安全加密算法存在的一個(gè)必要條件是P≠NP。如果P=NP，根據(jù)Cook的觀點(diǎn)，現(xiàn)代密碼體制將崩潰。依據(jù)P=NP的假定，給出一個(gè)可能的密碼分析模型。

關(guān)鍵詞：P vs.NP；密碼學(xué)；NP完全；計(jì)算復(fù)雜性；MSP

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A