梅森素数特别判定法

yangchuanju · 发表于 2024-9-11 07:40

循环节长等于3的共两套——48,258,132和121,331,205；
48的父辈数4个——132,160,361,379；
160的祖辈数4个——69,223,288,442；
祖辈数69有4个曾祖数——85,134,377,426；
祖辈数223有4个曾祖数——15,204,307,496。

然121截然不同，
121的父辈数4个——205,233,278,306；
233的祖辈数4个——142,215,296,369；278的祖辈数4个——112,399,77,434；
另两个父辈数205,306都没有祖辈数；
8个祖辈数中有6个各有4个曾祖数，有2个有2个曾祖数，共28个曾祖数。
循环节121后的331,205具有同样多的父辈数、祖辈数、曾祖数。

本系统中，循环节长等于3的共168数——
从r2开始循环的24=4*3*2；
从r3开始循环的36=4*3*1+8*3*1；
从r4开始循环的108=8*3*1+28*3*1。

yangchuanju · 发表于 2024-9-11 07:41

r1 2 3 4 5 6
132 48 258 132
160 48 258 132
351 48 258 132
379 48 258 132
69 160 48 258 132
223 160 48 258 132
288 160 48 258 132
442 160 48 258 132
85 69 160 48 258 132
134 69 160 48 258 132
377 69 160 48 258 132
426 69 160 48 258 132
15 223 160 48 258 132
204 223 160 48 258 132
307 223 160 48 258 132
496 223 160 48 258 132

r1 2 3 4 5 6
205 121 331 205
233 121 331 205
278 121 331 205
306 121 331 205
142 233 121 331 205
215 233 121 331 205
296 233 121 331 205
369 233 121 331 205
112 278 121 331 205
399 278 121 331 205
77 306 121 331 205
434 306 121 331 205
12 142 233 121 331 205
61 142 233 121 331 205
450 142 233 121 331 205
499 142 233 121 331 205
231 215 233 121 331 205
280 215 233 121 331 205
58 296 233 121 331 205
131 296 233 121 331 205
380 296 233 121 331 205
453 296 233 121 331 205
161 369 233 121 331 205
350 369 233 121 331 205
25 112 278 121 331 205
171 112 278 121 331 205
340 112 278 121 331 205
486 112 278 121 331 205
67 399 278 121 331 205
213 399 278 121 331 205
298 399 278 121 331 205
444 399 278 121 331 205
88 77 306 121 331 205
234 77 306 121 331 205
277 77 306 121 331 205
423 77 306 121 331 205
158 434 306 121 331 205
207 434 306 121 331 205
304 434 306 121 331 205
353 434 306 121 331 205

yangchuanju · 发表于 2024-9-11 10:01

2^21-1= 2097151=7^2*127*337
序号 7 127 337 2097151
r1 4 4 4 4
r2 0 14 14 14
r3 5 67 194 194
r4 2 42 227 37634
r5 2 111 303 741029
r6 2 0 143 1766697
r7 2 125 227 1193544
r8 2 2 303 840107
r9 2 2 143 379605
r10 2 2 227 516511
r11 2 2 303 840107
整数 7 127 337 2097151
循环节长 1 1 3 3
循环开始 r2=0 r6=0 r5 r8

2^21-1=2097151=7^2*127*337
三素因子的循环节长分别是1,1,3，最大公约数是1，最小公倍数是3，
实际2^21-1的循环节长是3，是三素因子的最小公倍数。

yangchuanju · 发表于 2024-9-11 10:03

2^25-1= 33554431=31*601*1801
序号 31 601 1801 33554431
r1 4 4 4 4
r2 14 14 14 14
r3 8 194 194 194
r4 0 372 1614 37634
r5 29 152 748 7031852
r6 2 264 1192 25732079
r7 2 579 1674 1528922
r8 2 482 1719 33046467
r9 2 336 1319 27405335
r10 2 507 1794 619537
r11 2 420 47 30512589
r12 2 305 406 632557
r13 2 469 943 25323003
r14 2 594 1354 11509744
r15 2 47 1697 4734725
r16 2 404 8 6137816
r17 2 343 62 17606638
r18 2 452 240 17127750
r19 2 563 1767 6497974
r20 2 240 1154 11648221
r21 2 503 775 19728929
r22 2 587 890 11638952
r23 2 194 1459 26577015
r62 2 587 1787 30307214
r63 2 194 194 5412199
r64 2 372 1614 20603253
r65 2 152 748 14608659
r66 2 264 1192 25732079
整数 31 601 1801 33554431
循环节长 1 20 60 60
循环开始 r4=0 r3 r3 r6

2^25-1=33554431=31*601*1801
三素因子的循环节长分别是1,20,30，不计入1的最大公约数是10，最小公倍数是60，
实际2^25-1的循环节长是60，是三素因子的最小公倍数。

