2乗による指数計算

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

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

各二乗の結果、桁数は前の桁数の約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 while i ≥ 0 do (s, u) := f(n i ) for j := 1 to k - s do y := y 2 y := y * x u for j := 1 to s do y := y 2 i := i - 1 yを返す

最適な効率を得るには、k は^{[ 1 ]}を満たす最小の整数である必要がある。

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

^{この方法は、 2k}進法の効率的な変種です。例えば、2進展開が(110 001 110) _{2である指数398を計算するには、} ^2k進法アルゴリズムを使用して長さ3のウィンドウを取り、1、 ^x3、x6 ^、 x12 ^、 x24、x48 ^、 x49 ^、 x98 、^x99、^x198、x199 、^x398を計算します。しかし、1、x3、x6、x12、x24、x48、x96、x192、x199、x398を計算することもでき^、これ^は1回の^乗算を節約^し、⁽ 110 ⁰⁰¹ 110 ^{) 2を評価}_することに相当します^。

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

アルゴリズム：

入力

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 while i > -1 do if n i = 0 then 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 を実行します。 i := s - 1 yを返す

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

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

x 1 = x; x 2 = x 2 for i = k - 2 to 0 do if n i = 0 then x 2 = x 1 * x 2 ; x 1 = x 1 2 else x 1 = x 1 * x 2 ; x 2 = x 2 2 return x 1

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

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

底が固定され指数が変化する場合にx ⁿを計算する方法はいくつか存在する。ご覧のとおり、これらのアルゴリズムでは事前計算が重要な役割を果たす。

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を返す

ループ開始検索${\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}}}$。

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

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

13789 ⁷²²³⁴¹を計算し、それを2345 で割った余りを求めるという単純な方法を用いると、非常に長い時間と多くのストレージ容量が必要になります。より効率的な方法（13789 を二乗し、2345 で割った余りを求め、その結果に 13789 を掛ける、といった方法）を使っても、やはり時間がかかります。

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

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

Power( x , − n ) = Power( x ⁻¹ , n )、

Power( x , − n ) = (Power( x , n )) ⁻¹。

この手法は非可換半群でも有効であり、行列のべき乗を計算する際によく用いられる。

より一般的には、このアプローチは、二項演算が冪結合法則を満たすすべてのマグマにおいて、正の整数指数で機能します。

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

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

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

符号付きバイナリ表現は、特定の選択b = 2および${\displaystyle n_{i}\in \{-1,0,1\}}$。それは次のように表されます。${\displaystyle (n_{l-1}\dots n_{0})_{s}}$この表現を計算する方法はいくつかあります。表現は一意ではありません。たとえば、n = 478の場合、2 つの異なる符号付きバイナリ表現が与えられます。${\displaystyle (10{\bar {1}}1100{\bar {1}}10)_{s}}$そして${\displaystyle (100{\bar {1}}1000{\bar {1}}0)_{s}}$、 どこ${\displaystyle {\bar {1}}}$−1を表すために が使用されます。バイナリ法では、 nの 2 進数表現の非ゼロ要素ごとに乗算を計算するため、非ゼロ要素の数が最小の符号付きバイナリ表現、つまりハミング重みが最小の表現を見つけることに興味があります。これを行う 1 つの方法は、非隣接形式、略して NAFでの表現を計算することです。これは、次の条件を満たすものです。${\displaystyle n_{i}n_{i+1}=0{\text{ for all }}i\geqslant 0}$そして、${\displaystyle (n_{l-1}\dots n_{0})_{\text{NAF}}}$例えば、478のNAF表現は次のようになります。${\displaystyle (1000{\bar {1}}000{\bar {1}}0)_{\text{NAF}}}$この表現は常に最小のハミング重みを持ちます。与えられた整数の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}$; それでもハミング重みは最小化される。

二乗によるべき乗は、最適とは言えない加算連鎖べき乗アルゴリズムと見なすことができます。これは、指数を2倍にする（二乗する）操作を繰り返したり、指数を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}}$（最適な加算連鎖、3を再利用すれば5回乗算される^）。

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

• モジュラーべき乗
• ベクトル加算連鎖
• モンゴメリーのモジュラー乗算
• 非隣接形式
• 連鎖反応