梅森素数Lucas-Lehmer判定法

yangchuanju · 发表于 2024-8-24 04:38

https://www.cnblogs.com/pprp/p/7663555.html
梅森素数判定总结 - Lucas-Lehmer算法 & Miller-rabin算法

梅森素数
定义：
if m是一个正整数 and 2^m-1是一个素数 then m是素数
if m是一个正整数 and m是一个素数 then M(m)=2^m-1被称为第m个梅森数
if p是一个素数 and M(p)是一个素数 then M(p)被称为梅森素数

Lucas-Lehmer判定法：判定一个梅森数是否是梅森素数
设p是素数，第p个梅森数为M(p)为2^p-1，令r1 = 4，对于k >= 2
r(k) = r(k-1)^2-2(modM(p))， 0 <= r(k) <= M(p)，可以得到r(k)序列，
则有M(p)是素数，当且仅当r(p-1) = 0(mod M(p))。

推论:设p是素数，M(p)为第p个梅森数，则算法复杂度为O(n^3)

yangchuanju · 发表于 2024-8-24 04:47

本帖最后由 yangchuanju 于 2024-8-24 04:50 编辑

OEIS给出的一些LL检验数据
（平方减2的余数）

A129219 A129220 A129221 A129222
2^7-1 2^11-1 2^13-1 2^17-1
0 4 0 4 0 4 0 4
1 14 1 14 1 14 1 14
2 67 2 194 2 194 2 194
3 42 3 788 3 4870 3 37634
4 111 4 701 4 3953 4 95799
5 0 5 119 5 5970 5 119121
———— 6 1877 6 1857 6 66179
———— 7 240 7 36 7 53645
———— 8 282 8 1294 8 122218
———— 9 1736 9 3470 9 126220
———— ———— 10 128 10 70490
———— ———— 11 0 11 69559
———— ———— ———— 12 99585
———— ———— ———— 13 78221
———— ———— ———— 14 130559
———— ———— ———— 15 0

A129223 A129224 A129225 A129226
2^19-1 2^23-1 2^29-1 2^31-1
0 4 0 4 0 4 0 4
1 14 1 14 1 14 1 14
2 194 2 194 2 194 2 194
3 37634 3 37634 3 37634 3 37634
4 218767 4 7031978 4 342576132 4 1416317954
5 510066 5 7033660 5 250734296 5 669670838
6 386344 6 1176429 6 433300702 6 1937259419
7 323156 7 7643358 7 16341479 7 425413602
8 218526 8 3179743 8 49808751 8 842014276
9 504140 9 2694768 9 57936161 9 12692426
10 103469 10 763525 10 211467447 10 2044502122
11 417706 11 4182158 11 71320725 11 1119438707
12 307417 12 7004001 12 91230447 12 1190075270
13 382989 13 1531454 13 153832672 13 1450757861
14 275842 14 5888805 14 217471443 14 877666528
15 85226 15 1140622 15 239636427 15 630853853
16 523263 16 4321431 16 223645010 16 940321271
17 0 17 7041324 17 90243197 17 512995887
———— 18 2756392 18 27374393 18 692931217
———— 19 1280050 19 490737401 19 1883625615
———— 20 6563009 20 35441039 20 1992425718
———— 21 6107895 21 303927542 21 721929267
———— ———— 22 202574536 22 27220594
———— ———— 23 515018664 23 1570086542
———— ———— 24 330289146 24 1676390412
———— ———— 25 148819211 25 1159251674
———— ———— 26 365171774 26 211987665
———— ———— 27 458738443 27 1181536708
———— ———— ———— 28 65536
———— ———— ———— 29 0

yangchuanju · 发表于 2024-8-24 04:52

本帖最后由 yangchuanju 于 2024-8-24 04:54 编辑

