剰余群での除算
大きな素数Nと適当な数K, Rが与えられた時に、KxのNでのあまりがRになるようなxを求めたい。
Kx mod N = R
これは剰余群の中でKを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倍すれば求める除算結果が得られる
code:python
def 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
code: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 = 1234567