Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

拡張ユークリッドの互除法

pythonの再帰で実装したもの

import sys

def egcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

rustではタプルが使えるので、同じアルゴリズムでいけます。

Algorithm Implementation/Mathematics/Extended Euclidean algorithm - Wikibooks, open books for an open world

拡張ユークリッドの互除法を使って、
 l_1, l_2を異なる素数とし、
 x = r_1 \mod l_1
 x = r_2 \mod l_2
の式と、
 l_1 p + l_2 q = 1で求めたpを使って、
 x \mod l_1 l_2 = r_1 + l_1 p (r_2 - r_1)
が求められます。

プライバシーポリシー

お問い合わせ

スポンサーリンク