太阳先生所要的大素数在这里

yangchuanju · 发表于 2023-5-4 12:24

本帖最后由 yangchuanju 于 2023-5-4 12:29 编辑

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)

【附注】r(k)、r(k+1)、M(p)小括号中的字母是“下标”。

yangchuanju · 发表于 2023-5-4 12:24

本帖最后由 yangchuanju 于 2023-5-4 12:34 编辑

卢卡斯-莱默素性测试(Lucas-Lehmer testing)
如果 P > 2， 2^P-1 是素数当且仅当 SP-2 = 0，其中，S0 = 4，Sn = (Sn-1^2 - 2) mod (2^P-1)
例如，证明 2^7 - 1＝127 是素数的过程如下：
S0 = 4
S1 = (4 * 4 - 2) mod 127 = 14
S2 = (14 * 14 - 2) mod 127 = 67
S3 = (67 * 67 - 2) mod 127 = 42
S4 = (42 * 42 - 2) mod 127 = 111
S5 = (111 * 111 - 2) mod 127 = 0
看起来，非常简单。

【附注】文中SP、S0、Sn、Sn-1中的P、0、n、n-1都是“下标”。

yangchuanju · 发表于 2023-5-4 12:38

本帖最后由 yangchuanju 于 2023-5-4 12:42 编辑

卢卡斯-莱默素性测试(Lucas-Lehmer testing)
p 3 5 7 11 13 17 19
2^p-1 7 31 127 2047 8191 131071 524287
1 4 4 4 4 4 4 4
2 0 14 14 14 14 14 14
3 —— 8 67 194 194 194 194
4 —— 0 42 788 4870 37634 37634
5 —— —— 111 701 3953 95799 218767
6 —— —— 0 119 5970 119121 510066
7 —— —— —— 1877 1857 66179 386344
8 —— —— —— 240 36 53645 323156
9 —— —— —— 282 1294 122218 218526
10 —— —— —— 1736 3470 126220 504140
11 —— —— —— —— 128 70490 103469
12 —— —— —— —— 0 69559 417706
13 —— —— —— —— —— 99585 307417
14 —— —— —— —— —— 78221 382989
15 —— —— —— —— —— 130559 275842
16 —— —— —— —— —— 0 85226
17 —— —— —— —— —— —— 523263
18 —— —— —— —— —— —— 0

yangchuanju · 发表于 2023-5-4 12:42

本帖最后由 yangchuanju 于 2023-5-4 12:45 编辑

卢卡斯-莱默素性测试(Lucas-Lehmer testing)
p 23 29 31
2^p-1 8388607 536870911 2147483647
1 4 4 4
2 14 14 14
3 194 194 194
4 37634 37634 37634
5 7031978 342576132 1416317954
6 7033660 250734296 669670838
7 1176429 433300702 1937259419
8 7643358 16341479 425413602
9 3179743 49808751 842014276
10 2694768 57936161 12692426
11 763525 211467447 2044502122
12 4182158 71320725 1119438707
13 7004001 91230447 1190075270
14 1531454 153832672 1450757861
15 5888805 217471443 877666528
16 1140622 239636427 630853853
17 4321431 223645010 940321271
18 7041324 90243197 512995887
19 2756392 27374393 692931217
20 1280050 490737401 1883625615
21 6563009 35441039 1992425718
22 6107895 303927542 721929267
23 6243954 202574536 27220594
24 4552058 515018664 1570086542
25 5402421 330289146 1676390412
26 7870419 148819211 1159251674
27 7881879 365171774 211987665
28 6394319 458738443 1181536708
29 3441923 199330295 65536
30 6924963 217157831 0

若2^p-1是一个素数，则用L-L检验法，
检验至第p-1次时余数为0；
p=3——2次；p=5——4次；p=7——6次皆为0，3个素数；
p=11——第10次不为0，2^11-1不是素数；
p=13——12次；p=17——16次；p=19——18次皆为0，3个素数；
p=23——第22次不为0，2^23-1不是素数；
p=29——第28次不为0，2^29-1不是素数；但在直接平方减2时因平方数超大导致模余数出现了错误；
p=31——开始时第30次不为0，是因为直接平方减2时因平方数超大导致模余数出现了错误；后分列处理后才得到正确的余数0。

yangchuanju · 发表于 2023-5-4 12:47

梅森素数的判定
若合数Mp=2^p-1=m*n，m是较小的素数，则m≡1(mod p)；若m≡1(mod p)，对于每一个小于√ (Mp)的素数m，m不整除Mp，则Mp=2^p-1是素数。
若m≡1(mod p)，p＜m≤√ (Mp)不存在素数m，则Mp=2^p-1是素数。
根据费马小定理，(2，p)=1，2^(p-1) ≡1(mod p)，则2^p≡2(mod p)，则2^p-1≡1(mod p)。
也就是说小于p的素数都不能整除Mp=2^p-1，所以只用验证p＜m≤√ (Mp)就行了。

