モンゴメリ乗算

モンゴメリ乗算（モンゴメリじょうざん、英: Montgomery multiplication）とは、特に時間のかかる除算を実質的に行うことなく、乗算・加算・減算・シフト演算のみで、効率的に整数の積の剰余を求めることのできるアルゴリズムである。

応用において、特に暗号理論の分野では、数百ビットを超える法による冪剰余演算が重要な役割を果たし、このような冪剰余の演算にモンゴメリ乗算が用いられている。

モンゴメリ乗算の名称は提案者の Peter Montgomery に由来する。

モンゴメリ乗算はまた、モンゴメリ法 (英: Montgomery method) 、モンゴメリ剰余乗算 (英: Montgomery modular multiplication) とも呼ばれる。

概要

モンゴメリ乗算のアイデアは、 N > 0 {\displaystyle N>0} を法とした合同算術に関して、演算したい値を、ある定数 R {\displaystyle R} を掛けた表現（ここではモンゴメリ表現と呼んでおく）に変換し、この表現によってすべての計算を行った後、最後に元の領域での表現に逆変換することである。

モンゴメリ表現での加減算はそのまま実行した後、負または N {\displaystyle N} 以上のときのみ N {\displaystyle N} の加減をするだけでよい。 しかし乗算では R {\displaystyle R} が余分に残るので、 R − 1 {\displaystyle R^{-1}} を掛けて N {\displaystyle N} による剰余を求める処理を行う必要がある。 この処理をモンゴメリリダクションといい、 R {\displaystyle R} をうまく選ぶことにより効率的に計算することができる。

アルゴリズム

モンゴメリリダクション

上述したように、モンゴメリリダクションは、モンゴメリ乗算の基本となる演算である。 N {\displaystyle N} を法とする R {\displaystyle R} に関する T {\displaystyle T} （ 0 ≤ T < N R {\displaystyle 0\leq T<NR} ）のモンゴメリリダクションは

MR ( T ) = T R − 1 mod N {\displaystyle {\mbox{MR}}(T)=TR^{-1}{\bmod {N}}}

と定義される。 ここで、 R {\displaystyle R} は R > N {\displaystyle R>N} および gcd ( N , R ) = 1 {\displaystyle \gcd(N,R)=1} （つまり N {\displaystyle N} と互いに素）なる任意の整数であり、 R − 1 {\displaystyle R^{-1}} は R R − 1 ≡ 1 ( mod N ) {\displaystyle RR^{-1}\equiv 1{\pmod {N}}} なるモジュラ逆数である。

モンゴメリリダクションは次の手続きで計算できるが、 R {\displaystyle R} として、 mod R {\displaystyle {\bmod {R}}} と / R {\displaystyle /R} の計算が簡単になるような値（例えば2進数であれば2の冪）を選ぶことにより、除算を実質的に行う必要がなくなり効率的に計算できる。 ここで、 N ′ {\displaystyle N'} は N N ′ ≡ − 1 ( mod R ) {\displaystyle NN'\equiv -1{\pmod {R}}} なる値であり、 x R − y N = 1 {\displaystyle xR-yN=1} を満たす 0 < y < R {\displaystyle 0<y<R} として、拡張されたユークリッドの互除法や#Rが2の冪の時のN'の効率的な求め方などであらかじめ求めておく。 同時に得られる 0 < x < N {\displaystyle 0<x<N} は上述の R − 1 {\displaystyle R^{-1}} である。

