一個整數(shù)分解和素性判別的新方法

李良元

（重慶航天職業(yè)技術學院，重慶 400021）

1 預備工作

整數(shù)分解和素性判別是數(shù)論中的重要課題，數(shù)論中很多問題都跟其有關，這個課題在密碼學中有極其重要的地位，但在實際計算中，我們還沒有簡易可行的方法去分解一個大整數(shù)或判斷哪些正整數(shù)是素數(shù)。隨著計算機運行速度的提升，互聯(lián)網(wǎng)的廣泛應用，在整數(shù)分解與素性判別方面取得了一些成果。由全球麥森（Mersenne）數(shù)愛好者參與的GIMPS（互聯(lián)網(wǎng)麥森素數(shù)大搜尋）項目，在2018年12月找到了第51個麥森（Mersenne）數(shù)，但最近三年也沒有找到新的麥森數(shù)。而第五個Fermat數(shù)之后是否還有Fermat素數(shù)依然是一個沒有解決的問題。有些Fermat數(shù)盡管我們知道它們是合數(shù)，也不知道如何分解。本文運用數(shù)論和代數(shù)的基本知識，給出了一種整數(shù)分解和素性判別的新方法，并可以有效運用于麥森數(shù)，費馬（Fermat）數(shù)的素性判別。

定義1設奇數(shù)m3。滿足同余式2T≡1（modm）的最小正整數(shù)T稱為2對模m的指數(shù)（本文簡稱為m的指數(shù)）。m的指數(shù)為T的素因數(shù)或指數(shù)為T的素因數(shù)的乘積叫做m的主因數(shù)。

引理 1（[1]）

設素數(shù)p的指數(shù)為T，則T|p-1.

引理 2（[1]）

設m的指數(shù)為T，其素數(shù)分解式為，pi的指數(shù)為Ti，則Ti|T.

定理 1設m的指數(shù)為T，素數(shù)p1，p2是其主因數(shù)，則p1p2≡ 1（modT）.

證明：由于p1，p2是m的主因數(shù)，根據(jù)引理1，pi≡ 1（modT），i=1，2，因此，p1p2≡ 1（modT）。根據(jù)定理 1，立刻可得。

定理 2設m的指數(shù)為T，MT是其主因數(shù)，則MT≡ 1（modT）。為了后面計算中上界的設定，我們還需要下面的引理。

引理 3（[2]）

設mN，而m非素數(shù)，則m必為一不大于的素數(shù)所整除。

2 主因數(shù)的分解

設m的指數(shù)為T，MT為m的主因數(shù)，因此，

根據(jù)定理2，存在正整數(shù)h，使得MT=hT+1，并有非負整數(shù)a，b，0b

如果MT不是素數(shù)，設MI是MT的最小素因數(shù)，根據(jù)引理3，

且存在整數(shù)MIIMI，使得MT=MIMII。根據(jù)定義 1，MI，MII都是m的指數(shù)為T的主因數(shù)。由定理2，存在正整數(shù)x1，x2，使得

設k為待定非負整數(shù)，將（2.2）式化為

比較（2.5），（2.6）式，可知存在非負整數(shù)k，使x1x2=a-k，x1+x2=kT+b，即x1，x2為方程

的兩個正整數(shù)根，因此

因為x1，x2是正整數(shù)，根據(jù)（2.9），我們有q

這樣，對于每一組同時滿足（2.12）與（2.14）的k，q，由（2.5）都可以得到MT的一個分解：

當不存在整數(shù)k和q同時滿足（2.12）與（2.14）時，MT是素數(shù)。

3 Mersenne數(shù)的素性判定

形如2n-1的素數(shù)叫Mersenne數(shù)。設p是素數(shù)，Mp=2p-1，則

因此，Mp的指數(shù)為p.根據(jù)定義1與引理2，Mp的所有大于1的因數(shù)都是指數(shù)為p的主因數(shù)（根據(jù)定義1可知T2）.利用上節(jié)的結果，我們可以對Mp進行素性判定.

例3.1判別M13的素性。

解：M13=213-1=8191=13×（48×13+6）+1，因此，a=48，b=6，T=13.由（2.12）式及（2.14）式，

由于沒有適合（3.2）式的整數(shù)q，k，因此，M13是素數(shù).例3.2判別M29的素性。

