二乗による累乗

数学とコンピュータプログラミングにおいて、二乗による累乗は、数の大きな正の整数累乗、またはより一般的には多項式や正方行列のような半群の要素の累乗を高速に計算するための一般的な方法です。いくつかのバリエーションは、一般的に二乗して乗算するアルゴリズムまたは二進累乗と呼ばれます。これらは、たとえばモジュラー演算や行列の累乗など、非常に一般的に使用できます。暗号化で使用される楕円曲線のように、加法表記が一般的に使用される半群の場合、この方法は倍加して加算とも呼ばれます。

この方法は、任意の整数に対して次のことが成り立つという観察に基づいています。 ${\displaystyle n>0}$$${\displaystyle x^{n}={\begin{cases}x\,(x^{2})^{(n-1)/2},&{\mbox{if }}n{\mbox{ is odd}}\\(x^{2})^{n/2},&{\mbox{if }}n{\mbox{ is even}}\end{cases}}}$$

指数nが0の場合、答えは1です。指数が負の場合、値を正の指数で書き直すことで前の式を再利用することができます。つまり、 $${\displaystyle x^{n}=\left({\frac {1}{x}}\right)^{-n}\,.}$$

これらを組み合わせると、次の再帰アルゴリズムとして直接実装できます。

In: 整数 x; 整数 n
 アウト: x n
 
 exp_by_squaring(x, n)
   n < 0 の場合
      exp_by_squaring(1 / x, -n) を返します。
   そうでなければn = 0の場合
      1 を返します。
   そうでない場合、nが偶数であれば
      exp_by_squaring(x * x, n / 2) を返します。
   そうでなければnが奇数ならば
      x * exp_by_squaring(x * x, (n - 1) / 2) を返します。
 終了関数

各再帰呼び出しでは、 nのバイナリ表現の最下位桁が削除されます。したがって、再帰呼び出しの数は、nのバイナリ表現のビット数になります。したがって、このアルゴリズムは、この数の平方と、 nのバイナリ表現の1の数に等しい、より少ない数の乗算を計算します。この対数演算数は、 n − 1 回の乗算を必要とする単純なアルゴリズムと比較されます。 ${\displaystyle \lceil \log _{2}n\rceil ,}$

このアルゴリズムは末尾再帰的ではありません。つまり、再帰呼び出しの回数にほぼ比例する量の補助メモリが必要になります。反復ごとのデータ量が増加する場合は、さらに多くなる可能性もあります。

次のセクションのアルゴリズムでは異なるアプローチが使用され、結果として得られるアルゴリズムでは同じ数の操作が必要ですが、結果を格納するために必要なメモリとほぼ同じ補助メモリを使用します。

このセクションで説明するバリアントは、次の式に基づいています。

${\displaystyle yx^{n}={\begin{cases}(yx)\,(x^{2})^{(n-1)/2},&{\mbox{if }}n{\mbox{ is odd}}\\y\,(x^{2})^{n/2},&{\mbox{if }}n{\mbox{ is even}}.\end{cases}}}$

この式をy = 1から再帰的に適用すると、最終的に指数は0になり、望ましい結果は左因数になります。

これは末尾再帰関数として実装できます。

  関数exp_by_squaring ( x , n )はexp_by_squaring2 ( 1 , x , n )を返します。関数exp_by_squaring2 ( y , x , n )は、 n < 0の場合はexp_by_squaring2 ( y , 1 / x , - n )を返します。それ以外の場合、n = 0の場合はy を返します。それ以外の場合、nが偶数の場合はexp_by_squaring2 ( y , x * x , n / 2 )を返します。それ以外の場合、 nが奇数の場合はexp_by_squaring2 ( x * y , x * x , ( n - 1 ) / 2 )を返します。  
       
     
              
           
                 
                     

反復バージョンのアルゴリズムも有界補助空間を使用し、次のように表される。

  関数exp_by_squaring_iterative ( x , n ) n < 0の場合、x := 1 / x 、n := - n 、n = 0の場合、1を返すy := 1 、n > 1の場合、 nが奇数の場合、y := x * y 、n := n - 1 、x := x * x 、n := n / 2 、x * yを返す  
        
          
        
          
      
        
          
            
            
          
          
       

