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

mathe

1.                 __int64 r=PowModular( base[i], t, n );
   
2.                 if( r==1 ) continue;

复制代码

=>

1.                 __int64 r=PowModular( base[i], t, n );
   
2.                 if( r==1 ) return false;

复制代码

这里我弄错了

medie2005

GxQ顺便给我测一下下面这几个五元组测试基吧。
(2,3,5,1151,112327)   48 fail
(2,3,5,557,46853)       45 fail
(2,3,5,557,161333)    44 fail
(2,3,5,557,566149)    41 fail
(2,3,5,179,28087)     38 fail

mathe

1.                 for( j=0; j<s; ++j ){
   
2.                         if( r==n-1 ) break;
   
3.                         r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
   
4.                 }
   
5.                 if( j<s ) continue;

复制代码

=>

1.                 for( j=0; j<s; ++j ){
   
2.                         if( r==n-1 ) break;
   
3.                         r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
   
4.                 }
   
5.                 if( j<s-1 ) continue;

复制代码

medie2005

我按mathe的改了,还是不对啊.
结果还是有20个在10^16内误判了为素数.

gxqcn

我感觉原代码没有问题。

但如果将：

1.                 if( r==1 ) continue;
   
2.                 int j;
   
3.                 for( j=0; j<s; ++j ){
   
4.                         if( r==n-1 ) break;
   
5.                         r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
   
6.                 }
   
7.                 if( j<s ) continue;
   
8.                 return false;

复制代码

替换成：

1.                 if( r==1 || r==n-1 ) continue;
   
2.                 int j;
   
3.                 for( j=1; j<s; ++j ){
   
4.                         r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
   
5.                         if( r==n-1 ) break;
   
6.                 }
   
7.                 if( j==s ) return false;

复制代码

则更容易理解。

gxqcn

669094855201 = 578401*1156801，
而该数确实通过了 测试基（2, 3, 7, 61, 24251）！

这说明 Greathouse 的结论有问题，
因为该结论被许多知名站点引用，如 http://primes.utm.edu/prove/prove2_3.html，
我在开发 HugeCalc 时也采信了它，现在看来有些问题了，
好在是 10^12 ～ 10^16 范围内素数很少利用到，所以影响面相对比较小。
（幸亏在前不久开发的DSP RSA中不存在该问题，因为不必要利用该结论）

无心人

看来我帖子问题终于有了实际意义了啊

medie2005

而该数确实通过了 测试基（2, 3, 7, 61, 24251）！
================================
GxQ为什么这么肯定？

无心人

669094855201
20909214225