C++でpow関数を実装してみた

pow関数とは

pow関数とはpow(x, y)で$x^{y}$を返す関数です。Pythonでは引数を３つとることでモジュロ計算をしてくれます。具体的に言うとpow(x, y, z)とすることで$x^{y}$ mod(z)の値を返します。今回は引数を3つとる場合に着目して内部の数学的な部分に触れたいと思います。

数学的解説

準備

繰り返し2乗法と呼ばれるメソッドが活用されています。単純に$x^{y}$を$x * x * x *...*x$と計算すると$O(N)$になります。
これを次のように各段階で指数を半減させることで計算量を$O(logN)$に削減できます。

    \begin{align}
    x^y &= x^{y/2}* x^{y/2}\\
    &=x^{y/2}*(x^{y/4}*x^{y/4})\\
    &=x^{y/2}*x^{y/4}*(x^{y/8} * x^{y/8})\\\
    &．．．\\
    &=x^{y/2}*x^{y/4}*(x^{y/8}) * ...* (x^{y/2^N}*x^{y/2^N})
    \end{align}

剰余演算にも同様の考え方を適用できます。

コード

実際に書いてみるとこうなります。

uint64_t my_pow(uint64_t x, uint64_t y, uint64_t z){
    uint64_t num = 1;
    
    while(y){
        if(y%2 == 1){
            num = (num*x)%z;
        }
        y = y/2;
        x = (x * x) % z;
    }
    return num;
}

uint64_tは64bitの符号なし整数型です。これよりも大きい数字を扱いたい方は"GMP"をインストールするなど別途準備が必要になります。
具体例を追っていくのが一番わかりやすいと思うので確認してみましょう。

例)
$x=7, y=11, z=5$と設定します。
コードを追っていくと、
$y=11(10)=1011(2)$のとき

    \begin{align}
    num&=7*1=2(7^{1}の余り)\\
    x&=7^{2}=4(7^{2}の余り)\\
    \end{align}

$y=5(10)=101(2)$のとき

    \begin{align}
    num&=2*4=3(7^{3}の余り)\\
    x&=(7^{2})^{2}=1(7^{4}の余り)\\
    \end{align}

$y=2(10)=10(2)$のとき

    \begin{align}
    num&=3(7^{3}の余り)\\
    x&=((7^{2})^{2})^{2}=1(7^{8}の余り)\\
    \end{align}

$y=1(10)=1(2)$のとき

    \begin{align}
    num&=3*1=3(7^{11}の余り)\\
    \end{align}

という動作になります。
要するに$x$は繰り返し2乗法で値を大きくしてそれぞれの余りを計算し、指数である$y$の桁が2進数で1で表されているとき(2で割った余りが１であるとき)$num$に$x$の値をスタックするという流れです。

注意

Pythonのpow関数では$y=-1$とすることで乗法逆元を求められますが、今回紹介した関数では符号ありの整数で扱っても求めることはできません。

最後に

暗号の研究でも計算量はかなり重要な要素になってきます。あとは抽象代数学の理解度がかなり大事です。暗号の勉強をしていくには今回出てきたmod計算が前提で話が進んでいきます。本記事を読んでくれて少しでも面白いと感じてくれた方は暗号分野にも興味を持ってくれたら嬉しいです。
内部関数の動作を気にするようになるとプログラムの書き方も変わってくると思うので色々試してみるといいんじゃないかなと思います。