さらなる最適化

ウィキペディア小見出し辞書

さらなる最適化

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/11 10:07 UTC 版)

「冪剰余」の記事における「さらなる最適化」の解説

Pythonで右向きバイナリ法（指数の左端ビットから順に見ていく方法）を使った例である。 import mathdef bits(integer): #Gets number of bits in integer result = 0 while integer: integer >>= 1 result += 1 return resultdef power(base, exponent, modulo=None): #Allows fast exponentation with and without moduli result = 1 if not modulo: iteration = bits(exponent) while iteration >= 0: result *= result if (exponent >> iteration) & 1: result *= base iteration -= 1 else: firstModulus = base % modulo iteration = bits(exponent) while iteration >= 0: result = (result * result) % modulo if (exponent >> iteration) & 1: result = (result * firstModulus) % modulo iteration -= 1 return result この方法では、初期化後は変数 result（とループ変数の iteration）だけが変化していき、他の変数は変化しないという利点がある。このことからハードウェアによる暗号処理の実装を高速かつ安価に実装できる。 firstModulus = base % modulo という行は、ちょっとした最適化であり、前の手法にも適用可能である。 これらのバイナリ法では、指数の2進数表現の各ビットごとに自乗の計算が必要であり、そのビットが1であるときだけ乗算も行う。 右向きバイナリ法では、乗算回数をさらに減らす bit windowing optimization や sliding window optimization がある。 また、剰余を求める計算（%）の高速化として、モンゴメリ乗算がある。