一个整数分解和素性判别的新方法

李良元

（重庆航天职业技术学院，重庆 400021）

1 预备工作

整数分解和素性判别是数论中的重要课题，数论中很多问题都跟其有关，这个课题在密码学中有极其重要的地位，但在实际计算中，我们还没有简易可行的方法去分解一个大整数或判断哪些正整数是素数。随着计算机运行速度的提升，互联网的广泛应用，在整数分解与素性判别方面取得了一些成果。由全球麦森（Mersenne）数爱好者参与的GIMPS（互联网麦森素数大搜寻）项目，在2018年12月找到了第51个麦森（Mersenne）数，但最近三年也没有找到新的麦森数。而第五个Fermat数之后是否还有Fermat素数依然是一个没有解决的问题。有些Fermat数尽管我们知道它们是合数，也不知道如何分解。本文运用数论和代数的基本知识，给出了一种整数分解和素性判别的新方法，并可以有效运用于麦森数，费马（Fermat）数的素性判别。

定义1设奇数m3。满足同余式2T≡1（modm）的最小正整数T称为2对模m的指数（本文简称为m的指数）。m的指数为T的素因数或指数为T的素因数的乘积叫做m的主因数。

引理 1（[1]）

设素数p的指数为T，则T|p-1.

引理 2（[1]）

设m的指数为T，其素数分解式为，pi的指数为Ti，则Ti|T.

定理 1设m的指数为T，素数p1，p2是其主因数，则p1p2≡ 1（modT）.

证明：由于p1，p2是m的主因数，根据引理1，pi≡ 1（modT），i=1，2，因此，p1p2≡ 1（modT）。根据定理 1，立刻可得。

定理 2设m的指数为T，MT是其主因数，则MT≡ 1（modT）。为了后面计算中上界的设定，我们还需要下面的引理。

引理 3（[2]）

设mN，而m非素数，则m必为一不大于的素数所整除。

2 主因数的分解

设m的指数为T，MT为m的主因数，因此，

根据定理2，存在正整数h，使得MT=hT+1，并有非负整数a，b，0b

如果MT不是素数，设MI是MT的最小素因数，根据引理3，

且存在整数MIIMI，使得MT=MIMII。根据定义 1，MI，MII都是m的指数为T的主因数。由定理2，存在正整数x1，x2，使得

设k为待定非负整数，将（2.2）式化为

比较（2.5），（2.6）式，可知存在非负整数k，使x1x2=a-k，x1+x2=kT+b，即x1，x2为方程

的两个正整数根，因此

因为x1，x2是正整数，根据（2.9），我们有q

这样，对于每一组同时满足（2.12）与（2.14）的k，q，由（2.5）都可以得到MT的一个分解：

当不存在整数k和q同时满足（2.12）与（2.14）时，MT是素数。

3 Mersenne数的素性判定

形如2n-1的素数叫Mersenne数。设p是素数，Mp=2p-1，则

因此，Mp的指数为p.根据定义1与引理2，Mp的所有大于1的因数都是指数为p的主因数（根据定义1可知T2）.利用上节的结果，我们可以对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）式的整数q，k，因此，M13是素数.例3.2判别M29的素性。

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

经过计算，（q，k）=（-14，2740），（-74，580），（-142，308）适合（3.3）式，因此，M29是合数。将此三组数据及a，b，T的值代入（2.5）式，们可以得到

M29=233×1103×2089.

另外，我们也可以利用后附的Table1-3判别Mersenne数的素性。

例3.3判别M11的素性。解：由Table 1知道，23的指数为11，因此，23|M11且23

4 Fermat数的素性判定

形如22n+1的数叫Fermat数，记为Fn。由于

因此，Fn的指数为2n+1。根据定义1与引理2，Fn的所有大于1的因数都是指数为2n+1的主因数。利用第二节的结果，我们可以对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）式的整数qF，k，因此，Fn是素数.当n=5时，由（4.5）知，

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

F5=（25+1·10+1）（25+1（25+·11636-10）+1）=641·6700417.我们知道，F14是合数，但我们目前还不知道其任何真因子。通过上面的例子，我们给出一个求其真因子的一个算法。

例4.2F14的分解。

解：由（4.5）知，

通过计算，找出满足上式的qF和k，就可以由（4.6）得到F14的两个真因子。

另外，我们也可以利用Table 1-3判别Mersenne数的素性。

例4.3判别F4的素性。

解：由于F4=216+1=65537，216≡-1（mod F4），因此，F4的指数是32，根据引理2，F4的素因数的指数都是32.但.由Table 3知道，没有小于或等于256且指数为32的素数。根据引理3，F4是素数。

5 整数的素因子分解

设m的指数为T，其素数分解式为，pi的指数为Ti，由引理2知道Ti|T。

对于整数m，我们先计算出指数T。根据引理2，m的素因子pi的指数都是T的因子，因此，我们先计算出T的所有大于1的因子Ti，再找出指数为Ti的素数qi，检验qi是否为m的因子就可以了。

例5.1分解整数m=4311744255。

解：容易算出，m的指数是48，其大于1的因子有2，3，4，6，8，12，16，24，48.根据计算可知（亦可在 Table 3中查找），指数为2的素数是3，指数为3的素数是7，指数为4的素数是5，没有指数为6的素数，指数为8的素数是17，指数为12的素数是13，指数为16的素数是257，指数为24的素数是241，指数为48的素数是97和673.经验算，3，5，7，13，17，241，257是m 的素因子，并得出分解式：

6 结语

以上首先定义了主因子及其对应的主因数概念，其基本思路是一个“分”字，从而摆脱过去的“筛”字，并按指数分类列出了少部分素数，从中可探索出素数的分布规律。

其次给出了m3的奇数素性判别公式计算法，也可以变换为多项式计算法。

对于m3正奇整数的素因子分解可由同余式2T=1，mod（m）的T决定。根据T的真因子和主因子对应的素数，经验算可得出m的素因子分解，做到完全指数分解法。