一種適合量子計算的素性檢驗(yàn)方法

周忠奇

(湖北省煤炭地質(zhì)局，湖北武漢430070)

0 引言

眾所周知，如果m＞1是素數(shù)，ordm(a)是正整數(shù)a對模數(shù)m的階，則必有

定理 設(shè)≥3為正奇數(shù)，a為正整數(shù)，(a，m)=1，m≠9，15，25，49，561，6601，并設(shè)

若k不為整數(shù)，則m為合數(shù);若k為整數(shù)且k＜9，則m為素數(shù).

證明定理，需要以下引理.

引理1[4]p為奇素數(shù)，(a，p)=1，則

引理2[1]如果m=…是m的標(biāo)準(zhǔn)分解式，則正整數(shù)a對模數(shù)m的階d=[f1，…，fk]式中，fi表示a對模數(shù)的階.

引理3設(shè)m=p1p2p3，其中p1＜p2＜p3，p1，p2，p3為互不相同的奇素數(shù)，設(shè)

則

由m=p1p2p3和式(3)知p1，p2，p3都不等于3，且當(dāng)5≤p1＜p2＜p3，p3≥37時n＜.當(dāng)5≤p＜p＜p＜37時n≠，所以對于任意不同的奇素數(shù)p，p，p，n≠

由m=p1p2p3和式(4)知p1，p2，p3都不等于5.若p1=3，由式(4)有5(p2+p3)+p2p3=7此不可.當(dāng)7≤p＜p＜p，p≥53時n＜，在7≤p＜p＜p＜53的所有素數(shù)中，僅有p=7，p=23， p=41，m=6601使n=3

3＜p2≤7時式(5)不成立.當(dāng)p2=11時，p3=17，m=561使當(dāng)p1≥5時，由式(2)

定理 證畢.

引理4設(shè)m=p1p2，p1＜p2，p1，p2為不相同的奇素數(shù)，若

則

(ii)僅有m=p1p2=7×13=91使

(iii)僅有m=p1p2=3×5=15使

(iv)僅有m=p1p2=5×13=65使

若p1=3，式(7)不成立;若，因p1和p2為不相同的素數(shù)，所以若由式(6)

p1=3，5，7時式(8)不成立;若p1=11，由式(8)，p2不為素數(shù);若p1≥13，則所以

當(dāng)p1=3或5時，式(9)不成立.當(dāng)p1=7時，由式(9)，p2=13，m=91使當(dāng)p1≥11時，p2＜11.

若p1=3時，由式(10)，p2=5，m=15使若p1≥5時，由式(10)，可知

若p1=3，式(11)不成立.若p1=5，由式(11)，p2=13，m=65使若p1≥7，由式(11)p2=定理證畢.

引理5設(shè)m為奇數(shù)若m=9，15，25，49時k不為整數(shù).若m=561，6601時k＞8.

引理得證.

1 定理的證明

若ordm(a)≠m－1，根據(jù)引理1，m必為合數(shù).

如果t=1，p為奇素數(shù)，m=pα且當(dāng)α＞2時

當(dāng)α=2時

只有在p=3，h=2;p=3，h=1;p=5，h=1;p=7，h=1幾種情況下h(p+1)＜9，此時m=9，25，49.所以，當(dāng)m=pα，m≠9，25，49時

如果m=p1……，pi(i=1，…，t.)qj(j=1，…，s.)均為各不相同的奇素數(shù)且ordpi(a)=若t≥1，s≥1，則

不妨設(shè)m=p1…pr，下面要證明的是:如果，則r=1.因

當(dāng)r=2時，m=p1p2，p1＜p2，p1，p2為不相同的奇素數(shù)，

因此，只有h＜8.因p1－1與p2－1均為偶數(shù)且

因此，在h中必存在一個因子2，即h＜8的所有可能取值為:2，4，6.因

所以只要證明，當(dāng)m≠9，15，25，49，561，6601時

根據(jù)引理4知:當(dāng)m=p1p2，p1＜p2，p1，p2為不相同的奇素數(shù)時

