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

yangchuanju

索洛未-斯特拉森概率素性检验法
设n是正整数，从整数1,2,……n-1中随机选取k个整数b1,b2,……bk，对这些整数bj，（j=1,2,……k中的每一个）判定是否有
bj^(n-1)/2≡(bj/n) (mod n)
若这样的同余式都不成立，则n是合数；若n是素数，则同余式都成立。
若n是合数，则所有k个同余式都成立的概率小于1/2^k，
因此，当k足够大且通过这个检验时，整数n“几乎一定是素数”。
式中(bj/n)是雅可比符号，正确写法是在一对高3行的大括号内  第1行写b，第2行画一道横线，第3行写n。

因为每个以b为基的强伪素数也是有相同基的欧拉伪素数，所以通过索洛未-斯特拉森概率素性检验的合数比通过米勒-拉宾概率素性检验的合数多，尽管它们都需要O(k(log2 n)^3)次位运算。

yangchuanju

以2为基的6种伪素数表（前100个）
A001567        A002997        A001262        A006970        A033181        A047713
Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers.                                       
以2为底的费马伪素数，也称为萨鲁斯数或普洛伊数。                                       
        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。                               
                Strong pseudoprimes to base 2.                       
                以2为底的强伪素数。                       
                        Euler pseudoprimes: composite numbers n such that 2^((n-1)/2) == +-1 (mod n).               
                        以2为基的欧拉伪素数               
                                Absolute Euler pseudoprimes: odd composite numbers n such that a^((n-1)/2) == +-1 (mod n) for every a coprime to n.       
                                绝对欧拉伪素数：对于每个与n互质的a，使得a^((n-1)/2) == +-1 (mod n)的奇合数n。       
                                        Euler-Jacobi pseudoprimes: 2^((n-1)/2) == (2 / n) mod n, where (2 / n) is a Jacobi symbol.
                                        欧拉-雅可比伪素数：2^((n-1)/2) == (2 / n) mod n，其中 (2 / n) 是一个雅可比符号。