A000040 A095847
前100素数 LL检验残留数
1 2 1 1
2 3 2 0
3 5 3 0
4 7 4 0
5 11 5 1736
6 13 6 0
7 17 7 0
8 19 8 0
9 23 9 6107895
10 29 10 458738443
11 31 11 0
12 37 12 117093979072
13 41 13 856605019673
14 43 14 5774401272921
15 47 15 96699253829728
16 53 16 5810550306096509
17 59 17 450529175803834166
18 61 18 0
19 67 19 44350645312365507266
20 71 20 271761692158955752596
21 73 21 2941647823169311845731
22 79 22 149246123283525944719226
23 83 23 7426393223211489353123218
24 89 24 0
25 97 25 138799132171283648987055810555
26 101 26 2457457639868305855274916344886
27 103 27 4473275459952545161188509965118
28 107 28 0
29 109 29 80310482899578688674364643057506
30 113 30 6600791243740670132758919227993337
31 127 31 0
32 131 32 1720152102472260647526711808965574882231
33 137 33 90145568356072673645446219346258028265320
34 139 34 181318185791829225812656754645855481517572
35 149 35 267073170876646890164052223831706652997781887
36 151 36 470161961762879738539111160542992480498188270
37 157 37 118575088038271696981847356985091237731803092037
38 163 38 7949391637520036854358735766884218870217793032062
39 167 39 59077894719718305021040431865376339694751759149076
40 173 40 2988197556836046866193446269006656423021563329578278
41 179 41 179168095035563549612267159199350358897799678925859572
42 181 42 2545708861022630023106795600613882012653337766382168120
43 191 43 2821088812285258860697067303093261284412930158595090517585
44 193 44 5424570125193908141321143009568020463304970794324280151282
45 197 45 17795637780394400779031694196430946586900689971151521057263
46 199 46 618005096756687435771335671905442575859560302147442709524167
…………
98 521 98 0
99 523 99 1468025647395679657146189526712799440186277703370224062396990298411675630526566618205068397333402833591912842688020677553666161855432995011302389549500952495
100 541 100 6880023384160599081998085621614814982101522284740368094465940577475044864706536335718386108395891072641704360231615338763160279748248473993466273854145574699739819

yangchuanju · 发表于 2024-8-24 04:59

本帖最后由 yangchuanju 于 2024-8-24 05:00 编辑

笔者计算的2^37-1余数（对的）
2^37-1= 137438953471 模137438953471余
1 4
2 14
3 194
4 37634
5 1416317954 1416317954
6 2005956546822746114 111419319480
7 12414264753386307470398 75212031451
8 5656849674986213165399 42117743384
9 1773904307760475771454 134212256520
10 18012929800190282510398 54923239684
11 3016562257386112419854 61369726979
12 3766243389477000466439 100682126153
13 10136890526688606579407 46790825955
14 2189381393551101662023 120336432403
15 14480856963481788354407 15532303443
16 241252450245429654247 43487582705
17 1891169849524215117023 63215664337
18 3996220217568253649567 24881968247
19 619112343844716253007 36378170995
20 1323371324941459290023 23347868395
21 545122958590239876023 34319987212
22 1177861522231843532942 27325339261
23 746674165728748026119 67024860468
24 4492331920754869179022 67821607698
25 4599770470741412859202 45433743622
26 2064225059509625678882 32514699513
27 1057205684420682437167 51489094388
28 2651126840896373094542 44855569738
29 2012022136520581388642 31479590378
30 990964610366670182882 32455804440
31 1053379241847523713598 54840899833
32 3007524294493139427887 71222372297
33 5072626315612473056207 35230286592
34 1241173093354454974462 24416019713
35 596142018625604602367 80429963578
36 6468979041158406562082 117093979072

对了！ 12 117093979072

yangchuanju · 发表于 2024-8-24 05:04

ysr李彦会计算的M89、M107、M127的余数

