剰余群での除算
大きな素数Nと適当な数K, Rが与えられた時に、KxのNでのあまりがRになるようなxを求めたい。
Kx mod N = R Kのmod Pでの逆元を求めてRに掛けたという解釈もできる
単純に割り算をしてはいけない
例 2x mod 7=1の場合の答えは4
まずR=1について解く。
NとKにユークリッドの互除法を使う
ただし最大公約数を求めることが目的ではない。
Nが素数だから最大公約数が1であることは既知
1をNとKの線形結合で表現することが目的
aN + bK == 1 の形aNはmod Nで消えるのでbK \equiv 1 \pmod{N}
つまりbはmod NでのKの逆元
得られた式の両辺をR倍すれば求める除算結果が得られる
pythondef mod_inverse_ee(a, m):
"""
Solve ax mod m = 1 with extended euclidean.
x = a^-1.
"""
x, y, g = extended_euclidean(a, m)
assert g == 1
return x % m
def extended_euclidean(a, b, test=False):
"""
Extended Euclidean algorithm
Given a, b, solve:
ax + by = gcd(a, b)
Returns x, y, gcd(a, b)
Other form, for a prime b:
ax mod b = gcd(a, b) = 1
>>> extended_euclidean(3, 5, test=True)
3 * 2 + 5 * -1 = 1 True
>>> extended_euclidean(240, 46, test=True)
240 * -9 + 46 * 47 = 2 True
Derived from https://atcoder.jp/contests/acl1/submissions/16914912
"""
init_a = a
init_b = b
s, u, v, w = 1, 0, 0, 1
while b:
q, r = divmod(a, b)
a, b = b, r
s, u, v, w = v, w, s - q * v, u - q * w
if test:
print(f"{init_a} * {s} + {init_b} * {u} = {a}",
init_a * s + init_b * u == a)
else:
return s, u, a--- old version 2020/06/18
python"""
Given K, N, R, find x s.t. Kx mod N = R
"""
R = 1234567
# Solve Kx + Ny = 1
N = 9999991
K = 2236206
a = N
b = K
vec = [(1, 0), (0, 1)] # b = 0 N + 1 K
while True:
q = a // b
r = a % b
# print(q, r)
(aa, ab), (ba, bb) = vec
vec = [(ba, bb), (aa - q * ba, ab - q * bb)]
# print(vec)
if r == 1:
break
a, b = b, r
_, (ba, bb) = vec
print(f"{N} * {ba} + {K} * {bb} == 1")
# => 9999991 * 3109 + 2236206 * -13903 == 1
x = bb * R % N
print(f"{K} * {x} mod {N} = {R}")
# => 2236206 * 5799546 mod 9999991 = 1234567Related Pages
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]