1 341        1 561        1 2047        1 341        1 1729        1 561
2 561        2 1105        2 3277        2 561        2 2465        2 1105
3 645        3 1729        3 4033        3 1105        3 15841        3 1729
4 1105        4 2465        4 4681        4 1729        4 41041        4 1905
5 1387        5 2821        5 8321        5 1905        5 46657        5 2047
6 1729        6 6601        6 15841        6 2047        6 75361        6 2465
7 1905        7 8911        7 29341        7 2465        7 162401        7 3277
8 2047        8 10585        8 42799        8 3277        8 172081        8 4033
9 2465        9 15841        9 49141        9 4033        9 399001        9 4681
10 2701        10 29341        10 52633        10 4681        10 449065        10 6601
11 2821        11 41041        11 65281        11 5461        11 488881        11 8321
12 3277        12 46657        12 74665        12 6601        12 530881        12 8481
13 4033        13 52633        13 80581        13 8321        13 656601        13 10585
14 4369        14 62745        14 85489        14 8481        14 670033        14 12801
15 4371        15 63973        15 88357        15 10261        15 838201        15 15841
16 4681        16 75361        16 90751        16 10585        16 997633        16 16705
17 5461        17 101101        17 104653        17 12801        17 1050985        17 18705
18 6601        18 115921        18 130561        18 15709        18 1615681        18 25761
19 7957        19 126217        19 196093        19 15841        19 1773289        19 29341
20 8321        20 162401        20 220729        20 16705        20 1857241        20 30121
21 8481        21 172081        21 233017        21 18705        21 2113921        21 33153
22 8911        22 188461        22 252601        22 25761        22 2433601        22 34945
23 10261        23 252601        23 253241        23 29341        23 2455921        23 41041
24 10585        24 278545        24 256999        24 30121        24 2704801        24 42799
25 11305        25 294409        25 271951        25 31621        25 3057601        25 46657
26 12801        26 314821        26 280601        26 33153        26 3224065        26 49141
27 13741        27 334153        27 314821        27 34945        27 3581761        27 52633
28 13747        28 340561        28 357761        28 41041        28 3664585        28 62745
29 13981        29 399001        29 390937        29 42799        29 3828001        29 65281
30 14491        30 410041        30 458989        30 46657        30 4463641        30 74665
31 15709        31 449065        31 476971        31 49141        31 4903921        31 75361
32 15841        32 488881        32 486737        32 49981        32 5148001        32 80581
33 16705        33 512461        33 489997        33 52633        33 5310721        33 85489
34 18705        34 530881        34 514447        34 62745        34 5968873        34 87249
35 18721        35 552721        35 580337        35 65077        35 6189121        35 88357
36 19951        36 656601        36 635401        36 65281        36 6840001        36 90751
37 23001        37 658801        37 647089        37 74665        37 7995169        37 104653
38 23377        38 670033        38 741751        38 75361        38 8355841        38 113201
39 25761        39 748657        39 800605        39 80581        39 8719921        39 115921
40 29341        40 825265        40 818201        40 83333        40 8830801        40 126217
41 30121        41 838201        41 838861        41 85489        41 9439201        41 129921
42 30889        42 852841        42 873181        42 87249        42 9582145        42 130561
43 31417        43 997633        43 877099        43 88357        43 9585541        43 149281
44 31609        44 1024651        44 916327        44 90751        44 9613297        44 158369
45 31621        45 1033669        45 976873        45 104653        45 9890881        45 162401
46 33153        46 1050985        46 983401        46 113201        46 10024561        46 164737
47 34945        47 1082809        47 1004653        47 115921        47 10402561        47 172081
48 35333        48 1152271        48 1016801        48 126217        48 11119105        48 188057
49 39865        49 1193221        49 1023121        49 129921        49 11205601        49 196093
50 41041        50 1461241        50 1082401        50 130561        50 12490201        50 208465
51 41665        51 1569457        51 1145257        51 137149        51 12945745        51 215265
52 42799        52 1615681        52 1194649        52 149281        52 13696033        52 220729
53 46657        53 1773289        53 1207361        53 158369        53 13992265        53 223345
54 49141        54 1857241        54 1251949        54 162401        54 14469841        54 233017
55 49981        55 1909001        55 1252697        55 164737        55 14676481        55 252601
56 52633        56 2100901        56 1302451        56 172081        56 15829633        56 253241
57 55245        57 2113921        57 1325843        57 176149        57 15888313        57 256999
58 57421        58 2433601        58 1357441        58 188057        58 16046641        58 266305
59 60701        59 2455921        59 1373653        59 194221        59 16778881        59 271951
60 60787        60 2508013        60 1397419        60 196093        60 17098369        60 278545
61 62745        61 2531845        61 1441091        61 208465        61 17236801        61 280601
62 63973        62 2628073        62 1493857        62 215265        62 17586361        62 294409
63 65077        63 2704801        63 1507963        63 215749        63 17812081        63 314821
64 65281        64 3057601        64 1509709        64 219781        64 19683001        64 323713
65 68101        65 3146221        65 1530787        65 220729        65 20964961        65 334153
66 72885        66 3224065        66 1678541        66 223345        66 23382529        66 340561
67 74665        67 3581761        67 1730977        67 233017        67 25603201        67 348161
68 75361        68 3664585        68 1811573        68 252601        68 26474581        68 357761
69 80581        69 3828001        69 1876393        69 253241        69 26921089        69 390937
70 83333        70 4335241        70 1907851        70 256999        70 29020321        70 399001
71 83665        71 4463641        71 1909001        71 266305        71 33302401        71 410041
72 85489        72 4767841        72 1969417        72 271951        72 33596641        72 427233
73 87249        73 4903921        73 1987021        73 276013        73 35571601        73 448921
74 88357        74 4909177        74 2004403        74 278545        74 36121345        74 449065
75 88561        75 5031181        75 2081713        75 280601        75 37167361        75 458989
76 90751        76 5049001        76 2181961        76 282133        76 37354465        76 476971
77 91001        77 5148001        77 2205967        77 294409        77 37964809        77 486737
78 93961        78 5310721        78 2264369        78 314821        78 38151361        78 488881
79 101101        79 5444489        79 2269093        79 323713        79 38624041        79 489997
80 104653        80 5481451        80 2284453        80 334153        80 40280065        80 493697
81 107185        81 5632705        81 2304167        81 340561        81 40430401        81 514447
82 113201        82 5968873        82 2387797        82 348161        82 40622401        82 526593
83 115921        83 6049681        83 2419385        83 357761        83 40917241        83 530881
84 121465        84 6054985        84 2510569        84 390937        84 41298985        84 552721
85 123251        85 6189121        85 2746477        85 399001        85 41341321        85 580337
86 126217        86 6313681        86 2748023        86 410041        86 41471521        86 588745
87 129889        87 6733693        87 2757241        87 427233        87 42490801        87 625921
88 129921        88 6840001        88 2811271        88 448921        88 43331401        88 635401
89 130561        89 6868261        89 2909197        89 449065        89 43584481        89 647089
90 137149        90 7207201        90 2953711        90 458989        90 44238481        90 656601
91 149281        91 7519441        91 2976487        91 476971        91 45318561        91 658801
92 150851        92 7995169        92 3090091        92 486737        92 45877861        92 665281
93 154101        93 8134561        93 3116107        93 488881        93 45890209        93 670033
94 157641        94 8341201        94 3125281        94 489997        94 46483633        94 683761
95 158369        95 8355841        95 3375041        95 493697        95 47006785        95 711361
96 162193        96 8719309        96 3400013        96 514447        96 48628801        96 721801
97 162401        97 8719921        97 3429037        97 526593        97 50201089        97 741751
98 164737        98 8830801        98 3539101        98 530881        98 53245921        98 745889
99 172081        99 8927101        99 3567481        99 534061        99 54767881        99 748657
100 176149        100 9439201        100 3581761        100 552721        100 55462177        100 800605