yangchuanju · 发表于 2024-9-11 10:04

2^29-1= 536870911=233*1103*2089
序号 233 1103 2089 536870911
r1 4 4 4 4
r2 14 14 14 14
r3 194 194 194 194
r4 121 132 32 37634
r5 193 877 1022 342576132
r6 200 336 2071 250734296
r7 155 388 322 433300702
r8 24 534 1321 16341479
r9 108 580 724 49808751
r10 12 1086 1924 57936161
r11 142 287 66 211467447
r12 124 745 176 71320725
r13 229 214 1728 91230447
r14 14 571 801 153832672
r15 194 654 276 217471443
r16 121 853 970 239636427
r17 193 730 848 223645010
r18 200 149 486 90243197
r19 155 139 137 27374393
r20 24 568 2055 490737401
r21 108 546 1154 35441039
r22 12 304 1021 303927542
r23 142 865 28 202574536
r24 124 389 782 515018664
r25 229 208 1534 330289146
r26 14 245 940 148819211
r27 194 461 2040 365171774
r28 121 743 310 458738443
r29 193 547 4 199330295
r252 124 308 310 67096901
r253 229 4 4 285716712
r254 14 14 14 14
r255 194 194 194 194
整数 233 1103 2089 536870911
循环节长 12 252 28 252
循环开始 r2 r1 r1 r2

2^29-1=536870911=233*1103*2089
三素因子的循环节长分别是12,252,28，最大公约数是4，最小公倍数是21168，
实际2^29-1的循环节长是252，仅为最小公倍数的84分之一。

yangchuanju · 发表于 2024-9-11 10:07

用r1=4对2^p-1型梅森合数和非梅森合数进行（广义）LL检验时，
笔者发现了2^p-1型合数循环节长的一大规律——
猜想2^p-1型梅森合数和非梅森合数的循环节长规等于它的各个素因子循环节长的最小公倍数或最小公倍数的某个约数——

2^11-1=2047=23*89，23循环节长5，89循环节长12，5和12的最小公倍数是60，2047的循环节长等于60；
2^23-1=8388607=47*178481，47循环节长11，178481循环节长2940，11和2940的最小公倍数是32340，20478388607的循环节长等于32340；
2^9-1=511=7*73，7循环节长算作1，73循环节长3，1和3的最小公倍数是3，511的循环节长等于3；
2^15-1=32767=7*31*151，7和31循环节长算作1，151循环节长9，1,1和9的最小公倍数是9，32767的循环节长等于9；

2^21-1=2097151=7^2*127*337
三素因子的循环节长分别是1,1,3，最大公约数是1，最小公倍数是3，
实际2^21-1的循环节长是3，是三素因子的最小公倍数。
2^25-1=33554431=31*601*1801
三素因子的循环节长分别是1,20,30，不计入1的最大公约数是10，最小公倍数是60，
实际2^25-1的循环节长是60，是三素因子的最小公倍数。
2^29-1=536870911=233*1103*2089
三素因子的循环节长分别是12,252,28，最大公约数是4，最小公倍数是21168，
实际2^29-1的循环节长是252，仅为最小公倍数的84分之一。
…………

yangchuanju · 发表于 2024-9-11 16:22

2^33-1= 8589934591<10>=7*23*89*599479
序号 7 23 89 599479 8589934591
1 4 4 4 4 4
2 0 14 14 14 14
3 -2 10 16 194 194
4 2 6 76 37634 37634
5 2 11 78 348556 1416317954
6 2 4 30 271515 8559033198
7 2 14 8 64677 4600466523
8 2 10 62 549344 3380411946
9 2 6 15 502255 6313615604
10 2 11 45 520781 4112946721
11 2 4 65 157653 2302157013
12 2 14 40 69067 2150400240
13 2 10 85 196084 3011978580
14 2 6 14 150431 452757076
15 2 11 16 352467 7739026878
6423 2 10 16 599285 6269351188
6424 2 6 76 37634 37634
6425 2 11 78 348556 1416317954

整数 7 23 89 599479 8589934591
循环节长 1 5 12 6420 6420
循环开始 r4 r1 r2 r4 r4

2^35-1= 34359738367<11>=31*71*127*122921
序号 31 71 127 122921 34359738367
1 4 4 4 4 4
2 14 14 14 14 14
3 8 52 67 194 194
4 0 4 42 37634 37634
5 -2 14 111 22192 1416317954
6 2 52 0 63336 8383890141
7 2 4 -2 44980 26401509044
8 2 14 2 43659 4040948613
9 2 52 2 95253 7667169707
10 2 4 2 89155 21463079123
6828 2 52 2 46527 30812284834
6829 2 4 2 122917 9073044848
6830 2 14 2 14 23956688309
6831 2 52 2 194 5349890877
6832 2 4 2 37634 17786460492
6833 2 14 2 22192 14804135748
6834 2 52 2 63336 1620162116
6835 2 4 2 44980 12874052994
6836 2 14 2 43659 4040948613
6837 2 52 2 95253 7667169707

