剰余群での除算

大きな素数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で消えるので $b K \equiv 1 (mod N)$
  - つまりbはmod NでのKの逆元
- 拡張ユークリッド互除法

得られた式の両辺をR倍すれば求める除算結果が得られる

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 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

🪴 Quartz 4.0

剰余群での除算

Graph View

Backlinks