能通过2，3，5，7的检验的合数

无心人

是的
这就是我想得到32位内结果的原因
现在想来

有点困难了
呵呵

不过如果能得到其分布的规律，且计算出其大概的个数
我想，在个数不超过100万的情况下，还是可以计算的

我倾向于其个数少于100万

medie2005

不如讨论如何求对特定测试基的强伪素数。
比如求2-pseudoprimes，(2,3)-pseudoprimes 。
改进一下10^16这个上限。

无心人

小范围容易
大范围虽有理论
但很难快速筛选

mathe

这个$10^32$内的解我觉得还是很难的.但是$10^16$以内完全自己来计算应该问题不大.
我们假设这个伪素数含有一个素数幂的因子$p^a$,我们可以事先计算出2,3,5,7关于$p^a$的阶$D(2,p^a),D(3,p^a),D(5,p^a),D(7,p^a)$以及它们最小公倍数$D(p^a)$,这个数字应该是$phi(p^a)$的一个因子,而且通常应该非常接近$phi(p^a)$.如果设伪素数为$p^a*u$
那么我们得到$u=1/{p^a} (mod D(p^a))$,这样,相对来说我们需要搜索的范围就可以小很多了.不过由于结果可以是两个大素数的乘积,对于$10^32$以内的解,由于很难构造$10^16$以内的完全素数表,解决这个问题会很难.

liangbch

最终发现，自己其实对这个题目的了解很是有限，为3楼的发言致歉。
下面是从网上搜索到的关于这个题目中的一些概念，转发于此。
转自 http://www.readfree.net/bbs/read.php?tid=291982&page=e&fpage=1

米勒(Miller)测试：
设 n 属于正整数, n-1 = 2^s * t, s 属于正整数, t 是奇数, (n,b)=1. 若 b^t == 1 mod n 或 b^(2^j * t) == -1 mod n (1 <= j <= s-1), 则称 n 通过以 b 为底的米勒测试。

若 n 是素数，且 b 不能被 n 整除，则 n 通过以 b 为底的米勒测试，反之则未必。

强伪素数：
若合数 n 通过以 b 为底的米勒测试，则称 n 是以 b 为底的强伪素数。

强伪素数十分罕见，但却有无穷多个。以 2 为底的最小强伪素数是 2047, 以 2 和 3 为底的最小强伪素数是 1373653, 以 2, 3 和 5 为底的最小强伪素数是25326001, 以 2, 3 , 5 和 7 为底的最小强伪素数是 3215031751.

medie2005

改进五元组测试基试验,得到的结果如下:
find base 11 fail at 2152302898747
find base 61 fail at 10087771603687
find base 241 fail at 15070413782971
find base 3079 fail at 16915961179981
find base 8521 fail at 22749134240827
find base 11239 fail at 52657210792621
find base 27017 fail at 61995910815541
find base 204793 fail at 73288774103581
find base 1446191 fail at 74205496883251
find base 3439829 fail at 99050370260227

于是,找到了两个比较好的五元组测试基(2,3,5,7,1446191),(2,3,5,7,3439829).

medie2005

对(2,3,7,61,x) ,得到结果如下:
find base 5564869 fail at 49110566041153
find base 8771647 fail at 63182894336857
找到两个五元组测试基(2,3,7,61,5564869),(2,3,7,61,8771647).

medie2005

对测试基（2, 3, 7, 61, 24251），我这边用我自己实现的Miller-Rabin测试，在10^16内竟然找到了120个误判，而http://math.crg4.com/primes.html里却是测试基（2, 3, 7, 61, 24251）在10^16内只有一个误判。

是我的代码有错？
Miller-Rabin测试的代码如下：

1. __int64 TEMP=65536, Limit=TEMP*TEMP/2;
   
2. 
   
3. __int64 MultiModular( __int64 a, __int64 b, __int64 mod ){
   
4.         __int64 r=0, t=a%mod;
   
5.         while( b>0 ){
   
6.                 if( (b&1) && (r=r+t)>mod ) r-=mod;
   
7.                 if( (t<<=1)>mod )  t-=mod;
   
8.                 b>>=1;
   
9.         }
   
10.         return r;
    
11. }
    
12. __int64  PowModular( __int64 base, __int64 n, __int64 mod ){
    
13.         __int64 s=1, t=base, u=n;
    
14.         while(u){
    
15.                 if(u&1)
    
16.                         s=(s>=Limit || t>=Limit)? MultiModular( s, t, mod ) : (s*t)%mod;
    
17.                 u>>=1;
    
18.                 t=(t>=Limit)? MultiModular( t, t, mod ) : (t*t)%mod;
    
19.         }
    
20.         return s;
    
21. }
    
