伪素数基本理论及伪素数的应用

yangchuanju · 发表于 2025-12-26 05:40

本帖最后由 yangchuanju 于 2025-12-26 18:11 编辑

伪素数基本理论及伪素数的应用
大于等于1的正整数可以分为素数（旧称质数）和合数；
少数合数貌似素数，被称之为“伪素数”，
进一步伪素数可分为费马伪素数、绝对伪素数（卡迈克尔数）、强伪素数、欧拉伪素数等。

费马伪素数，即一般的伪素数，常简称为伪素数。
费马伪素数是最早被发现和研究的伪素数，尤其是以2为基的伪素数，
通常中国古人相信若2^n≡2(mod n)，则n一定是素数。这个命题在1≤n≤340内是正确的。
然341=11*31是一个合数，确能够通过通过费马小定理的检验，2^341≡2(mod 341)，
341是一个最小的以2为基的伪素数。
伪素数比较稀少，但伪素数确有无穷多个，在1百亿（10的10次方）以内有14844个（百万分子1.48）。
类似的存在以3,4,5,6,7……为基的各种伪素数。
费马伪素数，特别是以3,5,7为基的伪素数中有较多的偶数、末尾是5的数，明眼人一看就知道它们不是素数，尽管它们也是某个整数基的伪素数。

yangchuanju · 发表于 2025-12-26 05:41

伪素数（费马伪素数）
令b是一个正整数，若n是一个正合数且b^n≡b (mod n)，亦或b^(n-1)≡1 (mod n)，则n称为以b为基的伪素数。
以2为基的伪素数有341,561,645,1105,1387等；
以3为基的伪素数有91,121,286,671,703等；
以4为基的伪素数有15,85,91,341,435等；
以5为基的伪素数有4,124,217,561,781等；
以6为基的伪素数有35,185,217,301,481等；
以7为基的伪素数有6,25,325,561,703等；

b=2 b=3 b=4 b=5 b=6 b=7
341 91 15 4 35 6
561 121 85 124 185 25
645 286 91 217 217 325
1105 671 341 561 301 561
1387 703 435 781 481 703
1729 949 451 1541 1105 817
1905 1105 561 1729 1111 1105
2047 1541 645 1891 1261 1825
2465 1729 703 2821 1333 2101
2701 1891 1105 4123 1729 2353

yangchuanju · 发表于 2025-12-26 05:51

绝对伪素数（卡迈克尔数）
一个合数n若对所有满足(b,n)=1的正整数b都有b^(n-1)≡1 (mod n)成立，则称之为卡迈克尔数，或者称之为绝对伪素数。
A002997给出最小的10000绝对伪素数
Carmichael numbers: composite numbers k such that a^(k-1) == 1 (mod k) for every a coprime to k.
卡迈尔数：对于每个与k互质的a，使得a^(k-1) == 1 (mod k)的合数k。
前100个最小的绝对伪素数是
1 561 21 172081 41 838201 61 2531845 81 5632705
2 1105 22 188461 42 852841 62 2628073 82 5968873
3 1729 23 252601 43 997633 63 2704801 83 6049681
4 2465 24 278545 44 1024651 64 3057601 84 6054985
5 2821 25 294409 45 1033669 65 3146221 85 6189121
6 6601 26 314821 46 1050985 66 3224065 86 6313681
7 8911 27 334153 47 1082809 67 3581761 87 6733693
8 10585 28 340561 48 1152271 68 3664585 88 6840001
9 15841 29 399001 49 1193221 69 3828001 89 6868261
10 29341 30 410041 50 1461241 70 4335241 90 7207201
11 41041 31 449065 51 1569457 71 4463641 91 7519441
12 46657 32 488881 52 1615681 72 4767841 92 7995169
13 52633 33 512461 53 1773289 73 4903921 93 8134561
14 62745 34 530881 54 1857241 74 4909177 94 8341201
15 63973 35 552721 55 1909001 75 5031181 95 8355841
16 75361 36 656601 56 2100901 76 5049001 96 8719309
17 101101 37 658801 57 2113921 77 5148001 97 8719921
18 115921 38 670033 58 2433601 78 5310721 98 8830801
19 126217 39 748657 59 2455921 79 5444489 99 8927101
20 162401 40 825265 60 2508013 80 5481451 100 9439201

yangchuanju · 发表于 2025-12-26 05:57

强伪素数
设n是一个合数，且通过以b为基的米勒检验，那么称n为以b为基的强伪素数。
米勒检验——一旦同余式b^(n-1)≡1 (mod n)得到验证，则n可能是素数，也可能是伪素数；
再考虑b^[(n-1)/2]模n的最小正剩余是否等于±1，若同余式不成立，则n是合数。
若b^[(n-1)/2]模n的最小正剩余等于±1，n也不一定是素数。
若n是素数，且正整数b不能被n整除，那么n能通过以b为基的米勒检验。
b=2 b=3 b=4 b=5 b=6 b=7
1 2047 1 121 1 341 1 781 1 217 1 25
2 3277 2 703 2 1387 2 1541 2 481 2 325
3 4033 3 1891 3 2047 3 5461 3 1111 3 703
4 4681 4 3281 4 3277 4 5611 4 1261 4 2101
5 8321 5 8401 5 4033 5 7813 5 2701 5 2353

