ランダム素数とラビンカープ文字列検索

Aug 17 2020

SedgewickからRabin-Karbアルゴリズムを読んでいます。本は言う:

オーバーフローを避けながら、できるだけ大きな値をとるランダム素数Qを使用します

最初に読んだとき、ランダムの重要性に気づかなかったので、コードでalongが使用されているのを見て、最初に考えたのは次のとおりです
。a)エラトステネスのふるいを使用してalong
または
bに適合する大きな素数を見つけます。より大きい素数をプライミングし、intそれを定数として使用します。

しかし、その後の説明の残りの部分は次のように述べています。

衝突が発生する確率を以下にするよりもlong大きい値を使用します10^2010^-20

それより大きい値longは言うまでもなく、aは適合できないため、この部分は私を混乱さ10^20せました。それから私がプライムの計算をチェックしたとき、本は次のヒントだけを持っている練習に延期します:

ランダムなn桁の数は、1 / nに比例する確率で素数です。

どういう意味ですか?

つまり、基本的に私が得られないのは次のとおりです。a)ランダムプライム
を使用する意味は何ですか?事前に計算して定数として使用できないのはなぜですか?b)範囲外であるため、なぜ言及されているのですか?c)そのヒントはどのように役立ちますか?正確にはどういう意味ですか?
10^20long

回答

3 DavidEisenstat Aug 17 2020 at 14:09

繰り返しになりますが、Sedgewickはアルゴリズムを単純化しようとしましたが、詳細が少し間違っていました。まず、あなたが観察として、10 20は64ビットで表現することはできません。ただし、2 63 − 1に近い素数を取る場合でも、後続のモジュロが正しくなるように、オーバーフローせずに通常の方法で乗算するための少しの余地が必要になる可能性があります。答えは31ビットの素数を使用します。これにより、これは簡単になりますが、衝突確率は10-9の範囲でしか提供されません。

元のバージョンは、使用していますラビン指紋とランダム既約多項式𝔽オーバー2代数的整数論の観点から、整数上のランダムプライムのような多くの振る舞い[X]を、。多項式を32次または64次に選択すると、フィンガープリントは適切な長さのコンピューターワードに完全に適合し、多項式の加算と減算は両方ともビット単位のXORになり、オーバーフローは発生しません。

さて、Sedgewickはおそらく多項式環がどのように機能するかを説明したくなかったでしょう。結構です。私は実際にこのアプローチを実装する必要があった場合、私は最大の素数pの近くに選択したい安い指示によりMODに簡単でした(私はに部分的だ 2 31 2 - 27 + 1 EDIT実際に2; 31 - 1ここでは滑らかな素数が必要ないため、さらにうまく機能します)、[1、p-1]で乱数を選択して、で多項式を評価します(これがウィキペディアの説明です)。ある程度のランダム性が必要な理由は、そうしないと、気付かない敵が、多くのハッシュ衝突が保証される入力を選択する可能性があり、実行時間が大幅に低下するためです。

Sedgewickは、元の値をそれよりも少し厳密に追跡したいと考えていましたが、本質的には、xの固定値(多項式環を使用する元のバージョンでは文字通りx)で多項式を評価します。気づかない敵が衝突を設計できないように、彼はランダムな素数を必要とします。十分に大きな数をふるいにかけることは非常に非効率的であるため、彼は素数定理(彼のヒントの背後にある数学ですが、それは漸近的にしか成り立たず、理論的に大きな混乱を引き起こします)と素数判定(確率的である可能性があります;失敗した場合はアルゴリズムの正確さに影響せず、予想される実行時間に影響を与えないほどまれです)。

彼が衝突確率の正式な限界をどのように証明するかはわかりません。私の大まかな考えは、基本的に、対象のウィンドウに十分な素数があることを示し、中国剰余定理を使用して、一度に多くの素数の衝突が発生することは不可能であることを示し、衝突確率はによって制限されると結論付けます。悪い素数を選ぶ確率は低いです。しかし、素数定理は漸近的にしか成り立たないので、マシンワード範囲の素数の密度に関してはコンピューター実験に頼らなければなりません。良くない。