ブルーム整数

数学において、自然数 nがブルーム整数であるとは、n = p × q が半素数であり、pとq が3 mod 4に合同な異なる素数である場合を言う。 ^[1]つまり、pとq は、何らかの整数tに対して4 t + 3 の形式でなければならない。この形式の整数はブルーム素数と呼ばれる。^[2]これは、ブルーム整数の因数が虚数部を持たないガウス素数であることを意味する。最初のいくつかのブルーム整数は

21、33、57、69、77、93、129、133、141、161、177、201、209、213、217、237、249、253、301、309、321、329、341、381、393、413、417、437、453、469、473、489、497 、 ... （OEISの配列A016105 ）​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​

この整数はコンピュータ科学者のマヌエル・ブルムにちなんで名付けられました。^[3]

n = p × q をブルーム整数とし、 Q _{n を}nを法としてnと互いに素なすべての平方剰余の集合とし、 a ∈ Q _nとすると、次の式が成り立つ: ^[2]

• aにはnを法とする平方根が 4 つあり、そのうちの 1 つはQ _nにも含まれる。
• Q _nにおけるaの唯一の平方根は、nを法としたaの主平方根と呼ばれる。
• 関数f  : Qn → Qn_はf ( x )= x2modnで定義され_、^{順列である}。fの逆関数はf ⁻¹ ( x )= x ^{(( p} − ^{1)( q −1)+4)/8modn}である。[ ⁴ ]
• あらゆるブルーム整数nに対して、 −1 はnの平方剰余ではないものの、 n を法として +1 となるヤコビ記号を持ちます。

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

ブルーム整数は2 つの平方数の和ではありません。

MPQSやNFSなどの現代の因数分解アルゴリズムが開発される前は、RSA係数として Blum 整数を選択することが有用であると考えられていました。MPQS と NFS は、ランダムに選択された素数から構成される RSA 係数と同じ容易さで Blum 整数を因数分解できるため、これはもはや有用な予防策とは見なされていません。^{[引用が必要]}