通常java判断质数，只需用BigInteger.nextProbablePrime()方法就行了。这里记录miller rabin 的一种java实现。
View Code
1 public class MillerRabin{
2 public static void main(String[] args) {
3 int p = 7, p2 = p - 1;
4 boolean flag = true;
5 int k, i, j = 0;
6 k = (int) (Math.log(p) / Math.log(2)) + 1;
7 int a[], b[], c[];
8 c = new int[5];// 用来生成5个检测数
9 a = new int[k];
10 b = a;
11
12 // 把P转化为2进制
13 for (i = 0; p2 > 0; i++) {
14 a[i] = p2 % 2;
15 p2 /= 2;
16 }
17 for (i--; i >= 0; j++, i--) {
18 b[j] = a[i];
19 }
20
21 for (int r = 0; r < a.length; r++) {
22 System.out.print(a[r]);
23 }
24 for (int m = 0; m < 5; m++) { // //5次WITNESS(a[i],P)测试P的素数
25 c[m] = (int) (Math.random() * (p - 3)) + 2;
26 System.out.println("\n" + c[m]);
27 if (witness(c[m], p, b) == 0) {
28 flag = false;
29 }
30 }
31
32 if (flag)
33 System.out.println("Prime! " + p);
34 else
35 System.out.println("not Prime! " + p);
36
37 }
38
39 private static int witness(int a, int n, int[] b) {
40 int x, k;
41 int d = 1;
42 k = b.length - 1;
43 for (int m = k; m >= 0; m--) {
44 x = (int) d;
45 d = (d * a) % n;
46 if ((d == 1) && (x != 1) && (x != n - 1))
47 return 1;
48 if (b[m] == 1)
49 d = (d * a) % n;
50 }
51 if (d != 1){
52 System.out.println("a:"+a+" n:"+n);
53 return 0;
54 }
55 return 1;
56 }
57
58 public static void witness(int t) {
59 BigInteger bi = new BigInteger(""+(t-1)+"");
60 if(bi.nextProbablePrime().intValue()==t){
61 System.out.println(t+" is prime!");
62 }else{
63 System.out.println(t+" is not prime!");
64 }
65 }
66 }