解：M29=2291=536870911=29×（638372×29+2）+1，因此，a=638372，b=2，T=29.由（2.12）式及（2.14）式，

經(jīng)過計算，（q，k）=（-14，2740），（-74，580），（-142，308）適合（3.3）式，因此，M29是合數(shù)。將此三組數(shù)據(jù)及a，b，T的值代入（2.5）式，們可以得到

M29=233×1103×2089.

另外，我們也可以利用后附的Table1-3判別Mersenne數(shù)的素性。

例3.3判別M11的素性。解：由Table 1知道，23的指數(shù)為11，因此，23|M11且23

4 Fermat數(shù)的素性判定

形如22n+1的數(shù)叫Fermat數(shù)，記為Fn。由于

因此，F(xiàn)n的指數(shù)為2n+1。根據(jù)定義1與引理2，F(xiàn)n的所有大于1的因數(shù)都是指數(shù)為2n+1的主因數(shù)。利用第二節(jié)的結果，我們可以對Fn進行素性判定。由于

因此，在（2.2）式中，

此時，由（2.12）式及（2.14）式可得

記q=-2qF，由（4.3）式及（4.4）式可得

并由（2.15）得到

例4.1判別Fn，1n5的素性。

解：當n=1，2，3，4時，很容易算出沒有適合（4.5）式的整數(shù)qF，k，因此，F(xiàn)n是素數(shù).當n=5時，由（4.5）知，

計算可得qF=10，k=1636.由（4.6）可得

F5=（25+1·10+1）（25+1（25+·11636-10）+1）=641·6700417.我們知道，F(xiàn)14是合數(shù)，但我們目前還不知道其任何真因子。通過上面的例子，我們給出一個求其真因子的一個算法。

例4.2F14的分解。

解：由（4.5）知，

通過計算，找出滿足上式的qF和k，就可以由（4.6）得到F14的兩個真因子。

另外，我們也可以利用Table 1-3判別Mersenne數(shù)的素性。

例4.3判別F4的素性。

解：由于F4=216+1=65537，216≡-1（mod F4），因此，F(xiàn)4的指數(shù)是32，根據(jù)引理2，F(xiàn)4的素因數(shù)的指數(shù)都是32.但.由Table 3知道，沒有小于或等于256且指數(shù)為32的素數(shù)。根據(jù)引理3，F(xiàn)4是素數(shù)。

5 整數(shù)的素因子分解

設m的指數(shù)為T，其素數(shù)分解式為，pi的指數(shù)為Ti，由引理2知道Ti|T。

對于整數(shù)m，我們先計算出指數(shù)T。根據(jù)引理2，m的素因子pi的指數(shù)都是T的因子，因此，我們先計算出T的所有大于1的因子Ti，再找出指數(shù)為Ti的素數(shù)qi，檢驗qi是否為m的因子就可以了。

例5.1分解整數(shù)m=4311744255。

解：容易算出，m的指數(shù)是48，其大于1的因子有2，3，4，6，8，12，16，24，48.根據(jù)計算可知（亦可在 Table 3中查找），指數(shù)為2的素數(shù)是3，指數(shù)為3的素數(shù)是7，指數(shù)為4的素數(shù)是5，沒有指數(shù)為6的素數(shù)，指數(shù)為8的素數(shù)是17，指數(shù)為12的素數(shù)是13，指數(shù)為16的素數(shù)是257，指數(shù)為24的素數(shù)是241，指數(shù)為48的素數(shù)是97和673.經(jīng)驗算，3，5，7，13，17，241，257是m 的素因子，并得出分解式：

6 結語

以上首先定義了主因子及其對應的主因數(shù)概念，其基本思路是一個“分”字，從而擺脫過去的“篩”字，并按指數(shù)分類列出了少部分素數(shù)，從中可探索出素數(shù)的分布規(guī)律。

其次給出了m3的奇數(shù)素性判別公式計算法，也可以變換為多項式計算法。

對于m3正奇整數(shù)的素因子分解可由同余式2T=1，mod（m）的T決定。根據(jù)T的真因子和主因子對應的素數(shù)，經(jīng)驗算可得出m的素因子分解，做到完全指數(shù)分解法。