ソリナスプライム

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

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

  • メルセンヌ素数は次の形式を持ちます。2け−1{\displaystyle 2^{k}-1}
  • クランドール素数または擬似メルセンヌ素数は、小さな奇数に対して の形をとり、[ 3 ] 3 ( OEISのシーケンスA0504 ​​14 )、5 ( OEISのシーケンスA059608 )、7 ( OEISのシーケンスA059609 )、9 ( OEISのシーケンスA059610 ) などが含まれます。2け−c{\displaystyle 2^{k}-c}c{\displaystyle c}c＝{\displaystyle c=}

モジュラー縮約アルゴリズム

を係数とする次数 の単項多項式とし、をソリナス素数とします。最大ビットの数が与えられたとき、 を法として と同じビット数、つまり最大ビットの数で合同な数を見つけたいとします。 f（t）＝td−cd−1td−1−。。。−c0{\displaystyle f(t)=t^{d}-c_{d-1}t^{d-1}-...-c_{0}}d{\displaystyle d}Z{\displaystyle \mathbb {Z} }p＝f（2メートル）{\displaystyle p=f(2^{m})}n<p2{\displaystyle n<p^{2}}2メートルd{\displaystyle 2md}n{\displaystyle n}p{\displaystyle p}p{\displaystyle p}メートルd{\displaystyle md}

まず、基数 で表します。 n{\displaystyle n}2メートル{\displaystyle 2^{m}}

n＝∑j＝02d−1あj2メートルj{\displaystyle n=\sum _{j=0}^{2d-1}A_{j}2^{mj}}

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

（B0。。。Bd−1）＝（あ0。。。あd−1）+（あd。。。あ2d−1）X{\displaystyle (B_{0}...B_{d-1})=(A_{0}...A_{d-1})+(A_{d}...A_{2d-1})X}、

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

∑j＝0d−1Bj2メートルj≡∑j＝02d−1あj2メートルjモッドp{\displaystyle \sum _{j=0}^{d-1}B_{j}2^{mj}\equiv \sum _{j=0}^{2d-1}A_{j}2^{mj}\mod p}。

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

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

例

1999年にNISTは楕円曲線暗号の係数として4つのソリナス素数を推奨した。[ 4 ]

  • 曲線p-192は係数を使用する2192−264−1{\displaystyle 2^{192}-2^{64}-1}
  • 曲線p-224は係数を使用する2224−296+1{\displaystyle 2^{224}-2^{96}+1}
  • 曲線p-256は係数を使用する2256−2224+2192+296−1{\displaystyle 2^{256}-2^{224}+2^{192}+2^{96}-1}
  • 曲線 p-384 は係数を使用します。2384−2128−296+232−1{\displaystyle 2^{384}-2^{128}-2^{96}+2^{32}-1}

新しいCurve448は係数を使用します。 2448−2224−1{\displaystyle 2^{448}-2^{224}-1}

典型的な64ビット符号なし整数に収まるソリナス素数は であり、 は円分多項式であるため、 2を底とする（周期長192の）唯一の素数である。このサイズは暗号には小さすぎるが、大きな数の効率的な乗算のための数論的変換の実装には有用である。 [ 5 ]264−232+1{\displaystyle 2^{64}-2^{32}+1}Φ192（2）{\displaystyle \Phi _{192}(2)}Φ{\displaystyle \Phi }

、小さなモジュラー縮約重み、 （つ​​まりコンピュータのワードサイズの倍数）の完全なリストは、2010年にJosé de Jesús Angel AngelとGuillermo Morales-Lunaによって作成されました。[ 6 ]f（2け）＝2メートル−2n±1{\displaystyle f(2^{k})=2^{m}-2^{n}\pm 1}メートル≤2000{\displaystyle m\leq 2000}わt<15{\displaystyle wt<15}け＝8、16、32、64{\displaystyle k=8,16,32,64}

Curve25519は擬似メルセンヌとも呼ばれるを使用しています。 [ 7 ]2255−19{\displaystyle 2^{255}-19}

参照

  • プロス素数: このページのいくつかの例もプロス素数です

参考文献

  1. ^ Solinas, Jerome A. (1999).一般化メルセンヌ数(PDF) (技術レポート). ウォータールー大学応用暗号研究センター. CORR-99-39.
  2. ^ Solinas, Jerome A. (2011). 「一般化メルセンヌ素数」. Tilborg, Henk CA van; Jajodia, Sushil (編).暗号とセキュリティ百科事典. Springer US. pp.  509–510 . doi : 10.1007/978-1-4419-5906-5_32 . ISBN 978-1-4419-5905-8。
  3. ^米国特許 5159632、Richard E. Crandall、「暗号化システムにおける公開鍵交換の方法および装置」、1992 年 10 月 27 日発行、NeXT Computer, Inc. に譲渡。 
  4. ^連邦政府向け推奨楕円曲線(PDF) (技術レポート). NIST . 1999.
  5. ^ Craig-Wood, Nick. 「2^64-2^32+1を法とする整数DWT」www.craig-wood.com .
  6. ^ de Jesús Angel Angel, José; Morales-Luna, Guillermo (2010). 「固定サイズの小さな重みを持つソリナス素数」 Cryptology ePrint Archive, Paper 2010/058 .
  7. ^ Nath, Kaushik; Sarkar, Palash (2018), (擬似)メルセンヌ素数順序体における効率的な算術, 2018/985 , 2025年5月10日閲覧
「 https://en.wikipedia.org/w/index.php?title=Solinas_prime&oldid=1321323645」から取得