Recherche de nombres premiers aléatoires et de sous-chaînes Rabin Karp

Question

Je lis l'algorithme Rabin-Karb de Sedgewick. Le livre dit:

On utilise un Q premier aléatoire prenant une valeur aussi grande que possible tout en évitant les débordements

À la première lecture, je n'ai pas remarqué la signification du hasard et quand j'ai vu que dans le code a longest utilisé, mes premières pensées ont été:
a) Utilisez le tamis d'Eratosthene pour trouver un grand premier qui correspond à a long
ou
b) recherchez dans une liste de prime tout nombre premier suffisamment grand qui est supérieur à intet l'utilise comme constante.

Mais alors le reste de l'explication dit:

Nous utiliserons une longvaleur supérieure à 10^20la probabilité qu'une collision se produise inférieure à10^-20

Cette partie m'a rendu confus car un longne peut pas s'adapter et 10^20encore moins une valeur supérieure à cela. Ensuite, lorsque j'ai vérifié le calcul de l'amorce, le livre se reporte à un exercice qui a juste le conseil suivant:

Un nombre aléatoire à n chiffres est premier avec une probabilité proportionnelle à 1 / n

Qu'est-ce que ça veut dire?

Donc, fondamentalement, ce que je n'obtiens pas, c'est:
a) quel est le sens de l'utilisation d'un nombre premier aléatoire ? Pourquoi ne pouvons-nous pas simplement le pré-calculer et l'utiliser comme constante?
b) pourquoi le 10^20mentionné est-il hors de portée long?
c) En quoi cet indice est-il utile? Qu'est-ce que cela signifie exactement?

Answer 1

Une fois de plus , Sedgewick a essayé de simplifier un algorithme et s'est légèrement trompé dans les détails. Premièrement, comme vous le voyez, 10 ²⁰ ne peut pas être représenté en 64 bits. Même en prenant un prime proche de 2 ⁶³ - 1, cependant, vous voudrez probablement un peu de place pour multiplier normalement sans déborder afin que le module suivant soit correct. La réponse utilise un premier 31 bits, ce qui rend cela facile mais n'offre que des probabilités de collision dans la plage de ^10-9 .

La version originale utilise les empreintes de Rabin et un polynôme irréductible aléatoire sur 𝔽 ₂ [x], qui, du point de vue de la théorie algébrique des nombres, se comporte beaucoup comme un premier aléatoire sur les entiers. Si nous choisissons que le polynôme soit le degré 32 ou 64, alors les empreintes digitales s'intègrent parfaitement dans un mot d'ordinateur de la longueur appropriée, et l'addition et la soustraction polynomiales fonctionnent toutes deux en XOR au niveau du bit, donc il n'y a pas de débordement.

Maintenant, Sedgewick ne voulait probablement pas expliquer le fonctionnement des anneaux polynomiaux. Bien. Si je devais mettre en œuvre cette approche dans la pratique, je choisirais un proche prime p au maximum qui était facile à mod par des instructions bon marché (je suis partie à 2 ³¹ - 2 ²⁷ + 1 ; EDIT fait 2 ³¹ - 1 fonctionne encore mieux puisque nous n'avons pas besoin d'un nombre premier lisse ici), puis choisissez un nombre aléatoire dans [1, p − 1] pour évaluer les polynômes en (c'est ainsi que Wikipedia l'explique). La raison pour laquelle nous avons besoin d'un certain caractère aléatoire est qu'autrement, l'adversaire inconscient pourrait choisir une entrée qui aurait la garantie d'avoir beaucoup de collisions de hachage, ce qui dégraderait gravement le temps d'exécution.

Sedgewick voulait cependant suivre l'original d'un peu plus près que cela, qui évalue essentiellement les polynômes à une valeur fixe de x (littéralement x dans la version originale qui utilise des anneaux polynomiaux). Il a besoin d'un prime aléatoire pour que l'adversaire inconscient ne puisse pas créer de collisions. Tamiser des nombres assez grands est assez inefficace, il se tourne donc vers le théorème des nombres premiers (qui est le calcul derrière son indice, mais il ne tient que de manière asymptotique, ce qui fait un gros gâchis théoriquement) et un test de primalité rapide (qui peut être probabiliste; le les cas où il échoue n'influenceront pas l'exactitude de l'algorithme, et ils sont suffisamment rares pour qu'ils n'affectent pas le temps d'exécution prévu).

Je ne sais pas comment il prouve une limite formelle sur la probabilité de collision. Mon idée approximative est fondamentalement, montrer qu'il y a suffisamment de nombres premiers dans la fenêtre d'intérêt, utiliser le théorème chinois des restes pour montrer qu'il est impossible qu'il y ait une collision pour trop de nombres premiers à la fois, conclure que la probabilité de collision est limitée par le probabilité de choisir un mauvais premier, ce qui est faible. Mais le théorème des nombres premiers ne tient qu'asymptotiquement, nous devons donc nous fier à des expériences informatiques concernant la densité des nombres premiers dans les plages de mots machine. Pas génial.