中国の剰余定理のアルゴリズム(Algorithm.10.3)

(Gathen and Gerhard 2013) を参考に中国の剰余アルゴリズムを実装している。

“10.3 Fast Chinese remaindering” に6つの疑似コードがある。

• Algorithm.10.3
• Algorithm.10.14
• Algorithm.10.16
• Algorithm.10.18
• Algorithm.10.20
• Algorithm.10.22

上記をPythonで実装しようと考えた。

このアルゴリズムは他のアルゴリズムから利用される補助的なものである。本文では多項式環を扱えるように一般化しているが、今回は \(\mathbb{Z}/p\mathbb{Z}\) だけを扱うことにする。

入力は互いに素な数である。入力のサイズはパラメータ \(k\) で決定する。 \(r=2^{k}\) 個の値を入力とすることになる。出力は \(r \times r\) の行列となる。

k=2として具体的な計算手順を実行する。入力は \(r=2^{k}=4\) の数 \(m_{1},m_{2},m_{3},m_{4}\) とする。出力となる行列 \(M\) を \(r\times r=4×4\) の大きさで初期化する。

\begin{pmatrix}
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
\end{pmatrix}

初期化した行列の1行目に入力の数を配置する。

\begin{pmatrix}
m_{1} & m_{2} & m_{3} & m_{4}\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
\end{pmatrix}

行列の2行目に1行目の隣同士の積を左詰めで設定する。

\begin{pmatrix}
m_{1} & m_{2} & m_{3} & m_{4}\\
m_{1}m_{2} & m_{3}m_{4} & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
\end{pmatrix}

行列の3行目に2行目の隣同士の積を左詰めで設定する。

\begin{pmatrix}
m_{1} & m_{2} & m_{3} & m_{4}\\
m_{1}m_{2} & m_{3}m_{4} & 0 & 0\\
m_{1}m_{2}m_{3}m_{4} & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
\end{pmatrix}

上記が出力となる。

参考文献の疑似コードをPythonで実装した。

def alg10_3(ms):
    k=0
    while 2**k < len(ms):
        k += 1
    r = 2**k
    ms = ms + ([0] * (r-len(ms)))
    M = [[0]*r for _ in range(k+1)]

    for i in range(r):
        M[0][i] = ms[i]

    for i in range(1, k+1):
        for j in range(0, 2**(k-i)):
            M[i][j] = M[i-1][2*j] * M[i-1][2*j+1]

    return M

出力は以下のようなる。

alg10_3([2, 3, 5, 7, 11, 13, 17, 19])