バレット縮小

モジュラー算術において、バレット減算は1986年にPDバレットによって導入された減算アルゴリズムである。 ^[1]

素朴な計算方法

${\displaystyle c=a\,{\bmod {\,}}n\,}$

高速除算アルゴリズム を使用するのが最善です。バレット減算は、が定数であり、 であると仮定して、除算を乗算に置き換えて この演算を最適化するように設計されたアルゴリズムです。${\displaystyle n}$${\displaystyle a<n^{2}}$

歴史的には、値 については、完全な積 にバレット還元を適用することで計算されていました。最近、オペランドの1つで事前計算を実行できる場合は完全な積は不要であることが示されました。^{[2] [3]}${\displaystyle a,b<n}$${\displaystyle ab\,{\bmod {\,}}n\,}$${\displaystyle ab}$

関数が整数近似であるとは、 のときである。 を法とし、整数近似 を次のように 定義する。${\displaystyle \left[\,\right]:\mathbb {R} \to \mathbb {Z} }$${\displaystyle |\left[z\right]-z|\leq 1}$${\displaystyle n}$${\displaystyle \left[\,\right]}$${\displaystyle {\text{mod}}^{\left[\,\right]}\,n:\mathbb {Z} \to (\mathbb {Z} /n\mathbb {Z} )}$

${\displaystyle a\,{\text{mod}}^{\left[\,\right]}\,n=a-\left[a/n\right]n}$。

一般的な選択肢としては、floor、ceiling、rounding関数があります。 ${\displaystyle \left[\,\right]}$

一般的に、バレット乗算は2つの整数近似値を指定することから始まり、次のよう にかなり近い近似値を計算する。${\displaystyle \left[\,\right]_{0},\left[\,\right]_{1}}$${\displaystyle ab\,{\bmod {\,}}n}$

${\displaystyle ab-\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}n}$、

ここで、は固定定数であり、通常は 2 の累乗であり、乗算と除算を効率的に実行できるように選択されます。 ${\displaystyle R}$${\displaystyle R}$

このケースは、床関数の場合にPD Barrett ^[1]によって導入されました。 の一般的なケースはNTLで見つけることができます。^[2] 整数近似の見解とモンゴメリ乗算とバレット乗算の対応は、Hanno Becker、Vincent Hwang、Matthias J. Kannwischer、Bo-Yin Yang、およびShang-Yi Yangによって発見されました。^[3]${\displaystyle b=1}$${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\lfloor \,\rfloor }$${\displaystyle b}$

バレットは当初、値がマシンワードに収まる場合、上記のアルゴリズムの整数バージョンを検討しました。床関数の場合の考え方を、 と を使用して示します。 ${\displaystyle b=1}$${\displaystyle R=2^{k}}$

符号なし整数を計算する場合、明らかな類似法は による除算を使用することです。 ${\displaystyle a\,{\bmod {\,}}n}$${\displaystyle n}$

