Approximate GCD Problem

https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/

形式的にはという形式の要素からなる集合を与えられたときにの値を特定するという問題

現状はlattice basedなアプローチが主流

https://eprint.iacr.org/2016/215.pdf

https://eprint.iacr.org/2009/616.pdf

p = random_prime(1 << 2048)

xs = []
qs = []
for i in range(5):
    q = random_prime(1 << 1024)
    qs.append(q)
    r = randint(0, 1 << 512)
    xs.append(p*q + r)

print("LLL...")
K = 1<<512
M = matrix(ZZ, [
    [K,  xs[1],  xs[2],  xs[3],  xs[4]],
    [0, -xs[0],      0,      0,      0],
    [0,      0, -xs[0],      0,      0],
    [0,      0,      0, -xs[0],      0],
    [0,      0,      0,      0, -xs[0]],
])
L = M.LLL()

print(qs)
print(L[0] * M^(-1))