以2和3为底的强伪素数。
Strong pseudoprimes to base 2 and 5.
Strong pseudoprimes to bases 3 and 5.
Strong pseudoprimes to bases 2, 3 and 5
Strong pseudoprimes to bases 2, 3, 5 and 7.
1 1373653 1 1907851 1 112141 1 25326001 1 3215031751
2 1530787 2 4181921 2 432821 2 161304001 2 118670087467
3 1987021 3 4469471 3 1024651 3 960946321 3 307768373641
4 2284453 4 5256091 4 1563151 4 1157839381 4 315962312077
5 3116107 5 9006401 5 1627921 5 3215031751 5 354864744877

yangchuanju · 发表于 2025-12-26 06:06

本帖最后由 yangchuanju 于 2025-12-26 13:28 编辑

欧拉伪素数
一个满足同余式b^(n-1)≡(b/n) (mod n)的奇正合数，称为以b为基的欧拉伪素数，其中b是正整数。
式中(b/n)是雅可比符号，正确写法是在一对高3行的大括号内第1行写b，第2行画一道横线，第3行写n。

每一个以b为基的欧拉伪素数都是以b为基的伪素数；
并非每个伪素数都是欧拉伪素数；
若n是以b为基的强伪素数，则n是以b为基的欧拉伪素数。

yangchuanju · 发表于 2025-12-26 07:41

本帖最后由 yangchuanju 于 2025-12-27 15:19 编辑

米勒素性检验
给定一个正整数n，将n-1分解成n-1=2^s*t，t是奇数，s是正整数；
令1≤j≤s-1，如果b^t≡1 (mod n)或者某个b^(t*2^j)≡-1 (mod n)成立，则称n通过了以b为基的米勒检验。

7——7-1=6=2*3，s=1，t=3，j=0，2^3 (mod 7)≡1，2^6 (mod 7)≡1，素数
11——11-1=10=2*5，s=1，t=5，j=0，2^5 (mod 11)≡-1，2^10 (mod 11)≡1，素数
13——13-1=12=4*3，s=2，t=3，j=1，2^3 (mod 13)≡8，2^6 (mod 13)≡-1，2^12 (mod 13)≡1，素数
17——17-1=16，s=4，t=1，j=123，2^2 (mod 17)≡4，2^4 (mod 17)≡-1，2^8 (mod 17)≡1，2^16 (mod 17)≡1，素数
19——19-1=18=2*9，s=1，t=9，j=0，2^9 (mod 19)≡-1，2^18 (mod 19)≡1，素数
23——23-1=22=2*11，s=1，t=11，j=0，2^11 (mod 23)≡1，2^22 (mod 23)≡1，素数
49——49-1=48=16*3，s=4，t=3，j=123，2^2 (mod 49)≡4，2^4 (mod 49)≡16，2^8 (mod 49)≡11，2^16 (mod 49)≡23，2^24 (mod 49)≠-1，2^48 (mod 49)≠1，合数
77——77-1=76=4*19，s=2，t=19，j=1，2^19 (mod 77)≡72，2^38 (mod 77)≡25，2^76 (mod 77)≡9≠1，合数