func Reduce ( a uint ) uint { q := a / n // 除算は暗黙的に結果の切り捨てを返します。return a - q * n }    
         
         

ただし、除算はコストが高く、暗号化設定では一部の CPU で定数時間命令ではない可能性があり、その場合、操作がタイミング攻撃の対象になります。したがって、バレット減算は値で近似します。これは、による除算が右シフトだけであるため、コストがかからないためです。 ${\displaystyle 1/n}$${\displaystyle m/2^{k}}$${\displaystyle 2^{k}}$

与えられたものに対する最適な値を計算するには、次の点を考慮してください。 ${\displaystyle m}$${\displaystyle 2^{k}}$

${\displaystyle {\frac {m}{2^{k}}}={\frac {1}{n}}\;\Longleftrightarrow \;m={\frac {2^{k}}{n}}}$

を整数にするには、何らかの方法で丸める必要があります。最も近い整数に丸めると、最良の近似値が得られますが、よりも大きくなる可能性があり、アンダーフローが発生する可能性があります。したがって、符号なし演算には が使用されます。 ${\displaystyle m}$${\displaystyle {2^{k}}/{n}}$${\displaystyle m/2^{k}}$${\displaystyle 1/n}$${\displaystyle m=\lfloor {2^{k}}/{n}\rfloor }$

したがって、上記の関数は次のように近似できます。

func Reduce ( a uint ) uint { q := ( a * m ) >> k // ">> k" は k のビットシフトを表します。return a - q * n }    
           
         

しかし、 であるため、その関数の の値は1 つ小さくなりすぎる可能性があり、したがって が一般に要求されるではなく の範囲内にあることが保証されます。条件付き減算により、これを修正できます。 ${\displaystyle m/2^{k}\leq 1/n}$qa${\displaystyle [0,2n)}$${\displaystyle [0,n)}$

func Reduce ( a uint ) uint { q := ( a * m ) >> k a -= q * n a >= n の場合{ a -= n } a を返す}    
          
        
        
          
    
     

が既知であると仮定します。これにより、を受け取る前に事前計算することができます。バレット乗算は を計算し、 の上位部分を で 近似し、近似値を減算します。 は の倍数であるため、結果の値 は を表します。 ${\displaystyle b}$${\displaystyle \left\lfloor {\frac {bR}{n}}\right\rfloor }$${\displaystyle a}$${\displaystyle ab}$${\displaystyle ab}$${\displaystyle \left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$${\displaystyle \left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$${\displaystyle n}$${\displaystyle ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$${\displaystyle ab\,{\bmod {\,}}n}$

符号なしモンゴメリ乗算は、 次のように 代表値を計算することを思い出してください。${\displaystyle ab\,{\bmod {\,}}n}$

${\displaystyle {\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}}$。

実際、この値は に等しくなります。 ${\displaystyle ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$

この主張は次のように証明されます。

${\displaystyle {\begin{aligned}&&&ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n\\&=&&ab-{\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor -\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)}{R}}\,n\\&=&&\left({\frac {abR}{n}}-a\left\lfloor {\frac {bR}{n}}\right\rfloor +\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {abR}{n}}-a{\frac {bR-\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {a\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {a\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&{\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}.\end{aligned}}}$

一般に、整数近似の場合、 ${\displaystyle \left[\,\right]_{0},\left[\,\right]_{1}}$

${\displaystyle ab-\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}\,n={\frac {a\left(bR\,{\text{mod}}^{\left[\,\right]_{0}}\,n\right)+\left(a\left(-bR\,{\text{mod}}^{\left[\,\right]_{0}}\,q\right)n^{-1}\,{\text{mod}}^{\left[\,\right]_{1}}\,R\right)n}{R}}}$^[3 ]

出力を で制限します 。 ${\displaystyle ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n={\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}\leq {\frac {an+Rn}{R}}=n\left(1+{\frac {a}{R}}\right)}$

同様の境界は他の種類の整数近似関数にも当てはまります。例えば、切り上げ関数 を選択した場合、${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil }$

${\displaystyle \left|ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rceil }{R}}\right\rceil \,n\right|=\left|{\frac {a\left(bR\,{\text{mod}}^{\pm }\,n\right)+\left(a\left(-bR\,{\text{mod}}^{\pm }\,n\right)n^{-1}\,{\text{mod}}^{\pm }\,R\right)n}{R}}\right|\leq \left|{\frac {a{\frac {n}{2}}+{\frac {R}{2}}n}{R}}\right|\leq {\frac {n}{2}}\left(1+{\frac {|a|}{R}}\right).}$

バレットが縮小を検討した主な動機は、 RSAの実装であり、問​​題となる値はほぼ確実にマシンワードのサイズを超えるでしょう。この状況で、バレットは上記の単一ワードバージョンを複数ワード値で近似するアルゴリズムを提供しました。詳細については、応用暗号ハンドブックのセクション14.3.3を参照してください。^[4]

多項式を逆にしてX進演算を使用することで、多項式除算にバレットアルゴリズムを使用することも可能です。^[5]

• モンゴメリ削減は別の同様のアルゴリズムです。