Goldman Sachs CodeSprint: Transaction Certificates
- keywords
- rolling hash | birthday attack
解法
ハッシュ値が重複するまでひたすら生成し続けるだけで高速に発見できることが知られている。これは誕生日攻撃と呼ばれている。nが小さい場合は重複値が存在しない可能性があるので、100以上になるまで大きくしておく。
#include <iostream> #include <algorithm> #include <map> #include <vector> using namespace std; int main() { int n, k, p; unsigned long long m; cin >> n >> k >> p >> m; int u = 1; while (n * u < 100) { u++; } n *= u; auto gen = [&](int seed) { unsigned long long x = seed; vector<int> val; for (int i = 0; i < n; i++) { x ^= x << 13; x ^= x >> 7; x ^= x << 17; val.push_back(x % k + 1); } return val; }; auto calc_hash = [&](vector<int> a) { long long hash = 0; for (long long x : a) { hash = (hash * p + x) & (m - 1); } return hash; }; map<unsigned, int> mp; for (int i = 1;; i++) { long long hash = calc_hash(gen(i)); if (mp.count(hash)) { for (long long x : gen(i)) { cout << x << ' '; } cout << endl; for (long long x : gen(mp[hash])) { cout << x << ' '; } return 0; } else { mp[hash] = i; } } }
二冪なので他にも攻略法があって、それはhos氏のブログが参考になる。
文字列 \(110000\) と文字列 \(000011\) の rolling hash はそれぞれ
\begin{equation}
1x^5+1x^4+0x^3+0x^2+0x^1+0 \\
0x^5+0x^4+0x^3+0x^2+1x^1+1
\end{equation}
であり、その差は \(x^5+x^4-x-1\) である。この多項式は \(x\) が奇数のとき常に \(32\) の倍数になる。つまり法を \(32\)、基数を奇数としたとき必ず衝突する。法が二冪であればこのような多項式が容易に構成できる。
\(v(n)\) を \(2\) が \(n\) を割り切る回数とし、多項式 \(f\) に対して
\begin{equation}
V(f)=\min_{n \in 2\mathbb{Z}+1}v(f(n))
\end{equation}
とする。\(V(f) \ge 32\) となる多項式 \(f\) を見つければ良い。\(V(x^{2k} - 1) = V( (x^k - 1) (x^k+1) ) \ge 1+V(x^k - 1)\) なので、
\begin{equation}
V( (x-1)(x^2-1)(x^4-1)\cdots(x^{128}-1) ) \ge 32
\end{equation}
である。これは展開時の係数がすべて \(\pm 1\) であり、さらにその係数は組合せ的に求まる。
n, k, p, m = map(int, input().split()) # (x-1)(x^2-1)(x^4-1)(x^8-1)(x^16-1)(x^32-1)(x^64-1)(x^128-1) # 1 2 3 4 5 6 7 8 >32 n = (256+n-1)//n*n ans = [0]*(n-256) + [(-1)**bin(i).count('1') for i in range(256)] mp1 = {0: 1, 1: 2, -1: 1} mp2 = {0: 1, 1: 1, -1: 2} print(*[mp1[v] for v in ans]) print(*[mp2[v] for v in ans])
