Zenn
🐍

Pythonのpow()関数の使い方と繰り返し2乗法の解説

に公開
Python
アルゴリズム
pow
tech

はじめに

Python の pow() 関数は単なるべき乗計算を超えて、暗号や数論などの領域でも広く使われる高機能な関数です。本記事では、pow() の基本的な使い方に加え、繰り返し2乗法の仕組みや ** 演算子とのパフォーマンス比較も交えて解説します。

pow() とは

Python 組み込みの pow() 関数は、次のように使います：

pow(base, exp[, mod])
  • base：底（a）
  • exp：指数（b）
  • mod（任意）：a^b % mod を高速に計算（整数のみ）

pow(a, b) は a ** b と同等ですが、pow(a, b, c) は (a ** b) % c より高速に動作します。

前提条件

以下の理解があると読みやすいです：

  1. Python の基本的な文法（関数、演算子）
  2. for 文と if 文などの制御構文
  3. 数値演算（べき乗、剰余）

手順

1. 通常のべき乗との違い

print(pow(2, 10))       # 1024
print(2 ** 10)          # 同じく 1024

この場合、pow() と ** は等価です。ただし次のように mod を加えると差が出てきます：

print(pow(2, 10, 1000))  # 24 （高速に計算）
print(2 ** 10 % 1000)    # 同じ結果だが内部的には非効率

2. 繰り返し2乗法（Exponentiation by Squaring）

pow(a, b, c) の内部では、「繰り返し2乗法」というアルゴリズムが使われています。これは次のような仕組みです：

def fast_pow(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp = exp // 2
    return result
  • 指数 exp を 2 で割っていく（ビットシフト的）
  • 偶数なら base を2乗して継続
  • 奇数なら result に掛け算して継続
  • → 計算量 O(log b) の高速アルゴリズム

ポイント 暗号化（RSAなど）や大規模数の処理で威力を発揮します。

3. ** 演算子とのベンチマーク比較

Python の timeit モジュールを使って、以下の比較を行います：

import timeit

# pow を使う
print(timeit.timeit('pow(123456789, 12345, 100000)', number=1000))

# ** を使って剰余
print(timeit.timeit('123456789 ** 12345 % 100000', number=1000))

結果（例）：

pow(): 約 0.01 秒
**+%: 約 0.15 秒

ポイント 大きな指数や剰余演算を含む場合は、pow() の方が圧倒的に速く、計算中のオーバーフローも回避できます。

完了とその後

このように、pow() 関数は単なる数学的な演算を超えて、効率性・安全性・拡張性に優れた関数です。

どのような場面で特に有用か？

以下のような場面では pow() の真価が特に発揮されます：

  • 暗号・セキュリティ領域：RSA暗号、Diffie-Hellman鍵交換などで頻出する大きな指数付きのモジュラ演算
  • 競技プログラミング：大きな数でのべき乗と剰余計算が非常に多く、計算速度とオーバーフロー回避が重要
  • 数論的アルゴリズム：フェルマーの小定理を使った素数判定、逆元計算など
  • 組込み系・メモリ制約下：大きなリストを作らずに、最小のステップで処理可能

RSA暗号とは？

RSA暗号は、公開鍵暗号方式の代表例で、非常に大きな数を使ったモジュラべき乗演算（pow()）によって、メッセージの暗号化・復号を行います。公開鍵で暗号化されたデータは、対応する秘密鍵でのみ復号できます。

# 簡略化された例：暗号化と復号
cipher = pow(message, e, n)       # 暗号化
plain = pow(cipher, d, n)         # 復号

Diffie-Hellman鍵交換とは？

Diffie-Hellman鍵交換は、2者が安全に共通の鍵を共有するためのプロトコルです。各自が秘密の指数を使って pow() によるモジュラべき乗を行い、最終的に同じ共通鍵を得ることができます。

# 共有の g と p を使って共通鍵を導出
A = pow(g, a_secret, p)
B = pow(g, b_secret, p)
shared_key_A = pow(B, a_secret, p)
shared_key_B = pow(A, b_secret, p)
# shared_key_A == shared_key_B

このような実装タイミングにおいて、pow() を選択することは性能と信頼性の両立に直結します。

まとめ

  • pow(a, b) は a ** b と同じだが、
  • pow(a, b, c) は (a ** b) % c よりずっと高速で安全
  • 内部で繰り返し2乗法を使って O(log b) に高速化されている
  • ** 演算子と比較して、大きな数の処理や暗号用途で特に有効
  • 実装タイミングとしては、数論・暗号・競技・メモリ制約下など幅広く適用可能

この pow() の特徴を理解することで、Python における数値処理の精度と効率性が大きく向上します。

Discussion