t ← ( T + ( T N ′ mod R ) N ) / R {\displaystyle t\leftarrow (T+(TN'{\bmod {R}})N)/R}
if t ≥ N {\displaystyle t\geq N} then return t − N {\displaystyle t-N} else return t {\displaystyle t}

モンゴメリリダクション計算手続きの正当性

この手続きの正当性は次のように示される。 まず、

T + ( T N ′ mod R ) N ≡ T + T N ′ N ≡ T − T ≡ 0 ( mod R ) {\displaystyle T+(TN'{\bmod {R}})N\equiv T+TN'N\equiv T-T\equiv 0{\pmod {R}}}

より、 / R {\displaystyle /R} が割り切れて t {\displaystyle t} が整数であることがわかる。 次に、

t R ≡ T + ( T N ′ mod R ) N ≡ T ( mod N ) {\displaystyle tR\equiv T+(TN'{\bmod {R}})N\equiv T{\pmod {N}}}

より、 t ≡ T R − 1 ( mod N ) {\displaystyle t\equiv TR^{-1}{\pmod {N}}} である。 最後に、

T < R N {\displaystyle T<RN} , ( T N ′ mod R ) N < R N {\displaystyle (TN'{\bmod {R}})N<RN}

より、 0 ≤ t = ( T + ( T N ′ mod R ) N ) / R < 2 N {\displaystyle 0\leq t=(T+(TN'{\bmod {R}})N)/R<2N} であるため、手続きが返す値は N {\displaystyle N} より小さい。

モンゴメリ表現への変換と逆変換

整数 0 ≤ a < N {\displaystyle 0\leq a<N} をモンゴメリ表現 A {\displaystyle A} に変換するためには、 R {\displaystyle R} を掛けて N {\displaystyle N} による剰余を求めればよいので、あらかじめ R 2 = R 2 mod N {\displaystyle R_{2}=R^{2}{\bmod {N}}} を用意して、 A ← MR ( a R 2 ) {\displaystyle A\leftarrow {\mbox{MR}}(aR_{2})} を求めればよい。

逆変換はモンゴメリリダクションそのものであり、 a ← MR ( A ) {\displaystyle a\leftarrow {\mbox{MR}}(A)} である。

乗算剰余演算

被乗数 0 ≤ a < N {\displaystyle 0\leq a<N} と乗数 0 ≤ b < N {\displaystyle 0\leq b<N} の乗算剰余 c = a b mod N {\displaystyle c=ab{\bmod {N}}} は、上述の変換と逆変換を用いて、

A ← MR ( a R 2 ) {\displaystyle A\leftarrow {\mbox{MR}}(aR_{2})} , B ← MR ( b R 2 ) {\displaystyle B\leftarrow {\mbox{MR}}(bR_{2})}
C ← MR ( A B ) {\displaystyle C\leftarrow {\mbox{MR}}(AB)}
c ← MR ( C ) {\displaystyle c\leftarrow {\mbox{MR}}(C)}

により求められる。

しかし、単純に乗算剰余を1回だけ求めたい場合には、

c ← MR ( MR ( a b ) R 2 ) {\displaystyle c\leftarrow {\mbox{MR}}({\mbox{MR}}(ab)R_{2})}

とする方が効率的である。

冪剰余演算

冪剰余 a k mod N {\displaystyle a^{k}{\bmod {N}}} を求めたい場合、まず a {\displaystyle a} をモンゴメリ表現に変換しておき、 A k {\displaystyle A^{k}} の計算に出現する乗算のたびに積にモンゴメリリダクションを行っていけば、最後の結果に対して逆変換することによって結果を得ることができる。

通常の冪の計算ではバイナリ法などが効率的であるが、冪剰余の計算においても、同様の効率化がそのまま利用できる。

Rが2の冪の時のN'の効率的な求め方

Rが2の冪である場合には、計算機向けの効率的な求め方が存在する。

N N ′ ≡ − 1 ( mod R ) {\displaystyle NN'\equiv -1{\pmod {R}}}

は

N N ′ ≡ R − 1 ( mod R ) {\displaystyle NN'\equiv R-1{\pmod {R}}}

であり、Rが2の冪であるためR-1は二進数表記で全てのビットが1になる。また2の冪での剰余を求めることは即ち二進数表記での下位ビットを取り出すことである。なのでこれは実質的に、NN'の二進数表記の下位ビット全てが1になるN'を求めることに相当する。 

int result = 0;
int t = 0;
int r = R;
int i = 1;

while( r > 1 ) /* Rのトップビットを除いたビット数分繰り返す */
{
  if( !( t % 2 ) ) /* ゼロになっているビットがあったら、N'のその部分を1にする（NはRと互いに素なので必ず奇数） */
  {
    t += N; /* 掛け算だが、二進数一桁の掛け算なので実質は足し算 */
    result += i; /* N'のその部分を1にする */
  }
  t /= 2; /* 必ず端数が出るが切り捨てる */
  r /= 2; /* Rは2の冪なので、絶対端数は出ない */
  i *= 2;
}
/* return result; この時点で N' == result */

参考文献

  • Peter Montgomery, "Modular Multiplication Without Trial Division," Math. Computation, vol. 44, pp. 519–521, 1985.