M89=618970019642690137449562111，素性测试结果如下：
这是个素数4(1)
14(2)
194(3)
37634(4)
1416317954(5)
2005956546822746114(6)
598028640278675810224740676(7)
480114390397887436345871973(8)
256286478379806120980640370(9)
503856043838036255396725647(10)
511097357768708595775143636(11)
168909432968702305299180947(12)
606396047570974655444193748(13)
384259961875522880452984663(14)
400988785643977730394319793(15)
451946598706049129545781082(16)
519056096255902175211532475(17)
121085530627461043345077875(18)
71186560963388750687096830(19)
36000517785442762303479300(20)
523566428507141573725342798(21)
424152844029608571078391252(22)
451425083283677785701240528(23)
471604984152655775544654653(24)
149504332299367259583502770(25)
2661688372237296008669225(26)
14651690105229857026329789(27)
118366775657027743761992789(28)
78447114542527441733697497(29)
414825479001522844830957808(30)
140234396746501638380162556(31)
524724811145776165191705380(32)
454239684978083396425387798(33)
443190129321733552688414291(34)
193246662398964773806577169(35)
90276720159245463714588945(36)
325532186394213993941115709(37)
184428441183694588040637933(38)
20227257621080411005543513(39)
492178310326013754654519350(40)
98383234722633752804518339(41)
422539297718609229503207527(42)
239699647065516513819077229(43)
451540821309242236737612159(44)
386616582127510358048893037(45)
111015693969297793247714068(46)
526524283201479916042588129(47)
64862389039487459674212268(48)
222734658450663017797297098(49)
527979459006852476995019463(50)
597546382855243971575029724(51)
432108610907467792010713113(52)
267528776084781116062417378(53)
539136831481300028111816217(54)
451247597566784449829767505(55)
437168526145243171726687748(56)
598500912756632689317072800(57)
524692914241987400050525363(58)
332189870719179258780519572(59)
412661427218334854756142421(60)
321992305401224654215082066(61)
435970785565830723987708026(62)
381742226819095467298228805(63)
170103210134157444573479299(64)
529650761375006727395831727(65)
588636842041150882786657416(66)
532115895320758084925029926(67)
501541201809618824302560067(68)
339657887315362077441027847(69)
99498791857820493810407653(70)
267353229805674813483082782(71)
153775828163901691352640258(72)
645734370591155030147282(73)
239072406272077525999142496(74)
386211355975098724888629576(75)
589820547708179745896185533(76)
426471425099610829450724237(77)
14792991384462166970694984(78)
574596879853011245099388238(79)
269783273665984523074966550(80)
98263195276941167273641778(81)
288575740080467405879843347(82)
592120439037291200756916902(83)
248352176262993969312953851(84)
496815502059771466001738628(85)
309566686160249986820679689(86)
618970019642654953077473279(87)
0(88)

M107=162259276829213363391578010288127，素性测试结果如下：
这是个素数4(1)
14(2)
194(3)
37634(4)
1416317954(5)
2005956546822746114(6)
156120930203037441284156977127648(7)
152282864163660368507561255168699(8)
47447063325743411265488043955091(9)
43287419946592085122216771611854(10)
106477326326110909025981918810156(11)
122200248887230353105527523639491(12)
50073478326742071230643596151387(13)
9912018842522041816691947570056(14)
144082464553298142018801477786191(15)
127781097009807135354769843783776(16)
19865605180708016931827618234573(17)
126001631995377209250110255169626(18)
103243838630237208150182388486360(19)
2481353674900545210534841866705(20)
55151464703944115846884233853704(21)
46640632180243506476400131739360(22)
115502421482719876951998627283283(23)
101677279631846103912030626574990(24)
8135446140792271386405942601304(25)
38622534116872975383553690253955(26)
138687958258713295028352899050123(27)
101684766863586559292966101643524(28)
89041899733974281215131053478077(29)
138984160208051922360616592379759(30)
99401426611283177215508787148266(31)
81567083478699448160797146240296(32)
86172052844324193814322846796682(33)
115029899827700867874184426416093(34)
34577546807147649258106085957113(35)
27636075425625865458892944728269(36)
116300088085932994464683846957963(37)
66757088004907936741912803360332(38)
111215824090137511974979806285616(39)
157791670760860777359454827334058(40)
71076754939510086689558055872925(41)
82593123790529186151461606226271(42)
140194214821380925312038994078704(43)
124699805910449381729146324548104(44)
73160767872744201314362872678391(45)
108343652009015051652243262672592(46)
150606156954816655646541920048979(47)
104011373699404012445485246756557(48)
27239940835850812419441697006844(49)
61778276341233473507085733899401(50)
134311191866731143548202175648786(51)
10773861442571128428222274085141(52)
158430744480480682784702719931537(53)
104144454015966536007109390877727(54)
137601464755404943762959164710747(55)
97873030465277892718507046488834(56)
54231410178141160096912586172196(57)
160524880352550922678881225239016(58)
80847613439977397379341735887132(59)
25567630783628963035239643460063(60)
51338176873153842117224102923906(61)
103826792628657227657023228523894(62)
17056864661047888861147916452770(63)
9321666676951977236827522283068(64)
143256845526599710045452856450340(65)
137035107916901927508289839918463(66)
29840177088752954411017471600456(67)
86129626194819628502243747655237(68)
55184468067321898614231241736441(69)
64344131372416926245606406632607(70)
152176364258942830041434456900585(71)
136445594253029853465295553927851(72)
46831071480318038161030555544727(73)
29472271356397161700733621014507(74)
29357152428406980333013801620272(75)
130647207921043150645807424108405(76)
106228888764401589473264093711241(77)
127323762311616017529673676600762(78)
43735050168212562097104513670532(79)
70130088788222390767690350798246(80)
51092445406744440442366516667646(81)
150843123555709557929040292742624(82)
7652747622170452236856799619740(83)
105653258586684878088595227481071(84)
49347547747336851048974196013913(85)
68808590117594708118093045183215(86)
144898601279904501325597967868760(87)
105681379490430922177369804110299(88)
159395558630461774089147996588398(89)
95136647968461705280233431185735(90)
106617913398193797424286703522565(91)
25217198805366009868922082838849(92)
26281034528831210370193396922565(93)
88981258673257164977297813845933(94)
27816702692328723739074236836219(95)
134489675333911789595150351835450(96)
115713661048166756026066351464442(97)
22709260274860883065310761350350(98)
76944322811938710728002114616688(99)
72279541487735741305338513661757(100)
86289972368356120661214382381829(101)
87772691542774292677253091526913(102)
23437819630049688701809673541523(103)
123007059235929959534377495665976(104)
162259276829213345377179500806143(105)
0(106)

