ブラム数

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

性質

整数 n = pq をブラム数、Q_n を n を法として平方剰余となる整数の集合とし、a ∈ Q_nとすると：

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

${\displaystyle \left({\frac {-1}{n}}\right)=\left({\frac {-1}{p}}\right)\left({\frac {-1}{q}}\right)=(-1)^{2}=1}$

歴史

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

MPQS（複数多項式2次ふるい法）やNFS（数体ふるい法）のような素因数分解アルゴリズムは、ランダムに選択したRSAモジュラスでもブラム数に制限した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.