ソリナス素数

数学において、ソリナス素数（ソリナスそすう、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}modp$.

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

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