因為一個整數p，若檢測為合數，這永遠是真命題；而檢測為素數，這命題只以較大概率成立。 可構造一種NP檢測算法，步驟如下：
1. 猜測p（位長度n）的因子列表｛p1,p2,…pi｝，這是非確定的，每個分支耗時O(n)
2. 驗證p1*p2*…pi？=p-1，耗時不超過O(n^2)
3. 若各因子乘積等于p-1，則用當前算法遞歸驗證每個因子都是素數
4. 隨機選擇p最小剩余系內的一個數x，計算x^((p-1)/q) （q遍歷上述列表經過步驟3驗證過的素因子）是否都不同余于1模p，若是則必有x^(p-1)同余于1模p，則由指數整除p的歐拉數及費馬小定理，知p為素數，考慮到有少量的合數也滿足費馬小定理，故需多次選擇x重復驗證，選擇個數最多為log(p)
分析：本算法涉及的數論定理——設p是奇素數，p-1的所有素因子是q1,q2,…qs，那么g為原根的充要條件是，g^((p-1)/qj)不同余1模p，j=1,2…,s
結論：第3步可以看成遞歸調用樹，每個頂點為待檢測整數，其每個子結點為一個因子，則最多n層，每層至多耗時O(n^4)，所以每個路徑即檢測p是否素數的非確定任一分支中，總耗時O(n^5)。 2002年，印度科學家發現素檢測確定性多項式時間算法，于是從NP前進到了P
posted on 2023-09-09 08:07
春秋十二月 閱讀(695)
評論(0) 編輯 收藏 引用 所屬分類:
Compute Theory