[BOJ] 13318번: 위험한 해싱

https://www.acmicpc.net/problem/13318

 

LLL 알고리즘을 통해 충돌쌍을 알아낼 수 있습니다. 여기를 참고하세요.

 

아래 코드는 충돌쌍을 구해주는 sage 코드입니다.

p = [29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
m = 10**9+7

N = 80

def sparse_poly():
    L_rows = []
    B = 10000000

    for i in xrange(N):
        row = [1 if j==i else 0 for j in xrange(N)]
        for j in range(10):
            row.append(B*Integer(pow(p[j],i,m)))
        L_rows.append(row)

    L_matrix = Matrix(L_rows)
    L_redux = L_matrix.LLL()
    sparse = L_redux[0]
    print sparse[:-1]
    poly, vals = sparse[:N], sparse[N:]

    assert all(abs(x) <=25 for x in poly)
    assert all(x == 0 for x in vals)

    return poly

def build_strings(poly):
    a = [0 for _ in xrange(N)]
    b = [0 for _ in xrange(N)]

    # a[i] - b[(N-1)-i] = poly[i]

    for i in xrange(N):
        if poly[i] >= 0:
            a[i] = poly[i]
            b[i] = 0
        else:
            a[i] = 0
            b[i] = -poly[i]

    a_str = ''.join(chr(ord('a')+v) for v in a)
    b_str = ''.join(chr(ord('a')+v) for v in b)
    return a_str, b_str

def solve():
    poly = sparse_poly()
    s1, s2 = build_strings(poly)
    print s1
    print s2

solve()