ソリナス素数のソースを表示

[[数学]]において、'''ソリナス素数'''（ソリナスそすう、''Solinas prime''）または'''一般化メルセンヌ素数'''（いっぱんかメルセンヌそすう、''Generalized Mersenne prime''）とは、[[素数]]で<math>f(2^m)</math>の形を持つものである。(<math>f(x)</math>は小さい整数係数を伴う低次の多項式とする<ref>{{cite tech report|first=Jerome A.|last=Solinas|title=Generalized Mersenne Numbers|number=CORR-99-39|institution=Center for Applied Cryptographic Research, University of Waterloo|year=1999|url=http://cacr.uwaterloo.ca/techreports/1999/corr99-39.pdf}}</ref><ref>{{cite book |title=Encyclopedia of Cryptography and Security |url=https://archive.org/details/encyclopediacryp00tilb_374 |url-access=limited |first=Jerome A. |last=Solinas |editor-first1=Henk C. A. van |editor-last1=Tilborg |editor-first2=Sushil |editor-last2=Jajodia |date=2011 |publisher=Springer US |pages=[https://archive.org/details/encyclopediacryp00tilb_374/page/n549 509]–510 |doi=10.1007/978-1-4419-5906-5_32 |chapter=Generalized Mersenne Prime |isbn=978-1-4419-5905-8}}</ref>。)ソリナス素数は高速なモジュラー簡約(詳細は後述)に使えるため、暗号によく用いられる。

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

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

* [[メルセンヌ素数]]:<math>2^k-1</math>
* クランドール素数: <math>2^k-c</math>(<math>c</math>はある程度小さな[[奇数]]とする)<ref>{{Cite patent|country=US|number=5159632|status=patent|title=Method and apparatus for public key exchange in a cryptographic system|gdate=1992-10-27|fdate=1991-09-17|pridate=|invent1=Richard E. Crandall|assign1=NeXT Computer, Inc.|URL=http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=5159632.PN.&OS=PN/5159632&RS=PN/5159632}}</ref>

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

最初に<math>n</math>を<math>2^m</math>進数で表すと以下のようになる

: <math>n = \sum_{j=0}^{2d-1}A_j2^{mj}</math>

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

: <math>(B_0 ... B_{d-1}) = (A_0 ... A_{d-1}) + (A_d ... A_{2d-1})X</math>,

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

: <math>\sum_{j=0}^{d-1}B_j2^{mj}\equiv\sum_{j=0}^{2d-1}A_j2^{mj} \mod p</math>.

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

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

== 参考文献 ==
<references />
{{素数の分類}}
{{DEFAULTSORT:そりなすそすう}}
[[Category:素数]]
[[Category:整数の類]]
[[Category:数学に関する記事]]
[[Category:数論]]
[[Category:数学のエポニム]]