ソリナス素数

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

最初に${\displaystyle n}$を${\displaystyle 2^{m}}$進数で表すと以下のようになる

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

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

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

1. ↑ Solinas, Jerome A. (1999). Generalized Mersenne Numbers (PDF) (Technical report). Center for Applied Cryptographic Research, University of Waterloo. CORR-99-39。
2. ↑ Solinas, Jerome A. (2011). “Generalized Mersenne Prime”. Encyclopedia of Cryptography and Security. Springer US. pp. 509–510. doi:10.1007/978-1-4419-5906-5_32. ISBN 978-1-4419-5905-8. https://archive.org/details/encyclopediacryp00tilb_374 
3. ↑ US patent 5159632, Richard E. Crandall, "Method and apparatus for public key exchange in a cryptographic system", issued 1992-10-27, assigned to NeXT Computer, Inc.