Thue's Lemma - crypto-writeup-public

$n$ と $a \in \mathbb{Z}_n$ に対して、次を満たす整数 $|x|, |y| \le \sqrt{n}$ の組が存在する

$ax \equiv y \mod n$

これはLLLを使って効率的に求められる

def thues_lemma(a, mod):
    '''
            Find small elements x, y such that a * x = y
            and |x| < sqrt(mod) and |y| < sqrt(mod).
    '''
    R = Zmod(mod)
    A = matrix([
        [1,   a],
        [0, mod]
    ])
    A = A.LLL()
    return A[0][0], A[0][1]
 
# test
p = random_prime(2^512)
q = random_prime(2^512)
n = p * q
a = randint(0, 2**1024)
u, v = thues_lemma(a, n)
assert(a * u % n == v % n)