yangchuanju · 发表于 2024-8-24 05:05

本帖最后由 yangchuanju 于 2024-8-24 05:07 编辑

对M127的判断结果：
这是个素数余数14(1)
余数194(2)
余数37634(3)
余数1416317954(4)
余数2005956546822746114(5)
余数4023861667741036022825635656102100994(6)
余数148295852275705128589952510455019292911(7)
余数17934813421766634732012365957609373869(8)
余数85902463759488963702490017444612081724(9)
余数116475895319100247619106962527555061737(10)
余数49976279066382381059963127566460774395(11)
余数160668395611328156886231636609761589125(12)
余数94281146402315220816856494248417316624(13)
余数108007687823445325965842618064742685120(14)
余数31734492925565095550179541226941707640(15)
余数40502963312906587195023713454534295598(16)
余数94088105965254764875368473681747882892(17)
余数144493995864766378690749087262700586682(18)
余数20955297820352149233036565636331346012(19)
余数158915090152235934934479130912004389942(20)
余数52870398708381174466959392316679307296(21)
余数151490860312186869918440828859019512842(22)
余数95080894369933623491452109744508211636(23)
余数16832551656452962969322409924830603304(24)
余数50174049518004850581182191673210576861(25)
余数144336566379264365321651202616996055222(26)
余数130822199398052164937252409514558681721(27)
余数102532921936216636347982935976260898227(28)
余数113510945853789792879800143796642024867(29)
余数818764630715300415439121721750598757(30)
余数98873676748258741042292766411306359072(31)
余数115157140590183601330851495358050270577(32)
余数61932212331753972177049746744878494891(33)
余数162235341974786734396644569954762754962(34)
余数138222088850540840559618349986527965434(35)
余数12643335933642280592896036123803678462(36)
余数107874906898446614736459591766452551411(37)
余数105127310369349743611680099371735190865(38)
余数9288955258648756974993511313169148987(39)
余数22544078789156567134084495007232388871(40)
余数145330281715042877722945273276030728719(41)
余数2984059486841025471869552930115409684(42)
余数37572228739714097091268646718694828173(43)
余数137863838131209681188612129313912947511(44)
余数56951438527019760670940985275669549587(45)
余数33425539749822146052823924594117170181(46)
余数107032723030256277290622289200228566672(47)
余数53753380576481396758706859471945799623(48)
余数47099113889942965118806100149717565037(49)
余数99592518053374632198667753856515678006(50)
余数71264320053401377760498554706288870501(51)
余数93303582026251481068288102203876023525(52)
余数120228733067825856598036469060895809969(53)
余数118032048866201789290845587608054171643(54)
余数2650987091797688081935257855065994022(55)
余数145145919991993592884437642677980118562(56)
余数62997327855360484015702535758367792966(57)
余数83098680626625704955924126176100860767(58)
余数47102745120534589629594563604260423772(59)
余数23086037567407917159207583474834256176(60)
余数1648903944353085502350569803700249218(61)
余数146001941445125883362200107861188525242(62)
余数58072554876864005167998859270477790277(63)
余数85183974222777764635811000451869083253(64)
余数2178744815368192602929511049691246435(65)
余数142650016674409483015140356448611524239(66)
余数131180293024080215139431333296642157751(67)
余数23796400979692190167798559040061980681(68)
余数94691321662907057932605046718559371950(69)
余数28963125299159837855551115831455735161(70)
余数151145149675516943070949943379933758640(71)
余数76394190749566845285279900410093015143(72)
余数47725036928709433877841763022477907753(73)
余数104312534247659063865391654129512337576(74)
余数18945859719359721770108285233329380324(75)
余数164494116784207012462580689820261092953(76)
余数19312431404447051481513679243141178566(77)
余数27736528190775597167138586218006816402(78)
余数2300146040010405501321960790364494805(79)
余数148671707681260870148526487891403027688(80)
余数44689644596926350087083033086752357927(81)
余数114252518218238942159527597790043383515(82)
余数132347767817386283653136701980558442215(83)
余数82898165451862550147177322318323559762(84)
余数82550532064404830850169960592302750413(85)
余数75643059898515530266520341907002980339(86)
余数123982986142288470036528246058979625829(87)
余数82251894353697560270857485942566454845(88)
余数138612996512155828504361896311563427332(89)
余数38110442230077683457296715174480894554(90)
余数139824088758964839080901930176959179789(91)
余数91384193027872879688983922241190087851(92)
余数169520666637091361903503058366366526051(93)
余数169025277276139840475937137620617270244(94)
余数75767585679605360512739263520802144959(95)
余数49956247714329574425552443869563509087(96)
余数183690004880779837464570338561315540(97)
余数163703822629639553167738612906045835358(98)
余数169082445910970886147479859194469813067(99)
余数4415171566587865141382642765195174023(100)
余数110059221777184243569539344972552339165(101)
余数5064148876153793895511724877772701976(102)
余数26339871245616999480560619437480231895(103)
余数92058826383142394228174232088236221101(104)
余数25358529928264030171413979572591657174(105)
余数57391611503696291044494362875786761933(106)
余数4628408976566823773472049228202071599(107)
余数62888400681175191832847866264356373833(108)
余数83454791660308671184475704797189993564(109)
余数134424104788780027271116197574228580517(110)
余数15898780365670245164798848628558077094(111)
余数158133952358979283618604204477670831346(112)
余数6721506539191163416499937441762326133(113)
余数882594379818242655466533853441665046(114)
余数161925513938892243375929285060210027401(115)
余数80309984059206838477625980764275616860(116)
余数111061271103311825402106204765050643448(117)
余数8300180540889597001844078179358966103(118)
余数132515367850942399280896079195237732275(119)
余数46864209815407210576219476880150425377(120)
余数51366641762479717422620116634081008320(121)
余数142797848550190257259709111711506044974(122)
余数87676307088191859152273331489412200665(123)
余数18446744073709551616(124)
余数0(125)

