Miller-Rabin測試：

　　費馬小定理：對于素數p和任意整數a，有a^p?≡ a(mod p)（同余）。反過來，滿足a^p?≡ a(mod p)，p也幾乎一定是素數。

　　偽素數：如果n是一個正整數，如果存在和n互素的正整數a滿足 a^n-1?≡ 1(mod n)，我們說n是基于a的偽素數。如果一個數是偽素數，那么它幾乎肯定是素數。

　　Miller-Rabin測試：不斷選取不超過n-1的基b(s次)，計算是否每次都有b^n-1?≡ 1(mod n)，若每次都成立則n是素數，否則為合數。　

結合算法導論中說明的理解，參考代碼如下：

package cn.ansj;import java.util.Random;public class MillerRabin {private static final int ORDER = 10000;// 隨機數的數量級 private static final int MIN = 1000; // 選擇的隨機數的最小值public static void main(String[] args){int x = getPrime();boolean flag = true;for (int i = 0; i < 10; i++){if (!isPrime(x)){flag = false;break;}}if (flag) System.out.println(x + ":是素數，通過測試");else System.out.println(x + ":不是素數"); }/*** 整數轉為二進制* * @param m整數m* @return 字節數組*/public static byte[] getByte(int m){String sb = "";while (m > 0){sb = (m % 2) + sb;m = m / 2;}return sb.getBytes();}/*** 平方-乘法計算指數模運算 a^m % n* * @param a底數* @param m指數* @param n被mod數* @return*/public static int Square_and_Mutiply(int a, int m, int n){int d = 1; byte[] bm = getByte(m);// 把m轉化為二進制數for (int i = 0; i < bm.length; i++){d = (d * d) % n; if (bm[i] == 49)// 二進制1等于asciI碼的49d = (d * a) % n; }return d;}/*** 隨機選擇一個奇數*/public static int getRandom(){int x = 3;Random rd = new Random();do{x = rd.nextInt(ORDER);} while (x < MIN || x % 2 == 0);return x;}/*** 驗證一個數是否為素數，將n-1改寫為2^k * m的形式，其中m是奇數，在{2,...,n-1}中隨機選取一個整數a;* * @param n* @return 如果是素數返回true,否則返回false*/public static boolean isPrime(int n){ int[] arr = intTOIndex(n - 1);// n-1 用2的冪表示int k = arr[0];int m = arr[1]; Random r = new Random();// 在{2,...,n-1}隨機選擇一個整數aint a = 0;do {a = r.nextInt(n - 1);} while (a < 2);int b = Square_and_Mutiply(a, m, n);if (b == 1) return true;for (int i = 0; i < k; i++) {if (b == (n - 1)) return true;else b = (b * b) % n; }return false;}/*** 將一個數改為2^k * m的形式，其中m是奇數* * @param n* @return arr[0]=k,arr[1]=m*/public static int[] intTOIndex(int n){int[] arr = new int[2];int k = 0;int x;// 當n為奇數是停止循環do {k++;n >>= 1;x = n & 1;} while (x == 0);arr[0] = k;arr[1] = n;return arr;}/*** 獲取一個隨機數為并且檢查其為素數* * @return*/public static int getPrime(){int x = 0;while (x % 2 == 0 || !isPrime(x)){x = getRandom();}return x;} }
執行結果：

7207:是素數，通過測試

總結

以上是生活随笔為你收集整理的Java实现算法导论中Miller-Rabin随机性素数测试的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。