ブラム数

出典: フリー百科事典『ウィキペディア(Wikipedia)』

移動: 案内検索

ブラム数とは、暗号理論の概念で、4を法として3に合同な相異なる2つの素数の積となる整数のことである。

性質

整数 n = pq をブラム数、Qnn を法として平方剰余となる整数の集合とし、aQnとすると:

  1. an を法とする平方根をちょうど4個持ち、そのうち1個だけがQnに含まれる。
  2. 置換関数 f: QnQnf(x) = x2 mod n と定義すると、f の逆関数は f -1(x) = x((p-1)(q-1)+4)/8 mod n となる[1]
  3. n を法とする -1 のヤコビ記号は +1 である(-1 は n を法として平方非剰余であるが):
\left(\frac{-1}{n}\right)=\left(\frac{-1}{p}\right)\left(\frac{-1}{q}\right)=(-1)^2=1

歴史

マヌエル・ブラムが1982年に導入したブラム数は、1番目の性質により、Qnからランダムに選択した整数の平方根を(何回でも)求めることができると保証されていて、電話によるコイン投げのためのプロトコルなど利用された[2]。 また、2番目の性質から、Rabin暗号のモジュラスをブラム数にすると復号処理(平方根)が高速化できることが指摘されている。

MPQSやNFSのようなアルゴリズムは、ランダムに選択したRSAモジュラスでもブラム数に制限したRSAモジュラスでも同程度の計算量で計算可能であるため、もはやブラム数に限定する理由はないと考えられている。

参考文献

  1. ^ Alfred Menezes|A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography, ISBN 0-8493-8523-7.
  2. ^ M. Blum, "Coin flipping by telephone: a protocol for solving impossible problems", Proceedings of the 24th IEEE Computer Conference, pp133-137, 1982.

今日は何の日(11月30日

もっと見る

「ブラム数」のQ&A