yangchuanju · 发表于 2024-8-24 05:31

本帖最后由 yangchuanju 于 2024-8-24 05:41 编辑

对于2^11-1的检验余数，虽然没有0出现，但它的一系列余数是循环重复出现的，循环节长为60；
相当于一个正整数的倒数，小数部分是循环出现的，循环节长于正整数的素合性密切相关，
一个素数（2和5除外）的小数循环节长等于素数减1或素数减1的某个分数；
对于合数的小数循环节长度不等于合数减1或合数减1的某个分数（规律此处从略）；
由于2^11-1不是素数，它的余数循环节长60不是2047-1的分数，也不是两素因子减1的乘积（22*88=1936）的分数；它是指数11减1的6倍——

2^11-1 = 2047
序号平方减2 余数
0 4 ——
1 14 14
2 194 194
3 37634 788
4 620942 701
5 491399 119
6 14159 1877
7 3523127 240
8 57598 282
9 79522 1736
10 3013694 510
11 260098 129
12 16639 263
13 69167 1616
14 2611454 1529
15 2337839 165
16 27223 612
17 374542 1988
18 3952142 1432
19 2050622 1575
20 2480623 1706
21 2910434 1647
22 2712607 332
23 110222 1731
24 2996359 1598
25 2553602 993
26 986047 1440
27 2073598 2034
28 4137154 167
29 27887 1276
30 1628174 809
31 654479 1486
32 2208194 1528
33 2334782 1202
34 1444802 1667
35 2778887 1108
36 1227662 1509
37 2277079 815
38 664223 995
39 990023 1322
40 1747682 1591
41 2531279 1187
42 1408967 631
43 398159 1041
44 1083679 816
45 665854 579
46 335239 1578
47 2490082 930
48 864898 1064
49 1132094 103
50 10607 372
51 138382 1233
52 1520287 1413
53 1996567 742
54 550562 1966
55 3865154 418
56 174722 727
57 528527 401
58 160799 1133
59 1283687 218
60 47522 441
61 194479 14
62 194 194

