モジュラーべき乗

モジュラーべき乗とは、法を用いて行うべき乗演算のことです。これはコンピュータ科学、特に公開鍵暗号の分野で有用であり、ディフィー・ヘルマン鍵交換とRSA公開鍵／秘密鍵の両方で使用されています。

モジュラーべき乗とは、整数 $b$ (底) を $e$ 乗(指数) し、正の整数 $m$ (法)で割ったときの余り $cのことです。つまり、$ $c$ $=$ $b$ $e$ $mod$ $m$ $です。除算の定義から、 0 \leq$ $c$ $<$ $m$ が成り立ちます。

例えば、 $b = 5$ 、 $e = 3$ 、 $m = 13$ の場合、 $5 \div 3 = 125を$ $13$ で割ると、余りは $c = 8$ になります。

$b$ と $mが$ 互いに素である場合、 $b$ の法 $m$ における乗法逆元 $d$ を求めることで（例えば拡張ユークリッド互除法を用いるなど）、指数 $e$ を負にすることもできる。より正確には：

c = b e mod m = d - e mod m

、ただし

e < 0

および

b \cdot d \equiv 1 (mod m)

。

モジュラーべき乗は、非常に大きな整数に対しても効率的に計算できます。一方、モジュラー離散対数、つまり $b$ 、 $c$ 、 $m$ が与えられたときに指数 $e$ を求めることは難しいと考えられています。このような一方向関数的な性質から、モジュラーべき乗は暗号アルゴリズムへの応用候補として注目されています。

直接法

モジュラー指数を計算する最も直接的な方法は、 $b e を$ $直接計算し、次にこの数をm$ で割った余りを取ることです。b $= 4$ $、$ e $=$ $13$ 、 $m$ $= 497$ の場合に $c$ を計算してみましょう。

c \equiv 4 13 (mod 497)

電卓を使って 4 ÷ ¹³を計算すると、67,108,864 になります。この値を 497 で割った余りを求めると、答え $c$ は 445 となります。

$b$ は1 桁、 $eは 2 桁ですが、$ $b e の$ 値は8 桁になります。

強力な暗号化では、 $b$ は多くの場合、少なくとも 1024ビットです。^{[ 1 ]} $b = 5 \times 10 76$ および $e = 17$ を考えてみましょう。どちらも完全に妥当な値です。この例では、 $b$ は 77 桁、 $e$ は 2 桁ですが、値 $b e$ は 1,304 桁になります。このような計算は現代のコンピュータで可能ですが、このような数値の大きさが計算速度を大幅に低下させます。セキュリティを向上させるために $b$ と $e$ をさらに大きくすると、値 $b e$ は扱いにくくなります。

べき乗演算の実行に必要な時間は、動作環境とプロセッサによって異なります。上記の方法では、完了までに $Θ (e)回の乗算が必要です。$

メモリ効率の良い方法

数値を小さく保つには追加のモジュラ削減操作が必要になりますが、サイズが小さくなることで各操作が高速化され、全体として時間（およびメモリ）を節約できます。

このアルゴリズムは恒等式を利用します

(a \cdot b) mod m = [(a mod m) \cdot (b mod m)] mod m

修正されたアルゴリズムは以下のとおりです。

入力：整数 $b$ （底）、整数 $e$ （指数）、正の整数 $m$ （法）

出力：モジュラー指数 $c$ （

c = b e mod m）

$c = 1$ 、ループ変数 $e'$ $= 0$ で初期化する
e′ < eの間、
1. $e'$ を1増やす
2. $c$ $= ($ $b$ $\cdot$ $c$ $) mod$ $m$ を計算する
出力 $c$

ループの各反復の最後に、式 $c \equiv b e' (mod m)$ が成り立つことに注意してください。アルゴリズムは、ループが $e$ 回実行されると終了します。その時点で、 $c には$ $b e mod m$ の結果が格納されます。

要約すると、このアルゴリズムは、 e′ が $e$ と等しくなるまで $e' を$ 1 ずつ増やします。各ステップで、前の反復の結果 $c$ に $b$ を掛け、その結果の積に対して剰余演算を実行することで、結果として得られる $c を$ 小さな整数に保ちます。

$b = 4$ 、 $e = 13$ 、 $m = 497$ の例を再度示します。このアルゴリズムは、反復処理を 13 回実行します。

