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