概要
(Gathen and Gerhard 2013) を参考にして、中国の剰余定理のアルゴリズムを実装する。
Alg10.18
このアルゴリムズは入力m1,…,mr-1で、法miでのm=m1…mi-1,mi+1,…,mr-1 の逆元を算出するものである。
拡張ユークリッド互除法法を使用するため拡張ユークリッド互除法を参考にした。
実装
実装は以下のようになる。
def alg10_18(ms): m = functools.reduce(lambda a, b: a*b, ms, 1) ms2 = [mi**2 for mi in ms] # 1. call alg10_16 (alg10_16はalg10_3とalg10_14を併せたもの) M = alg10_3(ms2) m_rem_mi2 = alg10_14x(0, len(ms2), m, M, -2, 0) # 2. m/mi rem mi m_rem_mi = [m_rem2//mi for mi, m_rem2 in zip(ms, m_rem_mi2)] # 3. extended euclidean algo si = [] for mi, mi_rem in zip(ms, m_rem_mi): a, b = xgcd(mi, mi_rem) if 0 < b: si.append(b) else: si.append(b+mi) return si
結果
期待する結果は以下である。
ms = [2, 3, 5, 7, 11, 13, 17, 19] m = functools.reduce(lambda a, b: a*b, ms, 1) si = [] for mi in ms: for i in range(1, mi): if 1 == (i * m//mi) % mi: si.append(i) break; si
| 1 | 1 | 2 | 6 | 7 | 5 | 16 | 18 |
実装した結果は以下になり、一致している。
ms = [2, 3, 5, 7, 11, 13, 17, 19] ms, r, k = pack_ms(ms) alg10_18(ms)
| 1 | 1 | 2 | 6 | 7 | 5 | 16 | 18 |