22. bool  Miller_Rabin_Test( __int64 n ){
    
23.         int base[]={2,3,7,61,24251},base_num=sizeof(base)/sizeof(base[0]);
    
24.         __int64 t=n-1;
    
25.         int     s=0;
    
26.         while( (t&1)==0 ) t>>=1, ++s;
    
27.         for( int i=0; i<base_num; ++i ){
    
28.                 if( n==base[i] )  return true;
    
29.                 __int64 r=PowModular( base[i], t, n );
    
30.                 if( r==1 ) continue;
    
31.                 int j;
    
32.                 for( j=0; j<s; ++j ){
    
33.                         if( r==n-1 ) break;
    
34.                         r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
    
35.                 }
    
36.                 if( j<s ) continue;
    
37.                 return false;
    
38.         }
    
39.         return true;
    
40. }

复制代码

请各位给找找错。或者，请哪位提供一个正确的Miller-Rabin测试算法的代码。

gxqcn

请把误判的数据罗列出来，
我抽空用我的程序去验证一下，
先判断你们是谁的问题，
然后再确定问题出在哪里。

medie2005

0 : fail at 669094855201
1 : fail at 1052516956501
2 : fail at 2007193456621
3 : fail at 2744715551581
4 : fail at 9542968210729
5 : fail at 17699592963781
6 : fail at 19671510288601
7 : fail at 24983920772821
8 : fail at 24984938689453
9 : fail at 29661584268781
10 : fail at 37473222618541
11 : fail at 46856248255981
12 : fail at 47922612926653
13 : fail at 48103703944453
14 : fail at 49110566041153
15 : fail at 49752242681221
16 : fail at 91206655032481
17 : fail at 91481980096033
18 : fail at 119034193492321
19 : fail at 123645258399601
20 : fail at 128928036060253
21 : fail at 137364148720147
22 : fail at 150753857310253
23 : fail at 153131886327421
24 : fail at 155216912613121
25 : fail at 185610214763821
26 : fail at 224334357392701
27 : fail at 227752294950181
28 : fail at 230058334559041
29 : fail at 304562854940401
30 : fail at 306001576998253
31 : fail at 335788261073821
32 : fail at 377133492079081
33 : fail at 379242177424951
34 : fail at 389970770948461
35 : fail at 397319638319521
36 : fail at 448114903362253
37 : fail at 523235160050221
38 : fail at 628999496281621
39 : fail at 699349238838253
40 : fail at 746667678235753
41 : fail at 790198268451301
42 : fail at 794036495175661
43 : fail at 823820871230281
44 : fail at 867739535711821
45 : fail at 1039918661294761
46 : fail at 1099127938585141
47 : fail at 1104388025338153
48 : fail at 1173374598605653
49 : fail at 1262797719066157
50 : fail at 1265872947674653
51 : fail at 1325898212229667
52 : fail at 1327034517143653
53 : fail at 1418575746675583
54 : fail at 1666122072463621
55 : fail at 1837400535259453
56 : fail at 1857422490084961
57 : fail at 1870756820971741
58 : fail at 1914550540480717
59 : fail at 2018963273468221
60 : fail at 2163829000939453
61 : fail at 2206020317369221
62 : fail at 2301037384029121
63 : fail at 2416062055125421
64 : fail at 2435076500074921
65 : fail at 2545656135020833
66 : fail at 2594428516569781
67 : fail at 2669983768115821
68 : fail at 2690937050990653
69 : fail at 2758640869506607
70 : fail at 2833525461416653
71 : fail at 2876662942007221
72 : fail at 2932155806957821
73 : fail at 2957010595723801
74 : fail at 3183606449929153
75 : fail at 3220133449185901
76 : fail at 3424103775720253
77 : fail at 3625360152399541
78 : fail at 3939300299037421
79 : fail at 3947917710714841
80 : fail at 3980273496750253
81 : fail at 4182256679324041
82 : fail at 4450605887818261
83 : fail at 4727893739521501
84 : fail at 4750350311306953
85 : fail at 4755334362931153
86 : fail at 5756440863559753
87 : fail at 5760976603475341
88 : fail at 5794399356078761
89 : fail at 5954850603819253
90 : fail at 6125544931991761
91 : fail at 6320931714094861
92 : fail at 6347593619672581
93 : fail at 6406268028524101
94 : fail at 6510632945054941
95 : fail at 6620082224794741
96 : fail at 6627325072566061
97 : fail at 6844056606431101
98 : fail at 6989404981060153
99 : fail at 7144293947609521
100 : fail at 7288348593229021
101 : fail at 7288539837129253
102 : fail at 7406102904971689
103 : fail at 7430233301822341
104 : fail at 7576425305871193
105 : fail at 7601696719033861
106 : fail at 7803926845356487
107 : fail at 7892007967006633
108 : fail at 7947797946559453
109 : fail at 8207000460596953
110 : fail at 8295064717807513
111 : fail at 8337196000698841
112 : fail at 8352714234009421
113 : fail at 8389755717406381
114 : fail at 8509654470665701
115 : fail at 8757647355282841
116 : fail at 8903933671696381
117 : fail at 8996133652295653
118 : fail at 9074421465661261
119 : fail at 9157536631454221
120 : fail at 9188353522314541