yangchuanju · 发表于 2024-8-24 05:39

本帖最后由 yangchuanju 于 2024-8-24 05:42 编辑

同样，对于2^23-1的检验余数，虽然没有0出现，但它的一系列余数是循环重复出现的，循环节长为32340；
由于2^23-1不是素数，它的余数循环节长32340不是2^23-1的分数，也不是两素因子减1的乘积的分数；它是指数23减1的1470倍——

2^23-1 = 8388607
序号平方减2 余数
0 4 ——
1 14 14
2 194 194
3 37634 37634
4 1416317954 7031978
5 49448714592482 7033660
6 49472372995598 1176429
7 1383985192039 7643358
8 58420921516162 3179743
9 10110765546047 2694768
10 7261774573822 763525
11 582970425623 4182158
12 17490445536962 7004001
13 49056030007999 1531454
14 2345351354114 5888805
15 34678024328023 1140622
16 1301018546882 4321431
17 18674765887759 7041324
18 49580243672974 2756392
19 7597696857662 1280050
20 1638528002498 6563009
21 43073087134079 6107895
22 37306381331023 6243954
23 38986961554114 4552058
……
32340 49592031549919 4640502
32341 21534258812002 14
32342 194 194

yangchuanju · 发表于 2024-8-25 20:25

yangchuanju 发表于 2024-8-24 05:39
同样，对于2^23-1的检验余数，虽然没有0出现，但它的一系列余数是循环重复出现的，循环节长为32340；
由于 ...

2^29-1没有余数0，但余数也是呈循环出现的，
循环节长等于252，252是指数29-1=28的9倍数！

