現(xiàn)代密碼學第三講：復雜性理論.ppt
約21頁PPT格式手機打開展開
現(xiàn)代密碼學第三講：復雜性理論,本章主要內容問題的定義及分類算法復雜度定義及分類p問題和np問題規(guī)約思想與npc類密碼算法的計算安全性問題的定義及分類1 設a=(a1,a2,,an)是由n個不同的正整數(shù)構成的n元組，s是另一已知的正整數(shù). a稱為背包向量，s稱為背包容積. 求a中元素集合a’，使 .2設背包向量a=(1,2,5,10,20,50,10...
內容介紹
此文檔由會員 1406978338 發(fā)布
本章主要內容
問題的定義及分類
算法復雜度定義及分類
P問題和NP問題
規(guī)約思想與NPC類
密碼算法的計算安全性
問題的定義及分類
1 設A=(a1,a2,…,an)是由n個不同的正整數(shù)構成的n元組，S是另一已知的正整數(shù). A稱為背包向量，S稱為背包容積. 求A中元素集合A’，使 .
2 設背包向量A=(1,2,5,10,20,50,100), 背包容積為177，求向量 ，
使得 .
3 已知整數(shù)N，問N是否是一個素數(shù)？
4 試問77是否是素數(shù)？
5 試問79是否是素數(shù)？
6 已知整數(shù)N，求N的素分解式.
7 已知整數(shù)177，求其素分解式.
問題的定義及分類
算法復雜度定義及分類
P問題和NP問題
規(guī)約思想與NPC類
密碼算法的計算安全性
問題的定義及分類
1 設A=(a1,a2,…,an)是由n個不同的正整數(shù)構成的n元組，S是另一已知的正整數(shù). A稱為背包向量，S稱為背包容積. 求A中元素集合A’，使 .
2 設背包向量A=(1,2,5,10,20,50,100), 背包容積為177，求向量 ，
使得 .
3 已知整數(shù)N，問N是否是一個素數(shù)？
4 試問77是否是素數(shù)？
5 試問79是否是素數(shù)？
6 已知整數(shù)N，求N的素分解式.
7 已知整數(shù)177，求其素分解式.