yangchuanju

以3,5,6,7,8,9为基的欧拉伪素数表（前100个）
A262051        A262052        A262053        A262054        A262055        A263239
（好似没有以4为基的欧拉伪素数）                                       
Euler pseudoprimes to base 3: composite integers such that abs(3^((n - 1)/2)) == 1 mod n.
以3为基的欧拉伪素数                                       
        Euler pseudoprimes to base 5: composite integers such that abs(5^((n - 1)/2)) == 1 mod n.                               
                Euler pseudoprimes to base 6: composite integers such that abs(6^((n - 1)/2)) == 1 mod n.                       
                        Euler pseudoprimes to base 7: composite integers such that abs(7^((n - 1)/2)) == 1 mod n.               
                                Euler pseudoprimes to base 8: composite integers such that abs(8^((n - 1)/2)) == 1 mod n.       
                                        Euler pseudoprimes to base 9: composite integers such that abs(9^((n - 1)/2)) == 1 mod n.
                                        以9为基的欧拉伪素数                                       
1 121        1 217        1 185        1 25        1 9        1 4
2 703        2 781        2 217        2 325        2 21        2 28
3 1541        3 1541        3 301        3 703        3 65        3 91
4 1729        4 1729        4 481        4 817        4 105        4 121
5 1891        5 5461        5 1111        5 1825        5 133        5 286
6 2465        6 5611        6 1261        6 2101        6 273        6 532
7 2821        7 6601        7 1333        7 2353        7 341        7 671
8 3281        8 7449        8 1729        8 2465        8 481        8 703
9 4961        9 7813        9 2465        9 3277        9 511        9 949
10 7381        10 11041        10 2701        10 4525        10 561        10 1036
11 8401        11 12801        11 3421        11 6697        11 585        11 1105
12 8911        12 13021        12 3565        12 8321        12 1001        12 1541
13 10585        13 13333        13 3589        13 10225        13 1105        13 1729
14 12403        14 14981        14 3913        14 11041        14 1281        14 1891
15 15457        15 15751        15 5713        15 11521        15 1417        15 2465
16 15841        16 15841        16 6533        16 12025        16 1541        16 2665
17 16531        17 16297        17 8365        17 13665        17 1661        17 2701
18 18721        18 21361        18 10585        18 14089        18 1729        18 2821
19 19345        19 23653        19 11041        19 19345        19 1905        19 3281
20 23521        20 24211        20 11137        20 20197        20 2047        20 3367
21 24661        21 25351        21 12209        21 20417        21 2465        21 3751
22 28009        22 29539        22 14701        22 20425        22 2501        22 4636
23 29341        23 30673        23 15841        23 25829        23 3201        23 4961
24 30857        24 38081        24 17329        24 29857        24 3277        24 5551
25 31621        25 40501        25 18361        25 29891        25 3641        25 6364
26 31697        26 41041        26 20017        26 35425        26 4033        26 6601
27 41041        27 44173        27 21049        27 38081        27 4097        27 7381
28 44287        28 44801        28 22049        28 39331        28 4641        28 8401
29 46657        29 46657        29 29341        29 46657        29 4681        29 8911
30 47197        30 47641        30 31021        30 49241        30 4921        30 10585
31 49141        31 48133        31 31621        31 49321        31 5461        31 11011
32 50881        32 53971        32 34441        32 50881        32 6305        32 11476
33 52633        33 56033        33 36301        33 58825        33 6533        33 12403
34 55969        34 67921        34 38081        34 64681        34 6601        34 14383
35 63139        35 75361        35 39305        35 75241        35 7161        35 15203
36 63973        36 79381        36 39493        36 75361        36 8321        36 15457
37 72041        37 90241        37 41041        37 76627        37 8481        37 15841
38 74593        38 98173        38 43621        38 78937        38 9265        38 16471
39 75361        39 100651        39 44801        39 79381        39 9709        39 16531
40 79003        40 102311        40 46657        40 87673        40 10261        40 18721
41 82513        41 104721        41 46873        41 88399        41 10585        41 19345
42 83333        42 106201        42 48133        42 88831        42 10745        42 19684
43 87913        43 106561        43 49141        43 89961        43 11041        43 23521
44 88573        44 112141        44 49321        44 92929        44 12545        44 24046
45 93961        45 113201        45 49661        45 97921        45 12801        45 24661
46 97567        46 115921        46 52633        46 102943        46 13333        46 24727
47 105163        47 121463        47 54481        47 109061        47 13833        47 28009
48 111361        48 130417        48 56033        48 126673        48 14497        48 29161
49 112141        49 131977        49 58969        49 128161        49 14981        49 29341
50 115921        50 133141        50 74023        50 132193        50 15665        50 30857
51 125665        51 135201        51 74563        51 137257        51 15709        51 31621
52 126217        52 136137        52 75361        52 144901        52 15841        52 31697
53 138481        53 141361        53 76921        53 149171        53 16589        53 32791
54 148417        54 146611        54 82937        54 157681        54 16705        54 38503
55 152551        55 158401        55 83333        55 162401        55 16881        55 40132
56 162401        56 162401        56 83665        56 173951        56 17865        56 41041
57 172081        57 172081        57 87061        57 177025        57 18705        57 44287
58 182527        58 177661        58 88561        58 178709        58 19345        58 46657
59 184705        59 179893        59 92053        59 188191        59 19561        59 46999
60 188191        60 188113        60 94657        60 188501        60 20801        60 47197
61 188461        61 190513        61 94697        61 197633        61 23241        61 49051
62 192713        62 192001        62 97751        62 212201        62 24311        62 49141
63 192865        63 193249        63 97921        63 219781        63 24929        63 50881
64 194545        64 195313        64 104377        64 227767        64 25761        64 52633
65 204001        65 197633        65 106561        65 229633        65 29341        65 53131
66 206981        66 211951        66 109061        66 231793        66 30121        66 55261
67 211411        67 216457        67 115669        67 240577        67 31621        67 55969
68 218791        68 222301        68 115921        68 243277        68 32865        68 63139
69 221761        69 244569        69 124073        69 245281        69 33153        69 63973
70 226801        70 251521        70 125563        70 259093        70 33201        70 65485
71 228073        71 252601        71 125809        71 289441        71 34881        71 68887
72 238465        72 267977        72 126217        72 296241        72 34945        72 72041
73 239701        73 289081        73 128627        73 302177        73 35113        73 74593
74 258017        74 290629        74 133141        74 314821        74 37401        74 75361
75 278221        75 298271        75 151387        75 317251        75 37901        75 76627
76 282133        76 315121        76 162401        76 344641        76 38081        76 79003
77 288163        77 315283        77 164081        77 350065        77 40833        77 80956
78 293401        78 318551        78 171361        78 352225        78 41041        78 82513
79 294409        79 319507        79 172081        79 359341        79 41441        79 83333
80 313447        80 326929        80 173377        80 377719        80 42799        80 83665
81 314821        81 334153        81 178777        81 380281        81 43745        81 87913
82 320167        82 334657        82 178945        82 383531        82 45761        82 88561
83 327781        83 341531        83 180901        83 385003        83 46657        83 88573
84 328021        84 342361        84 181949        84 385201        84 48133        84 88831
85 334153        85 347777        85 188501        85 392977        85 49141        85 90751
86 340033        86 353827        86 193285        86 394957        86 49601        86 93961
87 341341        87 360533        87 207929        87 399001        87 49981        87 96139
88 359341        88 375601        88 208681        88 402305        88 50881        88 97567
89 359369        89 399001        89 216001        89 407809        89 52429        89 101101
90 364231        90 401401        90 224497        90 435601        90 52521        90 104653
91 365713        91 406901        91 228241        91 443311        91 52633        91 105163
92 385003        92 407353        92 247969        92 449065        92 52801        92 107185
93 385201        93 412933        93 256961        93 454129        93 54161        93 111361
94 399001        94 416641        94 268397        94 481601        94 55537        94 112141
95 402721        95 421637        95 282133        95 485357        95 55969        95 115921
96 416641        96 432821        96 289441        96 488881        96 56033        96 125665
97 432821        97 453331        97 290629        97 491063        97 57681        97 126217
98 443713        98 464881        98 293281        98 491209        98 59291        98 138481
99 449065        99 470009        99 294409        99 494241        99 59641        99 141391
100 453259        100 486157        100 295121        100 526825        100 61337        100 142901