例如：1、M11=2^11-1=23×89，23≡1(mod 11)，其它梅森合数自已验证。
2、M13=2^13-1=8191是一个素数。
证明：设m=13k+1，13k+1<√ (8191)，k=1、2、3、4、5、6，k=4或6时m是素数，m=13k+1=53或m=13k+1=79，但是53不整除8191，79 不整除8191，所以8191是一个素数。
3、M7=2^7-1=127是一个素数
设m=7k+1，7k+1＜√ (127)，k=1，m=7k+1=8不是素数，也就是说p＜m≤√ (Mp)内没有素数m，所以M7=2^7-1=127是一个素数。

原文来自网络，作者和出处不详。原文为图片，译者根据原文进行了改写。

太阳 · 发表于 2023-5-4 16:39

已知:奇数\(a＞0\)，\(c＞0\)，\(a＝3c\)，\(k＞0\)，\(\frac{4^a+2^a+1}{73}\ne k\)，\(t＞a^2m^2\)
\(\left( 4^a+2^a+1\right)\)的最小质因数是\(m\)，\(\frac{4^a+2^a+1}{m}\)的最小质因数是\(t\)
\(\frac{4^a+2^a+1}{mt}\)的最大质因数是\(y\)
求证:\(y＞\sqrt{\frac{4^a+2^a+1}{mt}}\)
已知:偶数\(a＞0\)，\(c＞0\)，\(m＞0\)，\(t＞0\)，\(a＝c^2\)，\(a\ne m\)
方程\(\frac{\left( 2^a+1\right)^2+3}{\left( 2^m+1\right)^2+3}＝t\)，有唯一的正整数解，\(\sqrt{a}＝m\)
\(\frac{\left( 2^a+1\right)^2+3}{\left( 2^m+1\right)^2+3}\)的最大质因数是\(y\)
求证:\(y＞\sqrt{\frac{\left( 2^a+1\right)^2+3}{\left( 2^m+1\right)^2+3}}\)

太阳 · 发表于 2023-5-4 19:37

已知：奇数\(a＞0\)，\(c＞0\)，\(a＝3c\)，\(k＞0\)，\(\frac{4^a+2^a+1}{73}\ne k\)，\(t＞a^2m^2\)
\(\left( 4^a+2^a+1\right)\)的最小质因数是\(m\)，\(\frac{4^a+2^a+1}{m}\)的最小质因数是\(t\)
\(\frac{4^a+2^a+1}{mt}\)的最大质因数是\(y\)
求证:\(y＞\sqrt{\frac{4^a+2^a+1}{mt}}\)
已知：偶数\(a＞0\)，\(c＞0\)，\(m＞0\)，\(t＞0\)，\(a＝c^2\)，\(a\ne m\)
方程\(\frac{\left( 2^a+1\right)^2+3}{\left( 2^m+1\right)^2+3}＝t\)，有唯一的正整数解，\(\sqrt{a}＝m\)
\(\frac{\left( 2^a+1\right)^2+3}{\left( 2^m+1\right)^2+3}\)的最大质因数是\(y\)
求证:\(y＞\sqrt{\frac{\left( 2^a+1\right)^2+3}{\left( 2^m+1\right)^2+3}}\)
例1：\(a＝81\)，\(\frac{4^{81}+2^{81}+1}{73}\ne k\)
\(\left( 4^{81}+2^{81}+1\right)\)的最小质因数是487
\(\frac{4^{81}+2^{81}+1}{487}\)的最小质因数是16753783618801
\(\frac{4^{81}+2^{81}+1}{487\times16753783618801}\)的最大质因数是3712990163251158343＞\(\sqrt{\frac{4^{81}+2^{81}+1}{487\times3712990163251158343}}\)
例2：\(a＝100\)，\(m\ne100\)，方程\(\frac{\left( 2^a+1\right)^2+3}{\left( 2^m+1\right)^2+3}＝t\)，有唯一的正整数解，\(\sqrt{a}＝m＝10\)
\(\frac{\left( 2^{100}+1\right)^2+3}{\left( 2^{10}+1\right)^2+3}\)的最大质因数是170886618823141738081830950807292771648313599433＞\(\sqrt{\frac{\left( 2^{100}+1\right)^2+3}{\left( 2^{10}+1\right)^2+3}}\)

太阳 · 发表于 2023-5-4 19:46

例3：\(a＝405\)，\(\frac{4^{405}+2^{405}+1}{73}\ne k\)
\(\left( 4^{405}+2^{405}+1\right)\)的最小质因数是487
\(\frac{4^{405}+2^{405}+1}{487}\)的最小质因数是49677578641
\(\frac{4^{405}+2^{405}+1}{487\times49677578641}\)的最大质因数是35587730061651572813645091915392646587500419941226352943003407923114622009461764361082185123933692044046427168174533156579030041＞\(\sqrt{\frac{4^{405}+2^{405}+1}{487\times49677578641}}\)

wlc1 · 发表于 2023-5-10 20:11

yangchuanju · 发表于 2023-5-10 21:07

wlc1 发表于 2023-5-10 20:11

多谢wlc1、cz1两位老师的点赞和加分！
再次谢谢！

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

太阳先生所要的大素数在这里

评分