ブラム数のソースを表示

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

==性質==
整数 ''n = pq'' をブラム数、''Q<sub>n</sub>'' を ''n'' を法として[[平方剰余]]となる整数の集合とし、''a'' ∈ ''Q<sub>n</sub>''とすると：

# ''a'' は ''n'' を法とする平方根をちょうど4個持ち、そのうち1個だけが''Q<sub>n</sub>''に含まれる。<!-- ''a'' の平方根で ''Q<sub>n</sub>''に含まれるものを、''n'' を法とする ''a'' の 主平方根（''principal square root''）と言う。-->
# 置換関数 ''f:'' ''Q<sub>n</sub>'' → ''Q<sub>n</sub>'' を ''f(x) = x<sup>2</sup>'' mod ''n'' と定義すると、''f'' の逆関数は ''f <sup>-1</sup>(x) = x<sup>((p-1)(q-1)+4)/8</sup>'' mod ''n'' となる<ref name="hac">Alfred Menezes|A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography, ISBN 0-8493-8523-7.</ref>。
# ''n'' を法とする -1 の[[ヤコビ記号]]は +1 である（-1 は ''n'' を法として平方非剰余であるが）:<br>
:<math>\left(\frac{-1}{n}\right)=\left(\frac{-1}{p}\right)\left(\frac{-1}{q}\right)=(-1)^2=1</math>

==歴史==
[[マヌエル・ブラム]]が1982年に導入したブラム数は、1番目の性質により、''Q<sub>n</sub>''からランダムに選択した整数の平方根を（何回でも）求めることができると保証されていて、電話によるコイン投げのためのプロトコルなど利用された<ref name="BLUM82">M. Blum, "Coin flipping by telephone: a protocol for solving impossible problems", Proceedings of the 24th IEEE Computer Conference, pp133-137, 1982.
</ref>。
また、2番目の性質から、[[Rabin暗号]]のモジュラスをブラム数にすると復号処理（平方根）が高速化できることが指摘されている。

MPQS（複数多項式2次ふるい法）やNFS（数体ふるい法）のような素因数分解アルゴリズムは、ランダムに選択したRSAモジュラスでもブラム数に制限したRSAモジュラスでも同程度の[[計算量]]で計算可能である。なので、[[RSA暗号]]などの素因数分解の困難性を安全性の根拠とする暗号システムにおいて、もはや法をブラム数に限定する理由はないと考えられている。

==参考文献==
<div class="references-small">
<references />
</div>


{{DEFAULTSORT:ふらむすう}}

[[Category:数論]]
[[Category:整数の類]]
[[Category:数学に関する記事]]