太阳

太阳

已知:\(a^2b^3+ab^4+ab^2c+2ab^2+2abc+ab+5b^2c=2k\)
\(m^2t^3+mt^4+mt^2y+2mt^2+2mty+mt+5t^2y=3k\)，\(|b|=|t|=k\)
整数\(a\ne0\)，\(b\ne0\)，\(c\ne0\)，\(m\ne0\)，\(t\ne0\)，\(y\ne0\)，奇数\(k＞1\)，素数\(p＞0\)
求证:\(k=p\)
两个方程有整数解，判断素数提高精确度，判断这两个方程是否有整数解？难度大，很难判断有整数解

太阳

14＃，15＃，命题意义重大，值的收藏和研究

太阳

15＃，找到一个反例，可以忽略不记，k=9

yangchuanju

请验证341是一个以2为基的费马伪素数！
验：2^1,2^2,2^3,…2^10 (mod 341)=2,4,8,16,32,64,128,256,171,1;
2^10,2^20,2^30,…2^340 (mod 341)=1;
故341是一个以2为基的费马伪素数。

请验证561是一个以2为基的费马伪素数！
验：2^1,2^2,2^3,…2^40 (mod 561)=2,4,8,...1;
2^40,2^80,2^120,…2^560 (mod 561)=1;
故561是一个以2为基的费马伪素数。

