Primos aleatorios y búsqueda de subcadenas de Rabin Karp

Question

Estoy leyendo el algoritmo Rabin-Karb de Sedgewick. El libro dice:

Usamos un Q primo aleatorio tomando un valor lo más grande posible evitando el desbordamiento

En la primera lectura no me di cuenta de la importancia del azar y cuando vi que en el código de una longse utiliza mis primeros pensamientos fueron:
a) el tamiz de Uso Eratóstenes para encontrar un gran primer que se ajusta a una long
o
b) levantar la vista de una lista de ceba cualquier primo lo suficientemente grande que sea mayor que inty lo usa como una constante.

Pero luego el resto de la explicación dice:

Usaremos un longvalor mayor que 10^20hacer que la probabilidad de que ocurra una colisión sea menor que10^-20

Esta parte me confundió ya longque no cabe ni 10^20mucho menos un valor mayor que ese. Luego, cuando verifiqué el cálculo del primo, el libro se remite a un ejercicio que tiene solo la siguiente pista:

Un número aleatorio de n dígitos es primo con probabilidad proporcional a 1 / n

Qué significa eso?

Entonces, básicamente, lo que no entiendo es:
a) ¿cuál es el significado de usar un primo aleatorio ? ¿Por qué no podemos precalcularlo y usarlo como una constante?
b) ¿Por qué lo 10^20mencionado ya que está fuera de rango long?
c) ¿Cómo es útil esa pista? ¿Qué significa exactamente?

Answer 1

Una vez más , Sedgewick ha intentado simplificar un algoritmo y se ha equivocado un poco en los detalles. Primero, como observa, 10 ²⁰ no se puede representar en 64 bits. Sin embargo, incluso tomando un primo cercano a 2 ⁶³ - 1, probablemente querrá un poco de espacio para multiplicar de la forma normal sin desbordarse, de modo que el módulo posterior sea correcto. La respuesta usa un número primo de 31 bits, lo que facilita esto, pero solo ofrece probabilidades de colisión en el rango de 10 ⁻⁹ .

La versión original usa huellas dactilares de Rabin y un polinomio irreducible aleatorio sobre 𝔽 ₂ [x], que desde la perspectiva de la teoría algebraica de números se comporta mucho como un primo aleatorio sobre los enteros. Si elegimos que el polinomio sea de grado 32 o 64, entonces las huellas dactilares encajan perfectamente en una palabra de computadora de la longitud apropiada, y la suma y resta de polinomios funcionan en XOR bit a bit, por lo que no hay desbordamiento.

Es de suponer que Sedgewick no quería explicar cómo funcionan los anillos polinomiales. Multa. Si tuviera que implementar este enfoque en la práctica, elegiría un primer p cercano al máximo que fuera fácil de modificar con instrucciones baratas (soy parcial a 2 ³¹ - 2 ²⁷ + 1 ; EDITAR en realidad 2 ³¹ - 1 funciona incluso mejor ya que no necesitamos un número primo suave aquí) y luego elegir un número aleatorio en [1, p − 1] para evaluar los polinomios en (así es como Wikipedia lo explica). La razón por la que necesitamos algo de aleatoriedad es que, de lo contrario, el adversario ajeno podría elegir una entrada que estaría garantizada para tener muchas colisiones de hash, lo que degradaría gravemente el tiempo de ejecución.

Sedgewick quería seguir el original un poco más de cerca, sin embargo, que en esencia evalúa los polinomios en un valor fijo de x (literalmente x en la versión original que usa anillos polinomiales). Necesita un cebado aleatorio para que el adversario ajeno no pueda diseñar colisiones. Tamizar números lo suficientemente grandes es bastante ineficiente, por lo que recurre al Teorema de los números primos (que es la matemática detrás de su sugerencia, pero solo se mantiene asintóticamente, lo que teóricamente crea un gran lío) y una prueba de primalidad rápida (que puede ser probabilística; los casos en los que falla no influirán en la corrección del algoritmo, y son lo suficientemente raros como para no afectar el tiempo de ejecución esperado).

No estoy seguro de cómo demuestra un límite formal en la probabilidad de colisión. Mi idea aproximada es básicamente, mostrar que hay suficientes números primos en la ventana de interés, usar el teorema del resto chino para demostrar que es imposible que haya una colisión para demasiados números primos a la vez, concluir que la probabilidad de colisión está limitada por el probabilidad de elegir una prima mala, que es baja. Pero el Teorema de los números primos es válido solo de forma asintótica, por lo que debemos confiar en experimentos informáticos con respecto a la densidad de los números primos en los rangos de palabras de máquina. No es bueno.