证明指纹

Question

令$ a neq b $为间隔$ [1，2^n]的两个整数。$ let $ p $是一个随机素数，$ 1 le p le n^c。$ $证明$$ text {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 } $的许多数字是PRIME 。

结论：我们可以将$ n $ lits压缩到$ o（ log（n））$位，并获得很小的假阳性率。

我的问题是如何证明$$ text {pr} _ {p in mathsf {primes}}} {a equiv b equiv b pmod {p} } le c ln（n）/（n） ^{c-1}）$$？

Answer 1

在$ 1 $和$ n^c $之间均匀选择的随机素数满足$ a equiv b mod {p} $的概率$ p $是该范围内满足$ a equiv b mod { p} $除以此范围内的总数。写入$ [c] = 1 $如果$ c $为真，$ [c] = 0 $如果$ c $为false，而$ pi（x）$的数量小于$ x $：$ $ p = dfrac { sum limits_ {p le n^c} [p text {prime}] [p mid（ab）]} { pi（n^c）} $

由于$ | ab | le 2^n $，最多有$ n $不同的素数划分$ ab $。素数定理直接为分母提供了上限。因此：$$ p le dfrac {n} {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）} $ for $ 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 $ primes，则表示表示需要$ k ， lceil c ， log_2（n） rceil = o（k log（n））$ bits to存储每个选择的素数的值。每个元素上碰撞的可能性最多为$ c ln（n） / n^{c-1} = o（ ln（n） / n^{c-1}）$。为了评估$ k $的精度如何提高将需要进一步分析。