基于Java BigInteger類的大整數(shù)運(yùn)算應(yīng)用

申時(shí)全 SHEN Shi-quan

（廣東科技學(xué)院，廣州 510635）

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

0 引言

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

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

1 Java BigInteger類封裝

Java的BigInteger類是java.math包中的一個(gè)類，提供任意精度的整數(shù)運(yùn)算。

1.1 構(gòu)造大整數(shù)對(duì)象 Java中的大整數(shù)是BigInteger類的對(duì)象，構(gòu)造大整數(shù)對(duì)象的構(gòu)造方法是：

public BigInteger(String val)

因此，為構(gòu)造一個(gè)大整數(shù)對(duì)象需要用該構(gòu)造方法，步驟是：申明對(duì)象bignum，用new操作創(chuàng)建該對(duì)象。例如構(gòu)造一個(gè)20位數(shù)9999999999999999999，可用如下語句實(shí)現(xiàn)：

BigIntegerbignum=new BigInteger(“99999999999999 99999”);

然后可通過對(duì)象bignum調(diào)用相關(guān)計(jì)算方法。

1.2 BigInteger類封裝的主要方法 BigInteger類封裝了以下常用方法，實(shí)現(xiàn)另一個(gè)大整數(shù)對(duì)象與本對(duì)象的運(yùn)算，并生成一個(gè)新的大整數(shù)對(duì)象（比較運(yùn)算除外）。另外，還封裝了與大素?cái)?shù)的方法，這些方法是：

①獲取一個(gè)給定位數(shù)和隨機(jī)數(shù)位的大素?cái)?shù)，是一個(gè)靜態(tài)（static）方法，定義如下：

public static BigInteger probablePrime(int bitLength,Random rnd):該方法獲得一個(gè)可能性很的具有二進(jìn)制bitLength位的大素?cái)?shù)，其概率為1-2-100。

②獲取下一個(gè)可能素?cái)?shù)的方法，方法定義如下：

BigInteger nextProbablePrime();該方法返回一個(gè)與當(dāng)前的可能素?cái)?shù)p，最接近的可能素?cái)?shù)q;對(duì)于任意p

③將一個(gè)長(zhǎng)整型轉(zhuǎn)換為BigInteger對(duì)象的方法，方法定義如下：

public static BigInteger valueOf(long val);該方法返回長(zhǎng)整型數(shù)val的bigInteger對(duì)象。

④判斷大整數(shù)是否為可能素?cái)?shù)的方法，方法定義如下：

boolean isProbablePrime(int certainty);若對(duì)象num.isProbablePrime(cer)返回true，則num是素?cái)?shù)的概率大于1-2-cer。

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

public BigInteger remainder(BigInteger opnd)；實(shí)現(xiàn)一個(gè)大整數(shù)對(duì)象與另一大整數(shù)對(duì)象opnd的求余運(yùn)算，并返回余數(shù)（一個(gè)大整數(shù)對(duì)象）。

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

BigInteger aBig[]=new BigInteger[2];

BigInteger num=new BigInteger(“125”);

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

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

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

2 BigInteger類在高精度計(jì)算問題中的應(yīng)用

可應(yīng)用BigInteger類進(jìn)行高精度計(jì)算問題的求解，方法簡(jiǎn)便。求解步驟如圖1。

圖1

3 典型問題的大整數(shù)求解

3.1 高精度黃金分割系數(shù)問題的求解 黃金分割系數(shù)0.61803...是個(gè)無理數(shù)，這個(gè)常數(shù)十分重要，在許多工程問題中會(huì)出現(xiàn)。有時(shí)需要把這個(gè)數(shù)字求得很精確。比較簡(jiǎn)單的一種是用連分?jǐn)?shù)表示，如圖2。

圖2

這個(gè)連分?jǐn)?shù)計(jì)算的“層數(shù)”越多，它的值越接近黃金分割數(shù)。

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

我們可以將黃金數(shù)的計(jì)算抽象為以下表達(dá)形式：

可以將上式轉(zhuǎn)換為分?jǐn)?shù)形式：nk/dk，那么，nk+1=dk，dk+1=dk+nk，n0=1，d0=1。

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

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

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

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

4 結(jié)束語

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

[1]耿祥義，張躍平.Java面向?qū)ο蟪绦蛟O(shè)計(jì)（第2版）[M].北京：清華大學(xué)出版社，2013.

[2]王英.RSA算法中安全大素?cái)?shù)的選擇[J].西安：西安工業(yè)學(xué)院學(xué)報(bào)，2005.

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