Java BigIntegerによる多数桁計算

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

1. Java BigIntegerの主な機能

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

2. Java BigInteger基本プログラム

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

3. 多数桁の素数の作成

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

4. 素数定理の検証

  (1) フェルマーの小定理
    pを素数、mを任意の整数とすると下記が成立する。
     mp-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暗号鍵の作成