![定式化
● s, tの長さは同じとして、その長さをnと固定する
● sのハッシュとtのハッシュが一致するという条件は次のように
書ける
● 係数揃えたいからs,tを前後反転し、c[i]=s[i]-t[i]とおくと
ただし-25 <= c[i] <= 25
● つまり最大次数n-1のZ/mZ上の多項式であって、rを根に持ち、
かつ係数が小さいものが求まればs,tを構成できる](https://image.slidesharecdn.com/rh2-190616073759/85/Rolling-Hash-8-320.jpg)
![???
● LLL法を使ってSVPの近似解が出たら、その基底のうち最もノル
ムが小さいベクトルを多項式にする
● この多項式の係数がc[i]の条件を満たしているかを確認、okな
らそれらからs, tを復元して出力、だめなら文字列の長さを増や
して続行
● 先ほどの例はこの方法で生成した
● ランダムに試してみると文字列の長さが10~20程度で衝突が起
こせることがわかった](https://image.slidesharecdn.com/rh2-190616073759/85/Rolling-Hash-13-320.jpg)
![ペアでもダメです
● アルファベットとして2文字許さないことにして、衝突する文
字列を探す(つまり-1<=c[i]<=1)
– m=10^9ぐらいなら一瞬で衝突が見つかる(n=20ぐらい)
– m=10^18ぐらいだと数分かけても見つかりませんでした
● m1,r1について衝突する文字列をs1,t1とする
● rr2=pow(r2, s1.size()) mod m として、m2,rr2について衝突する
文字列をs2, t2とする
● s2,t2中の各aをs1で、bをt1で置き換えた文字列のペアを考える
● これらはm1,r1についてもm2,r2についても衝突する](https://image.slidesharecdn.com/rh2-190616073759/85/Rolling-Hash-15-320.jpg)
![おまけ
● s[i]=popcnt(i), t[i] =~ popcnt(i)として長さを2^nまでとる
● 多項式のときの議論と同様にハッシュの差をとると各係数は
iの立っているビット数が奇数なら1、偶数なら-1となる
●
x^0 – x^1 – x^2 + x^3 …. ±x^((2^n)-1)
=(x^1 – 1) ( -x^0 + x^2 + x^4 – x^6....)
=(x^1 -1) (x^2 – 1) (x^4 – 1)... ..(x^(2^(n-1) )-1)
● xに奇数を入れると、i+1番目の項はi番目の項*偶数に分解でき
る
● 帰納法により多項式全体は2^(n*(n-1)/2)で割り切れる](https://image.slidesharecdn.com/rh2-190616073759/85/Rolling-Hash-24-320.jpg)
More Related Content
What's hot (20)
Rolling Hashを殺す話
- 1. そのロリハ、大丈夫？
- 3. RollingHash ● 文字列を整数値(ハッシュ)に変換する方法 – 文字列の比較はO(n)だが、文字列を整数に対応づけてその整 数の比較をすればO(1)で文字列の一致判定ができる！ ● 文字列 について、 ● sの全ての接頭辞についてこのハッシュを求めておけば、s中の どの連続する部分文字列についてのハッシュもO(1)で求まる – ● (めんどいのでmodをとる操作は省略)
- 4. ところで ● 異なる文字列のハッシュ値が衝突したらやばい – 誤った一致判定を行うことになる ● ではどれぐらいの确率で衝突するのか
- 5. 誕生日問題 ● 何人の人を集めれば、誕生日が同じ二人がいる確率が50%を超 えるか？ ● 実はこの答えは23人。70人いれば99.9%を超える。 – 意外と少ないって思いません？ ● 一般化するぞ – m個の値を一様独立にとる変数があったとして、この変数を √m個ぐらい集めれば50%以上の確率で値が一致するペアが 現れる。 ● つまりm=10^9+7とかにすると10^5個の文字列が飛んで きただけでまあまあ衝突する
- 6. 対策 ● じゃあm=10^18, r=10^9+7とかにすればだいじょうぶそうだ ね！ ● そんなことはない！！！(今日の本題) – m, rを固定してとるとロリハは死ぬ
- 7. 雑ロリハを殺します ● m, rを入力として、ハッシュ値が一致するような英小文字から なる文字列の組(s,t)を求めたい ● 例1: m=10^9+7, r=10007 – s = dkaaa, t = aayagcで衝突 ● 例2: m=12318230912731, r=31434130048173 – s = amcaraha, t = paaqavamで衝突
- 8. 定式化 ● s, tの長さは同じとして、その長さをnと固定する ● sのハッシュとtのハッシュが一致するという条件は次のように 書ける ● 係数揃えたいからs,tを前後反転し、c[i]=s[i]-t[i]とおくと ただし-25 <= c[i] <= 25 ● つまり最大次数n-1のZ/mZ上の多項式であって、rを根に持ち、 かつ係数が小さいものが求まればs,tを構成できる
- 9. 定式化 ● 1つ目の条件である、rを根に持つ多項式は の線形 和を作ればできる ● 突然ですが多項式をベクトルで表します 係数をもつやつ ● (0,..,0,-r, 1,0,..,0)というn次元ベクトルをn-1本つくります – これは に対応する ● (p,0,...,0)というn次元ベクトルを1本作ります – これは mKに対応する ● これらのベクトルをb1,b2, … , bn と名付けます
- 10. Lattice ● とする ● ベクトル空間っぽいが係数が整数なのが特徴 – これはlatticeと呼ばれる 日本語では格子 ● bの作り方から、Lの任意の元はrを根にもつn-1次元多項式と一 対一に対応する。 ● あとは係数が小さいという第2の条件を満たす元を見つけたい – Note : ここでの係数というのはa_iのことではなく、多項式 の係数つまりベクトルの各要素のこと
- 11. Shortest Vector Problem (SVP) ● latticeが与えられたとき、そのlatticeに属するノルム最小の元を 求める問題 – ノルムはふつうL2ノルム ● 次元についてNP困難(???) ● よい近似を与えてくれる多項式時間アルゴリズムがある – LLL algorithm
- 12. LLL algorithm ● Lenstra–Lenstra–Lovász algorithm (3人の名前) – 名前被ることもあるんだなあ ● b = {b_1, b_2, … , b_d}、b_iの次元をn としたとき、bが張る latticeのいい感じ(ノルムが小さい)の基底を求める ● b_iのノルムの最大値をAとすると、LLL algorithmの時間計算量 は (?) – でも動かしてみたところかなり速い d=500とかでも数秒で 終わる ● アルゴリズムの詳細は省きます 時間がなかったのであんまり 読んでない
- 13. ??? ● LLL法を使ってSVPの近似解が出たら、その基底のうち最もノル ムが小さいベクトルを多項式にする ● この多項式の係数がc[i]の条件を満たしているかを確認、okな らそれらからs, tを復元して出力、だめなら文字列の長さを増や して続行 ● 先ほどの例はこの方法で生成した ● ランダムに試してみると文字列の長さが10~20程度で衝突が起 こせることがわかった
- 15. ペアでもダメです ● アルファベットとして2文字許さないことにして、衝突する文 字列を探す(つまり-1<=c[i]<=1) – m=10^9ぐらいなら一瞬で衝突が見つかる(n=20ぐらい) – m=10^18ぐらいだと数分かけても見つかりませんでした ● m1,r1について衝突する文字列をs1,t1とする ● rr2=pow(r2, s1.size()) mod m として、m2,rr2について衝突する 文字列をs2, t2とする ● s2,t2中の各aをs1で、bをt1で置き換えた文字列のペアを考える ● これらはm1,r1についてもm2,r2についても衝突する
- 16. 具体例 ● Sさんのライブラリ – m1=999999937, r1=17 ● aaaaababaaaaaabaaaaabbab ● baaaaaaabaabbaaaaabaaaba – m2=1000000007, r2=19 (rr2=749490718) ● aabaabaabaaaaaaaabaaabbb ● aaabaaaaaabaaaaaaaabaaaa ● 前ページのルールで置換すると??
- 19. 具体例 ● ??の二つの文字列はr1,m1についても衝突するし、r2,m2につ いても衝突する ● 手元でロリハがすぐ動かせる方は試してみては？ ● ただこの方法は文字列が指数的に長くなる – 1回の操作で10~20倍ぐらいになる – 10個ぐらいmとr用意されると確実にむり
- 20. 結論 ● そもそも何がいけなかったのかというと、実行前にm,bを固定 したこと ● mを十分大きな素数にとって、実行時にrを2からm-2までの乱 数で取りましょう – 十分大きな、というのは10^9ぐらいでは足りません 誕生 日攻撃に耐えるぐらいの大きさで ● 片方は定数でも問題ない(mは定数でとりたいよね)
- 21. まとめ ● ぼくがころせるロリハ – m=10^9ぐらい, r=定数 ● 論外 – m=10^18ぐらい, r=定数 – m=10^9ぐらい, r=定数 を5組ぐらい ● これが今回のスライドの内容です 実は死ぬ – m=2^k, r=乱数 ● (2冪modは絶対にやめましょう(おまけで話す)
- 22. まとめ ● ぼくがころせないロリハ – m=10^18 ぐらい,r=定数 の組を10個ぐらい ● 乱数を使いましょう – プログラム実行前にrがわからなければ解析は難しいです
- 23. おまけ ● ロリハのmodを2^64にして64bit符号なし整数で演算すれば mod操作が要らないじゃん！ ● だめです 死にます ● 谤を乱数でとっても死にます
- 24. おまけ ● s[i]=popcnt(i), t[i] =~ popcnt(i)として長さを2^nまでとる ● 多項式のときの議論と同様にハッシュの差をとると各係数は iの立っているビット数が奇数なら1、偶数なら-1となる ● x^0 – x^1 – x^2 + x^3 …. ±x^((2^n)-1) =(x^1 – 1) ( -x^0 + x^2 + x^4 – x^6....) =(x^1 -1) (x^2 – 1) (x^4 – 1)... ..(x^(2^(n-1) )-1) ● xに奇数を入れると、i+1番目の項はi番目の項*偶数に分解でき る ● 帰納法により多項式全体は2^(n*(n-1)/2)で割り切れる
- 25. おまけ ● したがってn=12 つまり文字列の長さを4096とすると、任意の 奇数rについてsとtのハッシュが一致する ● やばいですね ● 2冪modはやめましょう
- 26. 参考 ● https://yukicoder.me/problems/no/3014/editorial – ほぼこの内容 ● http://hos.ac/blog/#blog0002 – hosさんのブログ ● https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra %E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm – wikipedia LLL algorithm ● https://codeforces.com/blog/entry/4898 – 2冪modはいかんぞの話