请验证91是一个以3为基的费马伪素数！
验：3^1,3^2,3^3,…3^6 (mod 91)=3,9,27,81,61,1;
3^6,3^12,3^18,…3^90 (mod 91)=1;
故91是一个以3为基的费马伪素数。

请验证341也是一个以4为基的费马伪素数！
验：4^1,4^2,4^3,4^4,4^5 (mod 341)=4,16,64,256,1;
4^5,4^10,4^15,…4^340 (mod 341)=1;
故341是一个以4为基的费马伪素数。

yangchuanju

请用费马法判定553是不是素数！
解：2^1,2^2,2^3,…2^39 (mod 553)=2,4,8,…1;
2^39,2^78,2^117,…2^546 (mod 553)=1;
2^552 (mod 553)=64≠1,553不是素数。

请用费马法判定563是不是素数！
解：2^1,2^2,2^3,…2^281 (mod 563)=2,4,8,…562;
2^281 (mod 563)=562，2^562 (mod 563)=1，
563是素数。（尚需排除563不是费马伪素数，才能最终确定563确实是素数）

yangchuanju

请验证561是一个绝对伪素数（卡迈克尔数）！
验：与561互素的互素数有2,4,5,7,8,10,13,14,16,19…559,560；（没有3,11,17的倍数数）
2^1,2^2,2^3,…2^40 (mod 561)=2,4,8,...1;2^40,2^80,2^120,…2^560 (mod 561)=1;
4^560,5^560,7^560,8^560,…2^560  (mod 561)=1;
故561是应该绝对伪素数。

请验证341不是一个以3为基的费马伪素数！
验：3^1,3^2,3^3,…3^30 (mod 341)=3,9,27,...1;
3^30,3^60,3^90,…3^330 (mod 341)=1;3^340 (mod 341)=56≠1；
故341不是一个以3为基的费马伪素数。

请验证341不是一个以2为基的强伪素数！
要验证一个整数是不是强伪素数，需要用米勒法检验，
341-1=340=2^2*85,s=2,t=85,j=1;
2^(2^j)=2^2 (mod 341)=4≠-1；2^85 (mod 341)=32≠1；通不过米勒检验，故341不是一个以2为基的强伪素数。