整数 31 71 127 122921 34359738367
循环节长 1 3 1 6828 6828
循环开始 r6 r1 r8 r2 r8

2^39-1= 549755813887<12>=7*79*8191*121369
序号 7 79 8191 121369 549755813887
1 4 4 4 4 4
2 0 14 14 14 14
3 -2 36 194 194 194
4 2 30 4870 37634 37634
5 2 29 3953 63093 1416317954
6 2 49 5970 66185 386286279983
7 2 29 1857 4275 543377877212
8 2 49 36 70273 340683217380
9 2 29 1294 32655 405514008909
10 2 49 3470 989 90300478893
11 2 29 128 7167 493015692185
12 2 49 0 26800 283542891445
13 2 29 -2 99625 197789575951
14 2 49 2 69279 424791083803
15 2 29 2 42734 193202984550
16 2 49 2 76780 496893622717
1163 2 29 2 27888 348718531009
1164 2 49 2 7990 294165815729
1165 2 29 2 4 426107139964
1166 2 49 2 14 475921468227
1176 2 49 2 26800 466839574112
1177 2 29 2 99625 14627127398
1178 2 49 2 69279 424791083803
1179 2 29 2 42734 193202984550

整数 7 79 8191 121369 549755813887
循环节长 1 2 1 1164 1164
循环开始 r4 r5 r14 r1 r14

yangchuanju · 发表于 2024-9-11 20:42

众所周知，LL检验法常用于梅森数2^p-1的素性检验，令r1=4，r2=mod((r1^2-2),(2^p-1))，r3=mod((r2^2-2),(2^p-1))，……，当第p-1个余数等于0时这个梅森数就是素数；否则当第p-1个余数不等于0时这个梅森数就是合数；
然而并不是只有梅森素数的LL检验余数列中有余数0出现，普通素数97,607,12289,22783等套用LL检验时也都有余数0存在——
（下表中的7,31,12,8191都是梅森素数）
素数号素数 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12
4 7 4 0
11 31 4 14 8 0
31 127 4 14 67 42 111 0
1028 8191 4 14 194 4870 3953 5970 1857 36 1294 3470 128 0
25 97 4 14 0
111 607 4 14 194 0
2546 22783 4 14 194 14851 12759 7544 0
1470 12289 4 14 194 767 10704 5267 5014 9189 0

yangchuanju · 发表于 2024-9-11 20:43

一般素数的LL检验余数列——
素数 5 11 13 17 19 23
r1 4 4 4 4 4 4
r2 4 3 1 14 14 14
r3 4 7 12 7 4 10
r4 4 3 12 13 14 6
r5 4 7 12 14 4 11
r6 4 3 12 7 14 4
循环节长 1 2 1 3 2 5
循环开始 1 2 3 2 1 1

yangchuanju · 发表于 2024-9-11 20:44

普通二合数的LL检验余数列——
二合数 55 65 85 95 115 143 187 209 253 323 391
分解式 5*11 5*13 5*17 5*19 5*23 11*13 11*17 11*19 11*23 17*19 17*23
r1 4 4 4 4 4 4 4 4 4 4 4
r2 14 14 14 14 14 14 14 14 14 14 14
r3 29 64 24 4 79 51 7 194 194 194 194
r4 14 64 64 14 29 25 47 14 190 166 98
r5 29 64 14 4 34 51 150 194 172 99 218
r6 14 64 24 14 4 25 58 14 234 109 211
r7 29 64 64 4 14 51 183 194 106 251 336
r8 14 64 14 14 79 25 14 14 102 14 286
r9 29 64 24 4 29 51 7 194 29 194 75
r10 14 64 64 14 34 25 47 14 80 166 149
r11 29 64 14 4 4 51 150 194 73 99 303
r12 14 64 24 14 14 25 58 14 14 109 313
r13 29 64 64 4 79 51 183 194 194 251 217
r14 14 64 14 14 29 25 14 14 190 14 167
r15 29 64 24 4 34 51 7 194 172 194 126
r16 14 64 64 14 4 25 47 14 234 166 234
r17 29 64 14 4 14 51 150 194 106 99 14
r18 14 64 24 14 79 25 58 14 102 109 194
循环节长 2 1 3 2 5 2 6 2 10 6 15
循环开始 2 3 2 1 1 3 2 2 2 2 2
素数5的循环节长等于1，5p型二合数的循环节长等于单个素数p的循环节长；
素数11的循环节长等于2，11p型二合数的循环节长等于2个素数p的循环节长的最小公倍数（p的2倍数）；
素数17的循环节长等于3，17p型二合数的循环节长等于2个素数p的循环节长的最小公倍数（p的3倍数）；

		自动登录	找回密码
密码			注册