序号余数
0 4
1 14
2 194
3 37634
4 342576132
5 250734296
6 433300702
7 16341479
8 49808751
9 57936161
10 211467447
11 71320725
12 91230447
13 153832672
14 217471443
15 239636427
16 223645010
17 90243197
18 27374393
19 490737401
20 35441039
21 303927542
22 202574536
23 515018664
24 330289146
25 148819211
26 365171774
27 458738443
28 199330295
29 217157831
30 365610707
31 205405135
32 317470530
33 13499100
34 439327467
35 293025351
36 420244854
37 293151294
38 146474479
39 498007331
40 527112831
41 163640527
42 294933652
43 414826234
44 115794118
45 312487729
46 348806734
47 324490603
48 418045567
49 83070106
50 173600106
51 6683493
52 345144025
53 263275521
54 19172793
55 478659147
56 536843758
57 200414496
58 380885475
59 16768435
60 178292994
61 391814911
62 286721839
63 298197715
64 318769590
65 262559978
66 33622521
67 410359158
68 131113635
69 471550771
70 327730952
71 254420280
72 318305956
73 111099773
74 174297941
75 266873894
76 140858246
77 87037117
78 191193664
79 272893119
80 231939026
81 422244243
82 104537689
83 232100744
84 189829523
85 346556758
86 512534255
87 57472600
88 397090676
89 307682525
90 25901833
91 460732360
92 1621788
93 65723953
94 417843935
95 43576716
96 48397591
97 368970426
98 480796160
99 472783450
100 64968748
101 58605292
102 136890218
103 243961742
104 70486103
105 332645025
106 463952305
107 306208491
108 253384700
109 210634810
110 361277878
111 207582151
112 248977469
113 195254666
114 88657354
115 200051028
116 419198563
117 220849062
118 386273134
119 245811862
120 160327296
121 31773525
122 133819317
123 119325945
124 228256313
125 313068786
126 185417827
127 1099784
128 491555082
129 102704082
130 185263102
131 313782389
132 73922508
133 379492939
134 93288501
135 379524035
136 29251712
137 481333697
138 236257495
139 226042644
140 459452575
141 352763177
142 293759552
143 514700386
144 16209573
145 264289817
146 141187476
147 270453706
148 229696719
149 352119586
150 11232619
151 86192316
152 360853499
153 6230199
154 149585210
155 231056904
156 166444012
157 139330519
158 154828461
159 297538325
160 471352669
161 82169747
162 504165555
163 182846774
164 416899086
165 252859767
166 442333167
167 495912198
168 337310834
169 221465349
170 23850307
171 402082396
172 219431671
173 57986444
174 340333935
175 536176595
176 501500687
177 178646937
178 319036324
179 57205352
180 219729015
181 351934631
182 239861345
183 201184204
184 485509516
185 365736339
186 172908756
187 421620747
188 36414513
189 367690089
190 509705583
191 208374354
192 1741671
193 97225089
194 125697170
195 495243718
196 391104673
197 261450898
198 328618695
199 301292324
200 91137825
201 409216281
202 58699133
203 100277499
204 211921418
205 109164708
206 197581864
207 529158499
208 296886230
209 525772855
210 70061158
211 218184486
212 88050109
213 402534074
214 530359635
215 19306504
216 213129290
217 526974250
218 391171545
219 472004065
220 198636188
221 253540781
222 296126146
223 407108808
224 481355740
225 439889100
226 110259703
227 307350424
228 43466845
229 303715514
230 68176926
231 182841046
232 90489937
233 12377160
234 122695392
235 373367146
236 61510244
237 418496438
238 397334343
239 219375216
240 49627132
241 412876713
242 417666441
243 206031769
244 226523958
245 318723929
246 274912428
247 213997942
248 407164346
249 262594507
250 277816061
251 67096901
252 285716712
253 14
254 194
255 37634
256 342576132
……

yangchuanju · 发表于 2024-8-25 20:26

本帖最后由 yangchuanju 于 2024-8-25 20:33 编辑

yangchuanju 发表于 2024-8-24 05:39
同样，对于2^23-1的检验余数，虽然没有0出现，但它的一系列余数是循环重复出现的，循环节长为32340；
由于 ...

2^37-1也是合数，LL检验中没有余数0，各个余数也是呈循环出现的，然而笔者计算至10万，仍然没有在出现余数14、194等，可能认为它的循环节长大于10万！
循环节长等于252，252是指数29-1=28的9倍数！

序号余数
0 4
1 14
2 194
3 37634
4 1416317954
5 111419319480
6 75212031451
7 42117743384
8 134212256520
9 54923239684
10 61369726979
11 100682126153
12 46790825955
13 120336432403
14 15532303443
15 43487582705
16 63215664337
17 24881968247
18 36378170995
19 23347868395
20 34319987212
21 27325339261
22 67024860468
23 67821607698
24 45433743622
25 32514699513
26 51489094388
27 44855569738
28 31479590378
29 32455804440
30 54840899833
31 71222372297
32 35230286592
33 24416019713
34 80429963578
35 117093979072
36 31836395557
37 100730259915
…………
99999 104039998536
100000 136697964257

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