Java BigIntegerによる多数桁計算

　　　2008/3/10　後保範 (Ushiro Yasunori、東京工芸大学)

1. Java BigIntegerの主な機能

　　JavaはRSA暗号処理が容易にできるように、多数桁整数計算をBigIntegerでサポートしている。
　　主な機能は下記の通りである。
　　　(1) 多数桁整数の四則演算
　　　(2) 剰余系計算(X mod P, X^m mod P, 逆元)
　　　(3) ランダムな多数桁整数及び素数の生成
　　　(4) 多数桁整数の最大公約数(gcd)
　　詳細機能は クラス BigIntegerを参照

2. Java BigInteger基本プログラム

　　(1) Java BigInteger利用フレーム
　　(2) 多数桁の指定と乗算

3. 多数桁の素数の作成

　　(1) 多数桁の素数の作成
　　(2) 2素数を作成し、乗算

4. 素数定理の検証

　　(1) フェルマーの小定理
　　　　pを素数、mを任意の整数とすると下記が成立する。
　　　　　m^p-1=1 mod p
　　　(a) pを整数として上記の計算
　　　(b) pを素数として定理の検証

　　(2) オイラーの定理
　　　　オイラーの定理はより一般的であるが、RSA暗号に使用する範囲の、
　　　　p,qが素数とすると、任意の整数nに対し下記が成立する。
　　　　　m^(p-1)(q-1)=1 mod pq
　　　(a) p,qを素数として定理の検証

5. RSA暗号鍵の作成

　　RSA暗号鍵は下記で作成される。
　　　(a) ランダムに素数p,qを選び、n=p×qを計算
　　　(b) f=(p-1)×(q-1)を計算
　　　(c) ランダムに素数eを選ぶ。(n,e)は公開鍵
　　　(d) d=1/e mod fで秘密鍵dを計算

　　(1) RSA暗号鍵の作成