Elegir números primos uniformemente al azar

Question

Estoy interesado en la eficacia de los métodos de generación de números primos en un intervalo dado [a, b] (o con un determinado número de bits/dígitos, etc.). Por "eficiente" me refiero a minimizar el tiempo, el azar, y tal vez de otros recursos en el caso promedio. Para la concreción, digamos que el primer es para ser seleccionado en el rango de $(2^n,\,2^{n+1})$.

El ingenuo es el método para generar números en el intervalo al azar y la prueba de primalidad. Esto se lleva a $n$ bits por iteración con un promedio de $(n+1)\log 2-1\approx n\log 2$ iteraciones. En total, esta se lleva a $n^2\log 2$ bits aleatorios y $n\log 2$ pruebas de primalidad.

Una mejora evidente es el uso de sólo los números impares (el caso especial de 2 puede ser manejado por separado con O(1) sobrecarga), reduciendo el número de bits aleatorios a $(n-1)\frac{(n+1)\log 2-1}{2}\approx \frac{\log 2}{2}n^2$. Este truco puede ser extendido: generar un número en [a/30/b / 30], multiplicar por 30, y elegir el residuo mod 30 con 3 bits. (Los extremos pueden, una vez más, debe ser manejado con sólo O(1) trabajo extra.) Esto reduce el número de bits por iteración por sólo una pequeña cantidad (1.9 en este caso), pero reduce el número de iteraciones por un factor de $30/\varphi(30)=3.75$ sobre el método ingenuo (87% de mejora con respecto a la generación acaba de probabilidades).

La versión extrema de este algoritmo sería para calcular $\pi(b)$ $\pi(a-1)$ y elija un índice al azar; esto lleva a la teoría de la información número mínimo de bits, acerca de $n-\lg n+O(1)$, en el costo de una verdad atroz tiempo de ejecución, algo peor que la $2^{n/2}$ con los actuales algoritmos.

Existen algoritmos conocidos con un mejor tiempo/el azar, la desventaja de esta familia de algoritmos, pero que todavía genera los números primos de manera uniforme? (Algoritmos como nextprime(random(...)) que no son uniformes son excluidos, incluso si, como Joye-Paillier, que son cerca de uniforme.)

Answer 1

Esto le añade algo de información acerca de las cosas que ya he mencionado, estoy bastante interesado, así como en cualquier de los métodos. I nota:

Para conocimiento de los autores, la única conocida primer generación de algoritmos para que la distancia estadística para la distribución uniforme puede ser limitada son el uno propuesto por Maurer [19,20] por un lado, y el algoritmo trivial (es decir. pick aleatorio entero impar en el intervalo deseado, volver si es la primera, y se trate de de nuevo de otra manera) en el otro lado.

-- Fouque y Tibouchi 2014

Por n dígitos de los números primos, llamo a mi genérica de la función de rango con los extremos. Es decir, yo no he visto ninguna en particular ingeniosos métodos para la explotación de este. Si queremos sacrificar la uniformidad tal vez podríamos hacer algo como Fouque/Tibouchi, generando $n-\delta$ dígitos luego de bucle sólo la construcción de $\delta$ dígitos. Quizás la explotación de algunas de las sencillas reglas de divisibilidad rápidamente cortar múltiplos de los pequeños números primos, pero que puede ser de mucha ayuda a través de una decente isprime pretest.

Como usted menciona, el índice aleatorio de selección utilizando el primer método de cuenta que tiene algunas propiedades, pero no a escala. Me pareció que para ser más rápido que otros métodos de hasta 18 bits / 6 dígitos, pero el crossover es muy implementación específica. Yo uso $${\rm nth\_prime}( \pi({low}) + {\rm irand}(\pi({low},{high})-1) )$$ where the prime counts can be cached if desired (useful for n-bit and n-digit). For small sizes like this my nth prime routine is using a cached segment of 1-byte-per-30 bits and just counts bits (by word with popcount when possible). Speeding this up with some tables might move the crossover a couple more bits but really doesn't seem worth it. For some practical comparison at larger sizes, using this method for 14-digit random primes takes my program about 1.4 seconds vs. 80 microseconds for the trivial method. Regardless of what we do, this method won't work for 100+ bits (the current record for prime count being about $2^{86}$ using many days on a 600+ node cluster).

For n-bit, the best paper I've seen is Fouque and Tibouchi (ePrint 2011 or ICALP 2014). It has quite a bit of discussion of the issue as well as algorithms. Their algorithms don't set the ${n}$th bit so need some modification to generate in the range ($2^n$,$2^{n+1}$). I use a modification of their A1 that always sets the top bit, and checks divisibility by primes to 19 using just native-int calculations on the 63 bits that are generated per iteration. I did not find A2 to run faster, but it would use fewer random bits.

For generic ranges including n-digit, I use index selection for 18 or fewer bits, the trivial method for 64-bit ranges, and for larger ranges I divide the range into partitions of size < $2^{64}$, randomly select a partition, then do the trivial algorithm within the partition. The astute observer will note this skews toward the lower partitions (which contain more primes). It's quite a small effect for n-bit or n-digit, though much larger for ranges like ($0$,$2^{100}$). Definitely not uniform.

I did have an idea for how to address that issue, with lots of handwaving involved, and is just "closer to uniform". Set ${pclow},{pchigh}$ to the lower and upper prime count limits of low and high respectively. This has a small error at large sizes (Axler 2014 or Dusart 2010) and is fast. Generate a uniform random value between $pclow$ and $pchigh$ y calcular una enésima primer aproximación (por ejemplo, de 2º orden Cipolla 1902 con la tercera orden de la corrección). Repita si es fuera de la baja/alta gama (debe ser raro con un tamaño decente gama). Ahora hay que hacer un trivial algoritmo dentro de un rango alrededor de este punto. La primera parte se debe a contabilidad para el conjunto de la distribución de los números primos en el intervalo.