フィンガープリントを証明します

Question

$ a neq b $は、間隔$ [1、2^n]から2つの整数になります。$ $ p $は$ 1 le p le n^c。 {pr} _ {p in mathsf {primes}} {a equiv b pmod {p} } le c ln（n）/（n^{c-1}）。$$

ヒント：プライムナンバー定理の結果として、正確に$ n/ ln（n） pm o（n/ ln（n））$ $ {1、 ldots、n } $からの多くの数字はプライムです。

結論：$ n $ビットを$ o（ log（n））$ビットに圧縮し、非常に小さな偽陽性レートを取得できます。

私の質問は、$$ text {pr} _ {p in mathsf {primes}} {a equiv {p} } le c ln（n）/（n（n） {a equiv bod {p} } ln（n）をどのように証明できるかです。 ^{c-1}）$$？

Answer 1

$ 1 $ $と$ n^c $の間に均一に選択されたランダムプライムが$ a equiv b mod {p} $を満たす確率$ p $は、この範囲のプライムの数であり、$ a equiv b mod { p} $は、この範囲の素数の総数で割っています。 $ c $の場合は$ [c] = 1 $を書きます。 p = dfrac { sum limits_ {p le n^c} [p text {prime}] [p mid（ab）]} { pi（n^c）} $$

$ | ab |以来 le 2^n $、$ ab $を分割する$ n $の明確なプライムがせいぜいあります。主要な定理は、分母の上限を直接与えます。したがって、$$ p le dfrac {n^c/ ln（n^c） + o（n^c/ ln（n^c））} = dfrac {c ln（n） } {n^{c-1}}（1+o（1））$$

プライムナンバー定理の漸近バージョンから正確に拘束されることはありません。私が間違っていない場合、正確なバウンドは$ pi（x） gt dfrac {x} { ln（x）} $ $ x ge 11 $です。このバウンドを使用して、$ n^c ge 11 $の場合、$$ p le dfrac {c ln（n）} {n^{c-1}} $$であることがわかります。

アプリケーション：いくつかのランダムプライム番号$ P_I $に対して$ a mod p $を保存することにより、$ a le 2^n $（正確に表す$ n $ bitsを正確に表す）を圧縮できます。 $ a $の値とは無関係に選択された$ k $プライムを使用する場合、表現には$ k 、 lceil c 、 log_2（n） rceil = o（k log（n））$ bitsが必要です。選択されたプライムごとにValues Moduloを保存します。各プライムでの衝突の確率は、最大で$ c ln（n） / n^{c-1} = o（ ln（n） / n^{c-1}）$です。 $ k $で精度がどのように増加するかを評価するには、さらなる分析が必要になります。