数学において、ソリナス素数（ソリナスそすう、Solinas prime）または一般化メルセンヌ素数（いっぱんかメルセンヌそすう、Generalized Mersenne prime）とは、素数での形を持つものである。(は小さい整数係数を伴う低次の多項式とする。)ソリナス素数は高速なモジュラー簡約(詳細は後述)に使えるため、暗号によく用いられる。
ソリナス素数はジェローム・ソリナスにちなんで名付けられた。
この素数は、以下の素数のカテゴリーの上位集合となっている。
メルセンヌ素数: クランドール素数: (はある程度小さな奇数とする)
モジュラー簡約 をすべての係数が(整数)のd次方程式とし、はソナリス素数とする。この条件で、最大ビットの数()が与えられるとき、をで割ったあまりと合同でかつと同じビット数となる数を求める操作について考える。
最初にを進数で表すと以下のようになる
次に、多項式によって、(整数)上に定義された線形帰還シフトレジスタを回繰り返すことによって、の行列であるを導き出す。という個の整数レジスタから開始し、右に1ずつシフトして左に0を代入。各ステップで出力値にを加算する。ここで、はi番目のステップにおけるj番目のレジスタの整数値となるので、Xの最初の行はとなることに着目し、式を以下のように定義する。
,
これらの式より、以下のような式が導出できる。
.
したがって、はと合同なビットの整数だとわかる。
を適切に調整することによって、このモジュラー簡約のアルゴリズムは加算・減算のみとなり元の式よりもはるかに効率的になる(除算がないため)。
参考文献