(e' = 1) c = (4 \cdot 1) mod 497 = 4 mod 497 = 4

(e' = 2) c = (4 \cdot 4) mod 497 = 16 mod 497 = 16

(e' = 3) c = (4 \cdot 16) mod 497 = 64 mod 497 = 64

(e' = 4) c = (4 \cdot 64) mod 497 = 256 mod 497 = 256

(e' = 5) c = (4 \cdot 256) mod 497 = 1024 mod 497 = 30

(e' = 6) c = (4 \cdot 30) mod 497 = 120 mod 497 = 120

(e' = 7) c = (4 \cdot 120) mod 497 = 480 mod 497 = 480

(e' = 8) c = (4 \cdot 480) mod 497 = 1920 mod 497 = 429

(e' = 9) c = (4 \cdot 429) mod 497 = 1716 mod 497 = 225

(e' = 10) c = (4 \cdot 225) mod 497 = 900 mod 497 = 403

(e' = 11) c = (4 \cdot 403) mod 497 = 1612 mod 497 = 121

(e' = 12) c = (4 \cdot 121) mod 497 = 484 mod 497 = 484

(e' = 13) c = (4 \cdot 484) mod 497 = 1936 mod 497 = 445

$したがって、 c$ の最終的な答えは、直接法と同様に 445 です。

最初の方法と同様に、この方法でも計算には $O(e)$ 回の乗算が必要です。ただし、これらの計算で使用される数値は最初のアルゴリズムの計算で使用される数値よりもはるかに小さいため、この方法では計算時間が少なくとも $O(e)$ 倍短縮されます。

擬似コードでは、このメソッドは次のように実行できます。

関数module_pow(base, exponent, modulus)は、 modulus = 1の場合、 0を返します。 c := 1 e_prime = 0からexponent-1まで 、c := (c * base) mod modulus を 実行し、 cを返す。

右から左への二進法

3つ目の方法は、モジュラべき乗を実行するための演算回数を大幅に削減しつつ、前述の方法と同じメモリ使用量を維持します。これは、前述の方法と、二乗によるべき乗（バイナリべき乗とも呼ばれる）と呼ばれるより一般的な原理を組み合わせたものです。

まず、指数 $eを$ 2進数表記に変換する必要があります。つまり、 $eは$ 次のように表すことができます。

e=\sum _{i=0}^{n-1}a_{i}2^{i}

このような表記では、 $e$ の長さは $n$ ビットです。a $i$ $は$ $、0 \leq$ $i$ $<$ $n$ を満たす任意の $i$ に対して、0 または 1 の値を取ることができます。定義により、 $a$ $n$ $- 1$ $= 1 です$ 。

$すると、 b e の$ 値は次のように表すことができます。

b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}b^{a_{i}2^{i}}

したがって、解 $c$ は次のようになります。

c\equiv \prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}

擬似コード

以下は、 Bruce Schneier著『Applied Cryptography』に基づく擬似コードの例です。^[²^] 入力base、exponent、modulus は、上記の式における $b$ 、 $e$ 、 $m$ に対応します。

関数module_pow(base, exponent, modulus)は、 modulus = 1の場合、 0 を 返します。Assert :: (modulus - 1) * (modulus - 1) は base をオーバーフローしません。 結果 := 1 base := base mod modulus while exponent > 0 do if (exponent mod 2 == 1) then result := (result * base) mod modulus 指数 := 指数 >> 1 base := (base * base) mod modulus return result

ループに初めて入ったとき、コード変数baseは $b$ と等しくなります。しかし、コードの 3 行目で繰り返し二乗することで、ループが完了するたびに変数baseは $b 2 i mod m$ と等しくなります。ここで $i$ はループが繰り返された回数です。（これにより、 $i はバイナリ指数$ exponentの次の有効ビットになります。ここで最下位ビットは指数₀です。）

最初のコード行は単純に乗算を実行します。 $\prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}$ $a$ がゼロの場合、実行中の合計が実質的に1倍されるため、コードは実行されません。一方、 $a$ が1の場合、変数base （元の基数の $b 2 i mod m$ の値を含む）が単純に乗算されます。

この例では、基数 $b$ を指数 $e = 13$ で累乗します。指数はバイナリで 1101 です。バイナリの桁は 4 個あるため、ループは 4 回実行され、値は $a 0 = 1、 a 1 = 0、 a 2 = 1$ 、 $a 3 = 1$ となります。

まず、結果を初期化します。 $R$ 1 に戻し、変数 $xに$ $b$ の値を保存します。

R\leftarrow 1\,(=b^{0}){\text{ および }}x\leftarrow b

。

ステップ1）ビット1は1なので、

R\leftarrow R\cdot x{\text{ }}(=b^{1})

;

セット

x\leftarrow x^{2}{\text{ }}(=b^{2})

。

ステップ2）ビット2は0なので、

R

をリセットしない。

セット

x\leftarrow x^{2}{\text{ }}(=b^{4})

。

ステップ3）ビット3は1なので、

R\leftarrow R\cdot x{\text{ }}(=b^{5})

;

セット

x\leftarrow x^{2}{\text{ }}(=b^{8})

。

ステップ4）ビット4は1なので、

R\leftarrow R\cdot x{\text{ }}(=b^{13})

;

これが最後のステップなので、 x

を二乗する必要はありません。

完了しました: $R$ は現在 $b^{13}$ 。

以下は上記の計算であり、 $b = 4 の$ $e = 13$ 乗を 497 で割った余りを計算しています。

初期化:

R\leftarrow 1\,(=b^{0})

そして

x\leftarrow b=4

。

ステップ1）ビット1は1なので、

R\leftarrow R\cdot 4\equiv 4{\pmod {497}}

;

セット

x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}

。

ステップ2）ビット2は0なので、

R

をリセットしない。

セット

x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}\equiv 256{\pmod {497}}

。

ステップ3）ビット3は1なので、

R\leftarrow R\cdot x{\text{ }}(=b^{5})\equiv 4\cdot 256\equiv 30{\pmod {497}}

;

セット

x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}\equiv 429{\pmod {497}}

。

ステップ4）ビット4は1なので、

R\leftarrow R\cdot x{\text{ }}(=b^{13})\equiv 30\cdot 429\equiv 445{\pmod {497}}

;

完了しました: $R$ は現在 $4^{13}\equiv 445{\pmod {497}}$ これは、以前のアルゴリズムで得られた結果と同じです。

このアルゴリズムの実行時間は $O(log$ 指数 $)です。$ 指数が大きい場合、このアルゴリズムは、実行時間が $O($ 指数 $)$ である以前の 2 つのアルゴリズムよりも大幅に高速化されます。たとえば、指数が 2 ²⁰ = 1048576 の場合、このアルゴリズムは 1048576 ステップではなく 20 ステップで済みます。

Luaでの実装

function modPow(b, e, m) if m == 1 then return 0 end local r = 1 b = b % m e > 0の間、 e % 2 == 1ならば r = (r*b) % m 終わり b = (b*b) % m e = e >> 1 -- Lua 5.2 以前のバージョンでは 'e = math.floor(e / 2)' を使用してください end return r end

左から右への二値化方式

指数部のビットを左から右の順で使用することもできます。実際には、通常は結果を何らかの法 $m$ $で割った余りを求めます。その場合、処理を進める前に各乗算結果(mod m)$ を減算します。ここでは簡略化のため、法の計算は省略します。この例では、計算方法を示します。 $b^{13}$ 左から右への二進数べき乗を使用します。指数は二進数で1101です。ビット数は4なので、4回の反復が必要です。

結果を1に初期化します。 $r\leftarrow 1\,(=b^{0})$ 。

ステップ1）

r\leftarrow r^{2}\,(=b^{0})

; ビット 1 = 1 なので、計算します

r\leftarrow r\cdot b\,(=b^{1})

;

ステップ2）

r\leftarrow r^{2}\,(=b^{2})

; ビット 2 = 1 なので、計算します

r\leftarrow r\cdot b\,(=b^{3})

;

ステップ3）

r\leftarrow r^{2}\,(=b^{6})

; ビット 3 = 0 なので、このステップは完了です。

ステップ4）

r\leftarrow r^{2}\,(=b^{12})

; ビット 4 = 1 なので、計算します

r\leftarrow r\cdot b\,(=b^{13})

。

最小乗算数

『コンピュータプログラミングの技法』第2巻「半数値アルゴリズム」463ページで、ドナルド・クヌースは、一部の主張とは異なり、この方法が常に最小の乗算回数を与えるとは限らないと指摘している。最も小さな反例は15のべき乗で、2進法では6回の乗算が必要となる。代わりに、 2回の乗算でx ³を作り、次にx ³を2乗してx ⁶を作り、次にx ⁶を2乗してx ¹²を作り、最後にx ¹²とx ^{3を掛けて}x ^15を作ることで、わずか5回の乗算で目的の結果を得ることができる。しかし、その後の多くのページでは、このような数列を一般的にどのように考案できるかが説明されている。

一般化

行列

$各項がk$ 個の前の項の線形関数である定数再帰数列（フィボナッチ数列やペリン数列など）のm番目の項は $、$ 対応する $k$ $\times$ $k$ のコンパニオン行列 $A$ を用いて $A$ $m$ $mod$ $n$ を計算することで、効率的に $nを$ 法として計算できます。上記の方法は、この用途にも容易に適用できます。これは、例えば大きな数 $nの$ 素数判定などに利用できます。

擬似コード

ModExp(A, b, c)= $A b mod c$ の再帰アルゴリズム。ここで $A$ は正方行列である。

関数Matrix_ModExp(Matrix A, int b, int c)は 、 b == 0 の場合、 Iを返します// 単位行列 if (b mod 2 == 1) then return (A * Matrix_ModExp(A, b - 1, c)) mod c 行列 D := Matrix_ModExp(A, b / 2, c) return (D * D) mod c

有限巡回群

Diffie–Hellman鍵交換では、有限巡回群のべき乗演算が使用されます。上記のモジュラー行列のべき乗演算の方法は、明らかにこの文脈にも適用できます。モジュラー行列の乗算 $C \equiv AB (mod n)は、群の乗算$ $c = ab$ に単純に置き換えられます。

可逆的かつ量子的なモジュラーべき乗

量子コンピューティングでは、モジュラべき乗がショアのアルゴリズムのボトルネックとして現れ、可逆ゲートで構成される回路で計算する必要があり、さらに特定の物理デバイスに適した量子ゲートに分解することができます。さらに、ショアのアルゴリズムでは、各呼び出しでべき乗の底とモジュラスを知ることができ、さまざまな回路最適化が可能になります。^{[ 3 ]}

ソフトウェア実装

モジュラーべき乗はコンピュータサイエンスにおいて重要な演算であり、単純にべき乗して余りを取るよりもはるかに高速な効率的なアルゴリズム（上記参照）が存在するため、多くのプログラミング言語や任意精度整数ライブラリには、モジュラーべき乗を実行するための専用関数が用意されています。

Pythonの組み込みpow()（べき乗）関数オプションの3番目の引数としてモジュラスを受け取ります
.NET Frameworkのクラスには、モジュラーべき乗を実行するメソッドBigIntegerがあります。ModPow()
Javaのjava.math.BigIntegerクラスには、modPow()モジュラべき乗を実行するメソッドがあります。
MATLABのpowermodSymbolic Math Toolbox の関数
Wolfram LanguageにはPowerMod機能があります。
PerlのMath::BigIntモジュールにはbmodpow()メソッドがありますモジュラーべき乗を実行する
Rakuには組み込みのルーチンがありますexpmod。
Goのbig.Int型にはExp()（べき乗）メソッドが含まれていますその3番目のパラメータがnilでない場合、それはモジュラスです
PHPのBC Mathライブラリにはbcpowmod()関数がありますモジュラーべき乗を実行する
GNU多倍長演算ライブラリ(GMP) ライブラリにはmpz_powm()関数が含まれていますモジュラーべき乗を実行する
FileMaker@PowerMod() Pro用カスタム関数（1024ビットRSA暗号化の例付き）
RubyのopensslパッケージにはOpenSSL::BN#mod_expメソッドがありますモジュラーべき乗演算を実行する。

参考文献

↑ 「Weak Diffie–Hellman and the Logjam Attack」。weakdh.org 。2019年5月3日取得。
↑シュナイアー 1996、p. 244。
↑ IL Markov、 M . Saeedi (2012)。「モジュラー乗算とべき乗のための定数最適化量子回路」。Quantum Information and Computation。12 ( 5–6 ) : 0361–0394。arXiv : 1202.6614。Bibcode : 2012arXiv1202.6614M。doi : 10.26421 / QIC12.5-6-1。S2CID 16595181。

外部リンク

シュナイアー、ブルース（1996）。応用暗号：プロトコル、アルゴリズム、およびC言語によるソースコード、第2版（第2 版）。ワイリー。ISBN 978-0-471-11709-4。
ポール・ギャレット、高速モジュラーべき乗計算Javaアプレット
Gordon, Daniel M. (1998). "高速べき乗法の概観" (PDF) . Journal of Algorithms . 27 (1). Elsevier BV: 129– 146. doi : 10.1006/jagm.1997.0913 . ISSN 0196-6774 .

[1] 「Weak Diffie–Hellman and the Logjam Attack」。weakdh.org 。2019年5月3日取得。

[schneier96p244-2] シュナイアー 1996、p. 244。

[3] IL Markov、 M . Saeedi (2012)。「モジュラー乗算とべき乗のための定数最適化量子回路」。Quantum Information and Computation。12 ( 5–6 ) : 0361–0394。arXiv : 1202.6614。Bibcode : 2012arXiv1202.6614M。doi : 10.26421 / QIC12.5-6-1。S2CID 16595181。

[ 1 ]

[

[ 3 ]