【Python】pow関数(べき乗・べき乗余り・モジュラ逆数)

サンプルコード

# べき乗の計算
print(
    pow(2, 3), #8
    pow(4, 0.5) #2.0
)

# べき乗の余り
print(pow(2, 3, 5)) #3

# modの逆元
print(
    pow(3, -1, 7), #5
    pow(3, -2, 7) #4
)

pow関数でできること

べき乗の計算

• pow(a, b) = $a^b$
  • pow(2, 3) → 8
  • pow(4, 0.5) → 2
    • 平方根の計算も可能

べき乗の余りの計算

• pow(a, b, c) = $a^b \div c$ の余り
  • pow(2, 3, 5) → 3
• a ** b % cでも同じことはできるが、リソース効率が良い
  • a ** b % cでエラーになる場合でも、pow(a, b, c)にするだけで、エラーを解消できるケースもあり
  • 繰り返し二乗法を使っているため

モジュラ逆数の計算(modの逆元)

• pow(a, -b, c)
  • $a^{-b} \equiv x \pmod c$ の$x$
  • → $a^b \times x \equiv 1 \pmod c$を満たす$x$
  • pow(3, -1, 7) → 5
  • $3 \times x \equiv 1 \pmod 7$を満たす$x$
  • pow(3, -2, 7) → 4
  • $3^2 \times x \equiv 1 \pmod 7$を満たす$x$

モジュラ逆数(modの逆元)とは？

• 逆元…逆数を一般的に拡張したもの

• 自然数Nについて考えると、

  • 加法の逆数 → -N
  • 乗法の逆数 → $\frac{1}{N}$
  • モジュラ逆数 → $N^{-1} \equiv x \pmod m$
  • → $N \times x \equiv 1 \pmod m$ を満たす$x$

• 利用例

  • RSA暗号の計算でモジュラ逆数を求める必要があり、その時に使用した
  • モジュラ逆数を使用しないと大きい計算量が必要なケースを一発で計算できる
  • https://andynotes-blog.com/rsa_encode_decode/#toc20