根據(jù)引理1和引理2知ord65(a)=[ord5(a)，ord13(a)]的所有可能取值為:1，2，3，4，6，12.所以，若時，m－1=90.

根據(jù)引理1和引理2知ord91(a)=[ord7(a)，ord13(a)]，的所有可能取值為:1，2，3，4，6，12，若

所以，當(dāng)m≠15，m=p1p2且

當(dāng)r=3時，m=p1p2p3，p1＜p2＜p3，p1，p2，p3為各不相同的奇素數(shù)，設(shè)

所以在h中必有一個因子4，即h＜8的可能取值只有4，現(xiàn)只要證明，當(dāng)m≠9，15，25，49，561，6601時

綜合以上證明過程得出以下結(jié)論:

2 由定理得到的素性檢驗(yàn)方法

根據(jù)定理，我們可以得到一種確定型一般性素性檢驗(yàn)方法:

對于一個奇數(shù)m，當(dāng)m≠9，15，25，49，561，6601時，可以給定一個整數(shù)a1＞1，m＞a1，并計算d1=(a1，m)，若d1＞1，則m為合數(shù);若d1=1，再計算ordm(a1)和若k1不為整數(shù)，則m為合數(shù);若k1為整數(shù)且小于9，則m為素數(shù);若k1為整數(shù)且大于或等于9，則再給定一個整數(shù)a2＞1，m＞a2≠a1，并計算d2=(a2，m)，若d2＞1，則m為合數(shù);

如果d2=1再計算ordm(a2)和，若k2不為整數(shù)，則m為合數(shù);若k2為整數(shù)且小于9，則m為素數(shù);若k2為整數(shù)且大于或等于9，則再給定一個整數(shù)a3＞1，m＞a3≠a2≠a1，…，直到將m判定為合數(shù)或素數(shù)為止.

實(shí)際上，根據(jù)引理1.5我們可以設(shè)定a1=2從而可以不考慮m≠9，15，25，49，561，6601的因素.下面給出一個判定正整數(shù)是否為素數(shù)的程序的具體步驟:

1)輸入奇數(shù)m;a←2;

2)d←(a，m);如果d＞1，則輸出合數(shù)m.退出;

4)如果k不等于整數(shù)，則輸出合數(shù)m.退出;

5)如果k是整數(shù)且k＜9，則輸出質(zhì)數(shù)m.退出;

6)a←a+1轉(zhuǎn)到第2)步.

3 結(jié)束語

以上的素數(shù)檢驗(yàn)方法是一種確定型一般性檢驗(yàn)方法.通過實(shí)際計算可知:用a=2檢驗(yàn)一輪便可確定95%以上的數(shù)是合數(shù)或是素數(shù).例如，a1=2時，在106以內(nèi)，只有9 538個整數(shù)未能確定其素數(shù)或合數(shù).

從給出的檢驗(yàn)程序可以看出:決定檢驗(yàn)時間的主要是求(a，m)和ordm(a)，求(a，m)是可在多項(xiàng)式時間內(nèi)完成的，但現(xiàn)有計算機(jī)求ordm(a)的速度比較慢，但根據(jù)資料顯示，如果采用量子算法求ordm(a)[5]是多項(xiàng)式時間可完成的，所以，本文給出的應(yīng)該是一種適合量子算法的素性判別方式.

[1] 柯召，孫琦.數(shù)論講義[M].2版.北京:高等教育出版社，2001.

[2] 顏松遠(yuǎn).計算數(shù)論[M].楊思熳，譯.北京:清華大學(xué)出版社，2008.

[3] Ribenboim P.博大精深的素數(shù)[M].孫淑玲，馮克勤，譯.北京:科學(xué)技術(shù)出版社，2007.

[4] Joseph H Silverman.數(shù)論概論[M].3版.孫智偉，譯.北京:機(jī)械工業(yè)部出社，2008.

[5] 吳盛俊，周錦東，張永德.量子算法簡介[J].大學(xué)物理，1999，18(12):1-5.