「ブラム数」の版間の差分
提供: miniwiki
ja>新規作成 細 (→参考文献) |
細 (1版 をインポートしました) |
(相違点なし)
|
2018/8/19/ (日) 17:34時点における最新版
ブラム数とは、暗号理論の概念で、4を法として3に合同な相異なる2つの素数の積となる整数のことである。
性質
整数 n = pq をブラム数、Qn を n を法として平方剰余となる整数の集合とし、a ∈ Qnとすると:
- a は n を法とする平方根をちょうど4個持ち、そのうち1個だけがQnに含まれる。
- 置換関数 f: Qn → Qn を f(x) = x2 mod n と定義すると、f の逆関数は f -1(x) = x((p-1)(q-1)+4)/8 mod n となる[1]。
- n を法とする -1 のヤコビ記号は +1 である(-1 は n を法として平方非剰余であるが):
- [math]\left(\frac{-1}{n}\right)=\left(\frac{-1}{p}\right)\left(\frac{-1}{q}\right)=(-1)^2=1[/math]
歴史
マヌエル・ブラムが1982年に導入したブラム数は、1番目の性質により、Qnからランダムに選択した整数の平方根を(何回でも)求めることができると保証されていて、電話によるコイン投げのためのプロトコルなど利用された[2]。 また、2番目の性質から、Rabin暗号のモジュラスをブラム数にすると復号処理(平方根)が高速化できることが指摘されている。
MPQSやNFSのようなアルゴリズムは、ランダムに選択したRSAモジュラスでもブラム数に制限したRSAモジュラスでも同程度の計算量で計算可能であるため、もはやブラム数に限定する理由はないと考えられている。