Beweisen Sie Fingerabdruck

Question

Sei $ a neq b $ zwei ganze Zahlen aus dem Intervall $ [1, 2^n]. Oder

Hinweis: Als Folge des Primzahl -Theorems genau $ n/ ln (n) pm o (n/ ln (n)) $ viele Zahlen von $ {1, ldots, n } $ sind Primzahl .

Schlussfolgerung: Wir können $ n $ bit auf $ o ( log (n)) $ bit komprimieren und einen ziemlich kleinen falsch positiven Preis erhalten.

Meine Frage ist, wie kann ich diesen $$ text {pr} _ {p in mathsf {primes}} {a äquiv b pmod {p} le c ln (n)/(n) proovieren. ^{c-1}) $$?

Answer 1

Die Wahrscheinlichkeit $ p $, dass eine einheitlich ausgewählte zufällige Prime zwischen 1 $ $ und $ n^c $ erfüllt $ a äquiv b mod {p} $ ist die Anzahl der Primzahlen in diesem Bereich, die $ a äquiv b mod {erfüllen P} $ geteilt durch die Gesamtzahl der Primzahlen in diesem Bereich. Schreiben $ [c] = 1 $ Wenn $ c $ wahr ist und $ [c] = 0 $ Wenn $ c $ falsch ist und $ pi (x) $ für die Anzahl der Primzahlen von weniger als $ x $: $$ P = dfrac { sum limits_ {p le n^c} [p text {prime}] [p mid (ab)]} { pi (n^c)} $$

Seit $ | ab | le 2^n $, es gibt höchstens $ n $ unterschiedliche Primzahlen, die $ ab $ teilen. Der Primzahl -Theorem enthält direkt eine Obergrenze für den Nenner. Also: $$ 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)) $$

Sie werden keine exakte Bound von einer asymptotischen Version des Primzahl -Theorems erhalten. Eine genaue gebundene, wenn ich mich nicht irre, ist $ pi (x) gt dfrac {x} { ln (x)} $ für $ x ge 11 $. Mit dieser Grenze sehen wir, dass, wenn $ n^c ge 11 $ dann $$ p le dfrac {c ln (n)} {n^{c-1}} $$

Anwendung: Wir können $ a le 2^n $ (was $ n $ bits genau darstellen) ungefähr durch das Speichern $ a mod p $ für mehrere zufällige Prime -Zahlen $ p_i $ komprimieren. Wenn wir $ k $ primes verwenden, die unabhängig vom Wert von $ a $ ausgewählt werden Speichern Sie die Werte modulo jede ausgewählte Prime. Die Wahrscheinlichkeit einer Kollision an jeder Prime ist höchstens $ c ln (n) / n^{c-1} = o ( ln (n) / n^{c-1}) $. Um zu bewerten, wie die Präzision mit K $ K $ steigt, würde weitere Analysen erforderlich sein.