ソリナス素数

数学において、ソリナス素数（ソリナスそすう、Solinas prime）または一般化メルセンヌ素数（いっぱんかメルセンヌそすう、Generalized Mersenne prime）とは、素数で$f(2^{m})$の形を持つものである。($f(x)$は小さい整数係数を伴う低次の多項式とする。)ソリナス素数は高速なモジュラー簡約(詳細は後述)に使えるため、暗号によく用いられる。

ソリナス素数はジェローム・ソリナスにちなんで名付けられた。

この素数は、以下の素数のカテゴリーの上位集合となっている。

• メルセンヌ素数:$2^{k}-1$
• クランドール素数: $2^{k}-c$($c$はある程度小さな奇数とする)

モジュラー簡約

$f(t)=t^{d}-c_{d-1}t^{d-1}-...-c_{0}$をすべての係数が$\mathbb {Z}$(整数)のd次方程式とし、$p=f(2^{m})$はソナリス素数とする。この条件で、最大$2md$ビットの数($n<p^{2}$)が与えられるとき、$n$を$p$で割ったあまりと合同でかつ$p$と同じビット数となる数を求める操作について考える。

最初に$n$を$2^{m}$進数で表すと以下のようになる

$n=\sum _{j=0}^{2d-1}A_{j}2^{mj}$

次に、多項式$f(t)$によって、$\mathbb {Z}$(整数)上に定義された線形帰還シフトレジスタを$d$回繰り返すことによって、$d\times d$の行列である$X=(X_{i,j})$を導き出す。$[0|0|...|0|1]$という$d$個の整数レジスタから開始し、右に1ずつシフトして左に0を代入。各ステップで出力値に$[c_{0},...,c_{d-1}]$を加算する。ここで、$X_{i,j}$はi番目のステップにおけるj番目のレジスタの整数値となるので、Xの最初の行は$(X_{0,j})=[c_{0},...,c_{d-1}]$となることに着目し、式$B=(B_{i})$を以下のように定義する。

$(B_{0}...B_{d-1})=(A_{0}...A_{d-1})+(A_{d}...A_{2d-1})X$,

これらの式より、以下のような式が導出できる。

$\sum _{j=0}^{d-1}B_{j}2^{mj}\equiv \sum _{j=0}^{2d-1}A_{j}2^{mj}\mod p$.

したがって、$B$は$n$と合同な$md$ビットの整数だとわかる。

$f$を適切に調整することによって、このモジュラー簡約のアルゴリズムは加算・減算のみとなり元の式$n-p\cdot (n/p)$よりもはるかに効率的になる(除算がないため)。