基于Java BigInteger類的大整數運算應用

申時全 SHEN Shi-quan

（廣東科技學院，廣州 510635）

（Guangdong University of Science&Technology，Guangzhou 510635，China）

0 引言

Java提供了進行大整數計算的類BigInteger，封裝了大整數的加（add）、減(subtract)、乘(multiply)、除(divide)以及求余(remainder)運算，還封裝了大整數的冪運算(power)和比較(compare)運算等。通過使用這些大整數運算，可以求解許多高精度運算問題。

計算具有100位以上精度的黃金分割系數、計算100位以上精度的圓周率、計算具有100位以上十進制數的大整數都是具有重要意義的事。應用Java的BigInteger類，可以方便地解決這些問題。

1 Java BigInteger類封裝

Java的BigInteger類是java.math包中的一個類，提供任意精度的整數運算。

1.1 構造大整數對象 Java中的大整數是BigInteger類的對象，構造大整數對象的構造方法是：

public BigInteger(String val)

因此，為構造一個大整數對象需要用該構造方法，步驟是：申明對象bignum，用new操作創建該對象。例如構造一個20位數9999999999999999999，可用如下語句實現：

BigIntegerbignum=new BigInteger(“99999999999999 99999”);

然后可通過對象bignum調用相關計算方法。

1.2 BigInteger類封裝的主要方法 BigInteger類封裝了以下常用方法，實現另一個大整數對象與本對象的運算，并生成一個新的大整數對象（比較運算除外）。另外，還封裝了與大素數的方法，這些方法是：

①獲取一個給定位數和隨機數位的大素數，是一個靜態（static）方法，定義如下：

public static BigInteger probablePrime(int bitLength,Random rnd):該方法獲得一個可能性很的具有二進制bitLength位的大素數，其概率為1-2-100。

②獲取下一個可能素數的方法，方法定義如下：

BigInteger nextProbablePrime();該方法返回一個與當前的可能素數p，最接近的可能素數q;對于任意p

③將一個長整型轉換為BigInteger對象的方法，方法定義如下：

public static BigInteger valueOf(long val);該方法返回長整型數val的bigInteger對象。

④判斷大整數是否為可能素數的方法，方法定義如下：

boolean isProbablePrime(int certainty);若對象num.isProbablePrime(cer)返回true，則num是素數的概率大于1-2-cer。

⑤求余數運算方法remainder()，方法定義如下：

public BigInteger remainder(BigInteger opnd)；實現一個大整數對象與另一大整數對象opnd的求余運算，并返回余數（一個大整數對象）。

⑥求大整數的商和余數的方法 divideAndRemainder(BigInteger opnd)，該方法返回大整數對象除以大整數opnd的商和余數，用一個BigInteger類型數組存放，例如：

BigInteger aBig[]=new BigInteger[2];

BigInteger num=new BigInteger(“125”);

aBig=divideAndRemainder(num,new BigInteger(“23”));

那么aBig[0]是125除以23的商5，aBig[1]是余數10。

其余方法這里就不多加敘述，可參考文獻[1]。

2 BigInteger類在高精度計算問題中的應用

可應用BigInteger類進行高精度計算問題的求解，方法簡便。求解步驟如圖1。

圖1

3 典型問題的大整數求解

3.1 高精度黃金分割系數問題的求解 黃金分割系數0.61803...是個無理數，這個常數十分重要，在許多工程問題中會出現。有時需要把這個數字求得很精確。比較簡單的一種是用連分數表示，如圖2。

圖2

這個連分數計算的“層數”越多，它的值越接近黃金分割數。

我們需要求出黃金分割數的足夠精確值，四舍五入到小數點后100位。

我們可以將黃金數的計算抽象為以下表達形式：

可以將上式轉換為分數形式：nk/dk，那么，nk+1=dk，dk+1=dk+nk，n0=1，d0=1。

由此遞推，計算分子和分母，直到分子≥10100，這樣，可保證結果滿足能得到所要求精度。然后是將分子乘上10100，在與分母做除法，得到的就是100位的大整數，就是這個黃金數的小數點后的數字，經四舍五入處理并轉換成字符串輸出即可，通過對余數的判斷，可確定是否要在結果中加1。程序如下：

3.2 求大素數問題的程序 大素數是數據加密與解密問題的核心，在RSA加密體系中，為了生成RSA算法的公鑰和私鑰的秘鑰對，先要選擇兩個大素數p和q，并計算它們的乘積N。我們這里用Java的BigInteger類來產生具有100位（當然可以更多，視需要而定）十進制數的大素數。對于大素數的判斷，并沒有一個嚴密的數學公式可供應用。可用BigInteger類中相關運算方法，結合素數相關方法，可以求出給定位數（二進制）的可能大素數，且具有隨機性。

可以用BigInteger類的probablePrime()方法生成給定位數的近似大素數（稱為概素數），其準確度可用一個參數進行控制。下面的程序生成若干個隨機生成的具有330位二進制位（具有100位十進制）的大素數。BigInteger.probablePrime(bitNum,rnd)生成的“概素數”具有bitNum位二進制，其是素數的概率大于1-2-100。為了提高可靠性，程序中對生成的“概素數”進行更嚴格測試，用10000做參數，用isProbablePrime(10000)測試，該方法保證素數的概率大于1-2-10000。

3.3 求解與梅森素數有關的問題 根據法國數學家梅森的猜想，我們習慣上把形如：2n-1的素數稱為：梅森素數。截止2013年2月，一共只找到了48個梅森素數。新近找到的梅森素數太大，以至于難于用一般的編程思路驗證。這里要解決的是跟梅森素數有關的一個問題：1963年，美國伊利諾伊大學為了紀念他們找到的第23個梅森素數n=11213，在每個寄出的信封上都印上了“211213-1是素數”的字樣。211213-1這個數字已經很大 (有3000多位)，編程求出這個素數的十進制表示的最后100位。直接用BigInteger類求解該問題相關語句如下：

4 結束語

本文介紹了Java中的BigInteger類的一些典型應用。BigInteger類中包裝了絕大多數大整數運算功能，文中沒有完全涉及，可參考Java有關技術資料，應用Java的BigInteger類求解一些高精度運算問題，十分方便。特別說明的是，符合費爾馬定理的大整數只符合素數的必要條件，但不是充分條件。本文中所給程序計算的結果，只能是有極大可能性是素數，其可能性超過1-2-10000。如果要用所有小于待測“概素數”的平方根的所有概素數去檢測一個數百位十進制位需要很長時間，并不實用。

[1]耿祥義，張躍平.Java面向對象程序設計（第2版）[M].北京：清華大學出版社，2013.

[2]王英.RSA算法中安全大素數的選擇[J].西安：西安工業學院學報，2005.

[3]Mark Stamp，Information Security:Principles and Practice[M].by Wiley Publishing,Inc,2011（張戈譯,信息安全原理與實踐（第 2版）[M].北京：清華大學出版社，2013）.