ブラム数
提供: miniwiki
ブラム数とは、暗号理論の概念で、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モジュラスでも同程度の計算量で計算可能であるため、もはやブラム数に限定する理由はないと考えられている。