Lncas-Lehmer梅森素数判定法

yangchuanju

Lncas-Lehmer梅森素数判定法

采用太阳试除法虽然能判定一个梅森数2^p-1是不是梅森素数，该方法正确有效，但它不是一种简捷的判定方法。
若要判定移动梅森数2^p-1是不是梅森素数，通常采用Lncas-Lehmer梅森素数判定法。

Lncas-Lehmer梅森素数判定法
设p是素数，设第p个梅森数为Mp=2^p-1，定义r1=4，对于k≥2，利用rk≡<rk-1>^2 – 2  (mod Mp)，0≤rk<Mp；可以递归得到一整数序列，那么Mp是素数当且仅当<rp-1>≡0 (mod Mp)。

【附注】文中尖括号<rk-1>和<rp-1>中的k-1、p-1都是下标，<rk-1>和<rp-1>都是整体符号，尖括号是笔者外加的；Mp、rk中的p和k也都是下标。

例：考虑梅森数M5=2^5-1=31。那么r1=4、r2≡4^2-2≡14 (mod 31)、r3≡14^2-2=194≡8 (mod31)和r4≡8^2-2=62≡0 (mod 31)。因为r4≡0 (mod 31)，故可知M5=2^5-1=31是素数。

yangchuanju

r        31        63        127        255
1        4        4        4        4
2        14        14        14        14
3        8        5        67        194
4        0        23        42        149
5                23        111        14
6                23        0        194

yangchuanju

r        2^17-1=        2^19-1=
—        131071        524287
1        4        4
2        14        14
3        194        194
4        37634        37634
5        95799        218767
6        119121        510066
7        66179        386344
8        53645        323156
9        122218        218526
10        126220        504140
11        70490        103469
12        69559        417706
13        99585        307417
14        78221        382989
15        130559        275842
16        0        85226
17        ——        523263
18        ——        0

yangchuanju

        Lncas-Lehmer梅森素数判定法对于2^31-1也是正确的！       
r        2^31-1=        模余平方减2
—        2147483647        4
1        4        14
2        14        194
3        194        37634
4        37634        1416317954
5        1416317954        2005956546822746114
6        669670838        448459031267622242
7        1937259419        3752974056504217559
8        425413602        180976732766614402
9        842014276        708988040987804174
10        12692426        161097677765474
11        2044502122        4179988926862502882
12        1119438707        1253143018729831847
13        1190075270        1416279148265572898
14        1450757861        2104698371253295319
15        877666528        770298534371574782
16        630853853        397976583844945607
17        940321271        884204092695055439
18        512995887        263164780078916767
19        692931217        480153671493101087
20        1883625615        3548045457484128223
21        1992425718        3969760241747815522
22        721929267        521181866551157287
23        27220594        740960737712834
24        1570086542        2465171749369517762
25        1676390412        2810284813445529742
26        1159251674        1343864443671802274
27        211987665        44938770112152223
28        1181536708        1396028992351477262
29        65536        4294967294
30        0       

yangchuanju

如果p模4余3，p和2p+1都是素数，则2p+1能够整除梅森数2^p-1；
如23|M11，47|M23，167|M83，263|M131，359|M179，383|M191，479|M239，503|M251，……
M11、M23、M83、M131、M179、M191、M239、M251等都不是素数。

如果p模4余1，p和2p+1都是素数，则2p+1不能整除梅森数2^p-1，但能够整除2^p+1。

时空伴随者

2022-01-20 10:26:00
Lucas-Lehmer Test 判别 10000 以内奇素数产生的梅森素数
2^3-1 is prime
2^5-1 is prime
2^7-1 is prime
2^13-1 is prime
2^17-1 is prime
2^19-1 is prime
2^31-1 is prime
2^61-1 is prime
2^89-1 is prime
2^107-1 is prime
2^127-1 is prime
2^521-1 is prime
2^607-1 is prime
2^1279-1 is prime
2^2203-1 is prime
2^2281-1 is prime
2^3217-1 is prime
2^4253-1 is prime
2^4423-1 is prime
2^9689-1 is prime
2^9941-1 is prime
用时 469.1401333808899 秒
def LucasLehmerTest(p=61):
    m, q = 2 ** p - 1, 4
    for i in range(p - 2):
        q = pow(q, 2, m) - 2
    return not q

if __name__ == '__main__':
    import datetime as dt, time as tm
    print(dt.datetime.now().strftime("%F %T"))
    start = tm.time()
    print('Lucas-Lehmer Test 判别 10000 以内奇素数产生的梅森素数')
    Primes = prime_sieve(10000)
    for p in Primes:
        if LucasLehmerTest(p):
            print(f'2^{p}-1 is prime')
    print(f"用时 {tm.time() - start} 秒")

yangchuanju

时空伴随者 发表于 2022-1-20 10:31
2022-01-20 10:26:00
Lucas-Lehmer Test 判别 10000 以内奇素数产生的梅森素数
2^3-1 is prime

老师的检验程序对于小梅森素数非常迅速快捷，你的程序能不能检验一下2^(2^127-1)-1是不是素数？
网上有人猜想它是宝塔型梅森素数，对那人无法证明。

不要检验了，2^127-1是一个39位素数，太大了，恐怕它检验不了。
如果老师的程序能够检验指数是8位素数的梅森数（39-51号），那老师也一定成为了世界名人了。

太阳

\(已知：奇数a＞0，t＞0，\frac{2^a-1}{2\times a+1}＝t，素数u＞0，求证：a＝u\)

yangchuanju

太阳 发表于 2022-1-21 00:08
\(已知：奇数a＞0，t＞0，\frac{2^a-1}{2\times a+1}＝t，素数u＞0，求证：a＝u\)

太阳新素数
如果a是大于0的奇数，(2^a-1)/(2a+1)能整除，则a就是素数
A=1， (2^a-1)/(2a+1)=1/3，不能整除，1不是素数；
A=3， (2^a-1)/(2a+1)=7/7，能整除，3是素数；
A=5， (2^a-1)/(2a+1)=31/11，不能整除，5是素数；
A=7， (2^a-1)/(2a+1)=127/15，不能整除，7是素数；
A=11， (2^a-1)/(2a+1)=511/17，不能整除，17是素数；
A=13， (2^a-1)/(2a+1)=2023/19，不能整除，19是素数；
……
a        2^a-1        2a+1        整除1        素性
1        1        3        0       
3        7        7        1        整除 素数
5        31        11        0       
7        127        15        0       
9        511        19        0       
11        2047        23        1        整除 素数
13        8191        27        0       
15        32767        31        1        整除 非素数
17        131071        35        0       
19        524287        39        0       
21        2097151        43        0       
23        8388607        47        1        整除 素数
25        33554431        51        0       
27        134217727        55        0       
29        536870911        59        0       
31        2147483647        63        0       
33        8589934591        67        0       
35        34359738367        71        1        整除 非素数
37        1.37439E+11        75        0       

yangchuanju

梅森数有一条重要性质，“如果p是一个奇素数，那么梅森数Mp=2^p-1因子均如2kp+1，其中k是一个正整数。”
——美Kenneth  H.  Rosen 《初等数论及其应用》定理7.12

该定理的逆命题不成立：如果2kp+1能够整除2^p-1，则p就是素数。