アルゴリズムの正しさは、計算中は不変であり、計算の始めでも終わりでも 変わらないという事実から生まれます。${\displaystyle yx^{n}}$${\displaystyle 1\cdot x^{n}=x^{n}}$${\displaystyle yx^{1}=xy}$

これらのアルゴリズムは、前のセクションのアルゴリズムとまったく同じ数の演算を使用しますが、乗算は異なる順序で実行されます。

簡単に分析すると、このようなアルゴリズムは平方と最大で乗算を使用することがわかります。ここで、 は床関数を表します。より正確には、乗算の回数は、 nの2 進展開に存在する 1 の数より 1 少ないです。nが約 4 より大きい場合、これは単純に底をそれ自体で繰り返し乗算するよりも計算上効率的です。 ${\displaystyle \lfloor \log _{2}n\rfloor }$${\displaystyle \lfloor \log _{2}n\rfloor }$${\displaystyle \lfloor \;\rfloor }$

それぞれの平方は前の平方の約2倍の桁数になるので、2つのd桁の数の乗算が、ある固定kに対してO( dk ⁾回の演算で実装される場合、 xn^を計算する複雑さは次のように表される。

${\displaystyle \sum \limits _{i=0}^{O(\log n)}{\big (}2^{i}O(\log x){\big )}^{k}=O{\big (}(n\log x)^{k}{\big )}.}$

このアルゴリズムは、指数を 2 ^{k を}底として展開した後、 x ⁿの値を計算します。これは1939 年にBrauerによって初めて提案されました。以下のアルゴリズムでは、関数f (0) = ( k , 0) およびf ( m ) = ( s ,  u )を使用します。ここで、 m = u ·2 ^sで、 uは奇数 です。

アルゴリズム：

入力

Gの要素x、パラメータk > 0、非負整数n = ( n _{l −1}、n _{l −2}、 ...、n ₀ ) _{2 ^k} 、および事前計算された値。${\displaystyle x^{3},x^{5},...,x^{2^{k}-1}}$

出力

Gの要素x ⁿ

y := 1; i := l - 1
ただし、 i ≥ 0の場合
    (s, u) := f(n i )
    に対して、 j := 1からk - sまで
        、y := y 2を実行する
    y := y * x u
    に対して、 j := 1からsまで
        、y := y 2 を実行する
    私 := 私 - 1
yを
返す

最適な効率を得るには、kは^[1]を満たす最小の整数でなければならない。

${\displaystyle \lg n<{\frac {k(k+1)\cdot 2^{2k}}{2^{k+1}-k-2}}+1.}$

^{この方法は、 2 k}進法の効率的な変形です。たとえば、2 進展開 (110 001 110) _{2 を持つ指数 398 を計算するには、 2} ^k進法アルゴリズムを使用して長さ 3 のウィンドウを取り、 1、x ³、x 6 、x ¹²、x ^{24 、} x ⁴⁸、x ⁴⁹、x 98 、^{x 99 、x 198}、x ¹⁹⁹、x ^{398を計算します。ただし、 1、x 3}、x ⁶、x ¹²、x ²⁴、x ⁴⁸、 x 96 、x ¹⁹² 、 x ¹⁹⁹、x ³⁹⁸を計算することもできます。これにより、乗算が 1 つ節約され、 (110 001 110) ₂^を評価することになります^。

一般的なアルゴリズムは次のとおりです。

アルゴリズム：

入力

Gの要素x、非負の整数n =( n _{l −1}、n _{l −2}、 ...、n ₀ ) ₂、パラメータk > 0 、および事前に計算された値。${\displaystyle x^{3},x^{5},...,x^{2^{k}-1}}$

出力

要素x ⁿ ∈ G。

アルゴリズム：

y := 1; i := l - 1
 i > -1の場合、 n i = 0の
    場合、 
        y := y 2 ' i := i - 1
    の場合、そうでない場合
        s := max{i - k + 1, 0}
        n s = 0 の場合、 
            s := s + 1 [注 1]
        とし、 h := 1からi - s + 1の場合、 
            y := y 2 
        u := (n i , n i-1 , ..., n s ) 2 
        y := y * x uとする。
        私 := s - 1
yを
返す

指数計算アルゴリズムの多くは、サイドチャネル攻撃に対する防御策を提供していません。つまり、攻撃者は二乗と乗算のシーケンスを観察することで、計算に関係する指数を（部分的に）復元できます。これは、多くの公開鍵暗号システムのように指数を秘密にしておく必要がある場合に問題になります。「モンゴメリのはしご」^[2]と呼ばれる手法がこの懸念に対処します。

正の非ゼロ整数n = ( n _{k −1} ... n ₀ ) ₂（n _{k−1 = 1）の}2進展開が与えられた場合、 x ^{n は}次のように計算できます。

x 1 = x; x 2 = x 2
 、 i = k - 2 から 0の場合、 n i = 0の場合、 
        x 2 = x 1 * x 2、
        x 1 = x 1 2 、そうでない場合、 x 1 = x 1 * x 2、x 2 = x 2 2、 x 1を返す
    
    

このアルゴリズムは、固定された一連の演算 ( log  nまで) を実行します。つまり、ビットの特定の値に関係なく、指数の各ビットに対して乗算と二乗が行われます。2 倍乗算による同様のアルゴリズムが存在します。

モンゴメリのはしごのこの特定の実装は、キャッシュタイミング攻撃に対してまだ保護されていません。秘密指数のビットの値に応じて異なる変数がアクセスされるため、メモリアクセスの遅延が攻撃者に観測される可能性があります。最新の暗号化実装では、「スキャッター」技術を使用して、プロセッサが常に高速なキャッシュをミスするようにしています。^[3]

底が固定で指数が変化する場合にx ^{n を}計算するために使用できる方法はいくつかあります。ご覧のとおり、これらのアルゴリズムでは事前計算が重要な役割を果たします。

Yao 法は、指数が基数 b = 2 k で展開され、計算が上記のアルゴリズムで実行される 2 k 進法と直交します。n ^、 ni 、^b、 b i_を整数とし_ます。

指数nは次のように表される。

${\displaystyle n=\sum _{i=0}^{w-1}n_{i}b_{i},}$

どこにすべての。 ${\displaystyle 0\leqslant n_{i}<h}$${\displaystyle i\in [0,w-1]}$

x _i = x ^{b _i}とします。

次にアルゴリズムは等式を使用する

${\displaystyle x^{n}=\prod _{i=0}^{w-1}x_{i}^{n_{i}}=\prod _{j=1}^{h-1}{\bigg [}\prod _{n_{i}=j}x_{i}{\bigg ]}^{j}.}$

Gの要素xと、上記の形式で記述された指数n、および事前計算された値x ^{b ₀} ... x ^{b _{w −1}}が与えられると、要素x ^{n は}以下のアルゴリズムを使用して計算されます。

y = 1、u = 1、j = h - 1、
 j > 0の場合、 i = 0からw - 1の場合、 n i = jの場合、 
            u = u × x b iとなります。
    
        
    y = y × u
    j = j - 1
yを
返す

h = 2 ^k、bi = h ⁱと設定すると、n _{i の}値はh を底とするnの数字に過ぎません。 Yao の方法では、まず最も高いべき乗に現れる x i を u に集めます_。次のラウンドで_は、べき乗を持つものもuに集められます。変数yは、最初のuで⁠ ⁠回乗算され、次に高いべき乗で⁠ ⁠回乗算され、以下同様に続きます。アルゴリズムでは乗算が使用され、 x n^を計算するには⁠ ⁠要素を格納する必要があります。^[1]${\displaystyle h-1}$${\displaystyle h-2}$${\displaystyle h-1}$${\displaystyle h-2}$${\displaystyle w+h-2}$${\displaystyle w+1}$

ユークリッド法は、 PD Rooij による「事前計算とベクトル加算チェーンを使用した効率的な累乗」で初めて導入されました。

グループG（nは自然数） で計算するこの方法は、アルゴリズムが以下に示すように、次の等式を再帰的に使用します。${\displaystyle x^{n}}$

${\displaystyle x_{0}^{n_{0}}\cdot x_{1}^{n_{1}}=\left(x_{0}\cdot x_{1}^{q}\right)^{n_{0}}\cdot x_{1}^{n_{1}\mod n_{0}},}$

ここで、指数n _1をn ₀でユークリッド除算すると、商qと剰余n ₁ mod n ₀が返されます。 ${\displaystyle q=\left\lfloor {\frac {n_{1}}{n_{0}}}\right\rfloor }$

グループGの基数元xと、Yao 法で記述された指数が与えられると、元は事前に計算された値を使用して計算され、次に以下のアルゴリズムが実行されます。 ${\displaystyle n}$${\displaystyle x^{n}}$${\displaystyle l}$${\displaystyle x^{b_{0}},...,x^{b_{l_{i}}}}$

ループを開始します
    。となるものを検索${\displaystyle M\in [0,l-1]}$ します。となるものを検索します。となる場合はループを中断します。となるようにしてから、とします。再帰的に計算してから、とします。ループを終了し、
戻ります。${\displaystyle \forall i\in [0,l-1],n_{M}\geq n_{i}}$
    ${\displaystyle N\in {\big (}[0,l-1]-M{\big )}}$ ${\displaystyle \forall i\in {\big (}[0,l-1]-M{\big )},n_{N}\geq n_{i}}$
     ${\displaystyle n_{N}=0}$
     ${\displaystyle q=\lfloor n_{M}/n_{N}\rfloor }$  ${\displaystyle n_{N}=(n_{M}{\bmod {n}}_{N})}$
    ${\displaystyle x_{M}^{q}}$  ${\displaystyle x_{N}=x_{N}\cdot x_{M}^{q}}$
 ${\displaystyle x^{n}=x_{M}^{n_{M}}}$

アルゴリズムは、まずn _iの中で最大値を見つけ、次に{ n _i \ i ≠ M }の集合内で最大値を見つけます。次にx _{M を}q乗し、この値にx _Nを掛け、この計算の結果をx _Nに割り当て、 n _Mにn _Nを法とした値n _Mを 割り当てます。

このアプローチは、特性がゼロでない半群でも機能し、例えば、ある数を法とする大きな指数を高速に計算できます。特に暗号学では、 qを法とする整数の環のべき乗を計算するのに便利です。例えば、

13789 ⁷²²³⁴¹ (mod 2345) = 2029

13789 ⁷²²³⁴¹を計算し、それを2345 で割った余りを求めるという単純な方法を使用した場合、非常に長い時間と多くの記憶領域が必要になります。13789 を 2 乗し、それを 2345 で割った余りを求め、その結果に 13789 を掛ける、というより効率的な方法を使用した場合でも、長い時間がかかります。

上記のexp-by-squaredアルゴリズムを適用すると、「*」はx * y = xy mod 2345 (つまり、乗算の後に余りのある除算が続く) として解釈され、整数の乗算と除算は 27 回のみになり、これらはすべて 1 つのマシン ワードに格納できます。通常、これらのアプローチのいずれでも、モジュラー乗算 は2log ₂ (722340) ≤ 40 回未満になります。

このアプローチは、以下のいずれかの規則を使用して、 グループ内の整数乗を計算するためにも使用できます。

べき乗( x , −n ) = べき乗( x ⁻¹ , n )、

べき乗( x , n )=(べき乗( x , n )) ⁻¹。

このアプローチは非可換半群でも機能し、行列の累乗を計算するためによく使用されます。

より一般的には、このアプローチは、二項演算がべき乗結合的であるすべてのマグマにおいて正の整数指数で機能します。

特定の計算では、 Gの逆元が「高速」であるか、事前に計算されている場合、負の係数を許可して基数の逆元を使用する方が効率的である場合があります。たとえば、 x ^{2 k −1}を計算する場合、バイナリ法ではk −1 回の乗算とk −1回の二乗が必要です。ただし、 k 回の二乗を実行してx ^{2 k}を取得し、次にx ⁻¹を乗算してx ^{2 k −1}を取得することもできます。

この目的のために、基数bの整数nの符号付き数字表現を次のように 定義する。

${\displaystyle n=\sum _{i=0}^{l-1}n_{i}b^{i}{\text{ with }}|n_{i}|<b.}$

符号付きバイナリ表現は、特定の選択b = 2およびに対応します。これは で表されます。この表現を計算する方法はいくつかあります。表現は一意ではありません。たとえば、n = 478の場合、2 つの異なる符号付きバイナリ表現が および で与えられます。ここで、は−1 を表すために使用されます。バイナリ方式では、 nの基数 2 表現のすべての非ゼロ要素に対して乗算が計算されるため、非ゼロ要素の数が最も少ない、つまりハミング重みが最小の符号付きバイナリ表現を見つけることが目的です。これを行う 1 つの方法は、を満たしで表された非隣接形式、または略して NAFで表現を計算することです。たとえば、478 の NAF 表現は です。この表現は常にハミング重みが最小です。を持つ特定の整数の NAF 表現を計算する簡単なアルゴリズムは次のとおりです。 ${\displaystyle n_{i}\in \{-1,0,1\}}$${\displaystyle (n_{l-1}\dots n_{0})_{s}}$${\displaystyle (10{\bar {1}}1100{\bar {1}}10)_{s}}$${\displaystyle (100{\bar {1}}1000{\bar {1}}0)_{s}}$${\displaystyle {\bar {1}}}$ ${\displaystyle n_{i}n_{i+1}=0{\text{ for all }}i\geqslant 0}$${\displaystyle (n_{l-1}\dots n_{0})_{\text{NAF}}}$${\displaystyle (1000{\bar {1}}000{\bar {1}}0)_{\text{NAF}}}$${\displaystyle n=(n_{l}n_{l-1}\dots n_{0})_{2}}$${\displaystyle n_{l}=n_{l-1}=0}$

${\displaystyle c_{0}=0}$i = 0からl − 1まで
の場合、戻り値
  ${\displaystyle c_{i+1}=\left\lfloor {\frac {1}{2}}(c_{i}+n_{i}+n_{i+1})\right\rfloor }$
  ${\displaystyle n_{i}'=c_{i}+n_{i}-2c_{i+1}}$
${\displaystyle (n_{l-1}'\dots n_{0}')_{\text{NAF}}}$

小山と鶴岡による別のアルゴリズムでは、 という条件は不要ですが、それでもハミング重みは最小化されます。 ${\displaystyle n_{i}=n_{i+1}=0}$

二乗による累乗は、次善の加算連鎖累乗アルゴリズムと見なすことができます。つまり、指数の倍増 (二乗) と/または指数の1ずつの増加 ( xの乗算) のみで構成される加算連鎖によって指数を計算します。より一般的には、以前に計算された指数を合計できるようにすると ( xの累乗を乗算することにより)、より少ない乗算で累乗を実行できる場合があります (ただし、通常はより多くのメモリを使用します)。これが発生する最小の累乗は、 n = 15の場合です。

${\displaystyle x^{15}=x\times (x\times [x\times x^{2}]^{2})^{2}}$ （二乗、6倍）

${\displaystyle x^{15}=x^{3}\times ([x^{3}]^{2})^{2}}$ (最適な加算チェーン、x ³が再利用される場合は 5 回の乗算)。

一般に、与えられた指数に対する最適な加算チェーンを見つけることは難しい問題であり、効率的なアルゴリズムは知られていないため、最適なチェーンは通常、小さな指数に対してのみ使用されます (たとえば、小さな累乗のチェーンが事前に表にまとめられているコンパイラーなど)。ただし、最適ではないものの、追加の簿記作業とメモリ使用量を犠牲にして、2乗による累乗よりも乗算が少ないヒューリスティックアルゴリズムがいくつかあります。いずれにしても、乗算の回数がΘ (log n ) よりも遅くなることはないため、これらのアルゴリズムはせいぜい定数倍でしか2乗による累乗を漸近的に改善しません。

• モジュラー指数
• ベクトル加算チェーン
• モンゴメリ剰余乗算
• 非隣接形式
• 加算チェーン