341——341-1=340=4*85=10*34，s=2，t=85，j=1，2^85 (mod 341)≡32，2^170 (mod 341)≡1，2^340 (mod 341)≡1，以2为基的伪素数
另有2^10 (mod 341=1，2^20,2^30,…,2^170,…2^340 (mod 341)≡1，以2为基的伪素数
j=1，2^85 (mod 341)≡32≠1，2^2 (mod 341)≡4≠1，没有通过以2为基的米勒检验，341不是以2为基的强伪素数。

1729——1729-1=1728=64*27=36*48，s=6,t=27,j=1 2 3 4 5，2^27 (mod 1729)≡645，2^54 (mod 1729)≡1065，2^108 (mod 1729)≡1，2^216,2^432,2^864,2^1728 (mod 1729)≡1，以2为基的伪素数
另有2^36 (mod 1729)≡1，2^72,2^108,…2^864,…2^1728 (mod 1729)≡1，以2为基的伪素数
j=1 2 3 4 5，2^2,2^4,2^6,2^8,2^10 (mod 1729)≡4,16,64,256,1024≠1，2^27 (mod 1729)≡645也不等于1，没有通过以2为基的米勒检验，1729不是以2为基的强伪素数。

2023——2^2022 (mod 2023)≡1968，2023不是素数
2027——2^2026 (mod 2027)≡1，2027是素数
2029——2^2028 (mod 2029)≡1，2029是素数
2033——2^2032 (mod 2033)≡1278，2033不是素数
2039——2^2038 (mod 2039)≡1，2039是素数
2041——2^2040 (mod 2041)≡14，2041不是素数

2047——2047-1=2046=2*1023=2*3*11*31，s=1，t=1023，j=0，2^1023 (mod 2047)≡1，2^2046 (mod 2047)≡1，2047可通过以2为基的米勒检验，是一个以2为基的强伪素数；
实际上2047是以2为基的最小强伪素数，在2047之前共有7个以2为基的伪素数——341,561,651,1105,1387,1729,1905，它们都不是强伪素数。

yangchuanju · 发表于 2025-12-26 08:32

本帖最后由 yangchuanju 于 2025-12-26 12:05 编辑

要判定一个正整数是不是素数，仅用米勒检验是不行的，尽管它对于2047以下的各个正整数是有效的；
有效的方法是用2,3；2,3,5；2,3,5,7；2,3,5,7,11；……联合检验——
单用素数2检验，仅能检验到2047以下；
改用素数2,3联合检验，可检验到1373653以下；
当用素数2,3,5联合检验，可检验到25326001以下；
当用素数2,3,5,7联合检验，可检验到3215031751以下；
当用素数2,3,5,7,11联合检验，可检验到2152302898747以下；
……
当用素数2,3,5,7,……41联合检验，可检验到3.317*10^24以下。

A014233给出用前13个素数联合检验得到的最小强伪素数
素数最小强伪素数分解式
2 1 2047 23*89
3 2 1373653 829*1657
5 3 25326001 2251*11251
7 4 3215031751 151*751*28351
11 5 2152302898747 6763*10627*29947
13 6 3474749660383 1303*16927*157543
17 7 341550071728321 10670053*32010157
19 8 341550071728321 10670053*32010157
23 9 3825123056546413051 149491*747451*34233211
29 10 3825123056546413051 149491*747451*34233211
31 11 3825123056546413051 149491*747451*34233211
37 12 318665857834031151167461 399165290221*798330580441
41 13 3317044064679887385961981 1287836182261*2575672364521

yangchuanju · 发表于 2025-12-26 12:32

本帖最后由 yangchuanju 于 2025-12-26 12:47 编辑

正整数素性检验法有——
1、尾数目测法：若一个十进制正整数，尾数是0,2,4,5,6,8的都不是素数（2,5除外）；
2、各位数字和判断法：若一个十进制正整数，它的各位数字和是3的倍数时它一定是素数3的倍数数，各位数字和是9的倍数时它一定是9的倍数数；
3、隔位数字和判断法：若一个十进制正整数，它的偶数位数字和与奇数位数字和相等或相差11,22,33……时它一定是素数11的倍数数；
4、试除法：对于一个正整数n，用它的平方根以内的素数从小到大逐个试除，若有某个小素数可整除n，则n是合数，否则n是素数；
5、费马（小定理）检验法：对于一个正整数n，选出所有的与n互素的正整数b（2≤b<n)，如果某个b^(n-1) (mod n)≠1，则n是合数；否则n是素数或是与b为基的伪素数；
6、米勒-拉宾素性检验法：参见以上相关楼层网页；
7、索洛未-斯特拉森概率素性检验法：这也是当今用于检验大整数素性的主要方法，待研究。

yangchuanju · 发表于 2025-12-26 12:49

本帖最后由 yangchuanju 于 2025-12-26 12:51 编辑

米勒-拉宾素性检验
AI智能回答
米勒-拉宾素性检验是一种用于判断大数是否为素数的概率算法，由加里·米勒和迈克尔·拉宾在1980年提出，基于费马定理和威尔逊定理。
该算法通过随机选择一个数作为证据来判断待测数是否为合数。如果待测数经过多次测试都被判定为素数，则有很大的概率确实为素数。具体步骤包括：将待测数n-1分解为2^k * m的形式，其中m是奇数；随机选择一个数a，计算a^(n-1) mod n；如果结果为1或n-1，则n有很大的概率为素数；否则，计算c = a^m mod n，并依次计算c = c^2 mod n，直到找到一个等于n-1的c值，或者完成所有计算。如果在所有计算中都没有找到等于n-1的c值，则n是合数。

米勒-拉宾素性检验的时间复杂度为O(k log^3 n)，其中k是测试次数。该算法在密码学领域有广泛应用，特别是在生成大素数方面，因为大素数在很多加密算法中是必需的。此外，学习该算法也有助于提高对数论的理解和分析算法复杂度的能力。

需要注意的是，米勒-拉宾素性检验是一种概率算法，因此存在一定的误判概率。然而，通过增加测试次数k，可以显著降低误判的概率。对于2^64以内的数，该算法可以确保不出错，并且运行速度较快。

yangchuanju · 发表于 2025-12-26 12:59

亦可用下列各个数字作为米勒-拉宾检验用表——
米勒-拉宾检验用表
n≤ 检验用素数
2047 2
1373653 2，3
9080191 31，73
25326001 2，3，5
4759123141 2，7，61
2152302898747 2，5，7，11
3474749660383 2，5，7，11，13
341550071728321 2，3，5，7，11，13，17
3825123056546413051 2，3，5，7，11，13，17，19

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