能通过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;
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