ブラム数

ブラム数について

概要

ブラム数とは、暗号論における特異な整数で、4を法として3に合同である二つの異なる素数の積として定義されます。この数は、数論と暗号技術の交差点で重要な役割を果たしています。

性質

整数 n がブラム数であり、n = pq（p, q は素数）と表せる場合、Qnという集合が定義されます。この集合は、nを法とした平方剰余の整数から構成されています。

対応する平方根

ブラム数の重要な特性として、一つの整数 a ∈ Qn が n を法とする平方根を正確に4つ持つことが挙げられます。しかし、その中でQnに含まれるのはわずか1つです。これは計算や特定のアルゴリズムにおいて重要な影響を与えます。

置換関数の定義

置換関数 f: Qn → Qn に対し、f(x) = x² mod n が定義されます。また、この関数の逆関数は、f⁻¹(x) = x^((p-1)(q-1)+4)/8 mod n と表現され、これは特に暗号技術において迅速な計算を可能にします。

ヤコビ記号の特性

さらに、n を法とする -1 のヤコビ記号は +1 とされており、これが示すのは -1 自体が n を法として平方非剰余であるということです。これは、数論における深い意味を持ち、暗号の安全性にも寄与します。

歴史的背景

ブラム数は1982年にマヌエル・ブラムによって初めて紹介されました。彼はこの数を用いて、特に電話を用いたコイン投げのプロトコルなど、現実世界でのシステムに応用しました。この提案により、Qnから任意の整数の平方根を繰り返し計算可能であることが確保されました。

ラビン暗号との関連

また、ブラム数の性質はRabin暗号におけるモジュラスにも関連しています。この暗号方式では、ブラム数を用いることで復号処理が迅速化され、効率的な暗号化が実現されることが示唆されています。

素因数分解アルゴリズム

更に、MPQS（複数多項式二次ふるい法）やNFS（数体ふるい法）など、素因数分解のアルゴリズムにおいては、ブラム数に制限されていないRSAモジュラスでも計算が可能であり、計算量において同等のパフォーマンスを見せます。このため、RSA暗号における素因数分解の難しさを基にした安全性の原則において、法をブラム数に限定する必要がないとされる見解が広まっています。

結論

ブラム数は、暗号理論においてその特有の性質から多岐にわたる応用があり、現代の暗号技術に欠かせない要素といえます。これを理解することで、暗号の基本的な構造やその安全性を深く認識することができるでしょう。

もう一度検索