PrimeGenerator - lotteryjava @ ウィキ

PrimeGenerator

コンストラクタ

メソッド

• GetStrongPrimes()

[動作]
 this.GetStrongPrimes()でSafePrimeを返す。
 SafePrimeの意味は以下に説明してある。
[数学的idea]
☆SafePrime
 次の３つを満たす素数pをSafePrimeと言い、因数分解や離散対数問題に対して安全な素数となる。
  ①p-1は大きな素因数qをもつ。
  ②p+1は大きな素因数sをもつ。
  ③q-1は大きな素因数tをもつ。
  このような素数を作ることが本メソッドの目的である。
☆SafePrimeの作り方
   t,sは大きな素数であることを前提とする。
   q = 2*i*t + 1 となるiを探す。 
   z = s^(q-2) mod q
   p* = 2*z*s - 1 
   p = 2*q*s + p* 
   p = 2^x * q * s + p* (xは大きくする。またpは素数にする)
     このようにpを作り出せば、pはSafePrimeになる。
☆なぜこの作り方でSafePrimeになるのか。
   まずq=2*i*t +1 より t|q-1は自明で③を満たす。
   p*において、z*sはs^(q-1)であるのでフェルマーの小定理より1≡zs≡s^(q-1) mod q
   よって p*をqで割ると余りが1になります。
   ここでpの最終形を見てqで割った余りを見てみると
     p ≡ 2^x * q * s + p* (mod p)
       ≡ p* (mod p)
       ≡ 1 mod p
   となり　q|p-1が言えて①を満たす。
   最後に②についてだが　p* + 1 = 2*z*s を考えれば, s|p+1は自明。