ソリナスプライム

数学において、ソリナス素数、または一般化メルセンヌ素数は、という形式を持つ素数であり、 は小さな整数係数を持つ低次多項式である。 [ ^{1] [2]これらの素数により、高速なモジュラー削減アルゴリズムが可能になり}、暗号化で広く使用されている。これらはジェローム・ソリナスにちなんで名付けられている。 ${\displaystyle f(2^{m})}$${\displaystyle f(x)}$

このクラスの数には、他のいくつかの素数のカテゴリが含まれます。

• メルセンヌ素数は次の形式を持ちます。${\displaystyle 2^{k}-1}$
• クランドール素数または擬似メルセンヌ素数は、小さな奇数に対しての形をとる。^[3]${\displaystyle 2^{k}-c}$ ${\displaystyle c}$

を の係数を持つ の次数の単項多項式とし、 をソリナス素数とします。最大 ビットの数が与えられた場合、と同じビット数、つまり最大 ビットで を法として同値となる数を見つけます。 ${\displaystyle f(t)=t^{d}-c_{d-1}t^{d-1}-...-c_{0}}$${\displaystyle d}$${\displaystyle \mathbb {Z} }$${\displaystyle p=f(2^{m})}$${\displaystyle n<p^{2}}$${\displaystyle 2md}$${\displaystyle n}$${\displaystyle p}$${\displaystyle p}$${\displaystyle md}$

まず、基数 で表します。 ${\displaystyle n}$${\displaystyle 2^{m}}$

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

次に、多項式 によって上で定義される線形フィードバックシフトレジスタを回ステップ実行して、 -行 -列の行列を生成します。 -整数レジスタから始めて、1 つ右にシフトし、左側に を注入して、各ステップで出力値とベクトルの積を（要素ごとに）加算します（詳細は [1] を参照）。を 番目のステップの 番目のレジスタの整数とし、 の最初の行はで与えられることに注意してください。次に、を で与えられる整数ベクトル で表すと、次のようになります。${\displaystyle d}$${\displaystyle d}$ ${\displaystyle X=(X_{i,j})}$${\displaystyle d}$${\displaystyle \mathbb {Z} }$${\displaystyle f}$${\displaystyle d}$${\displaystyle [0|0|...|0|1]}$${\displaystyle 0}$${\displaystyle [c_{0},...,c_{d-1}]}$${\displaystyle X_{i,j}}$${\displaystyle j}$${\displaystyle i}$${\displaystyle X}$${\displaystyle (X_{0,j})=[c_{0},...,c_{d-1}]}$${\displaystyle B=(B_{i})}$

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

次のことは簡単に確認できます。

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

したがって、 はと同値の ビット整数を表します。 ${\displaystyle B}$${\displaystyle md}$${\displaystyle n}$

を賢明に選択すれば（これも[1]を参照）、このアルゴリズムは比較的少数の加算と減算（除算なし！）しか必要としないため、単純なモジュラー削減アルゴリズム（）よりもはるかに効率的になります。 ${\displaystyle f}$${\displaystyle np\cdot (n/p)}$

NISTの文書「連邦政府が使用するために推奨される楕円曲線」 で推奨されている素数のうち 4 つは、ソリナス素数です。

• 192ページ${\displaystyle 2^{192}-2^{64}-1}$
• 224ページ${\displaystyle 2^{224}-2^{96}+1}$
• 256ページ${\displaystyle 2^{256}-2^{224}+2^{192}+2^{96}-1}$
• 384ページ${\displaystyle 2^{384}-2^{128}-2^{96}+2^{32}-1}$

Curve448はSolinasプライムを使用する${\displaystyle 2^{448}-2^{224}-1.}$

• メルセンヌ素数