C# A Bigint al azar generador de

Question

Estoy a punto de poner en práctica el DSA algorithm, pero hay un problema:

elegir "p", un número primo con L bits, donde 512 < = L < = 1024 y L es un múltiplo de 64

¿Cómo puedo implementar un generador aleatorio de ese número? Int64 tiene "solo" 63 bits de longitud.

Answer 1

se puede generar un número aleatorio con n bits utilizando este código:

var rng = new RNGCryptoServiceProvider(); 
byte[] bytes = new byte[n/8]; 
rng.GetBytes(bytes); 

BigInteger p = new BigInteger(bytes); 

El resultado es, por supuesto, al azar y no necesariamente un número primo.

El BigInteger class se introdujo en .NET 4.0 Framework.

---

para generar grandes números primos, Wikipedia says:

Para los números primos grandes utilizados en la criptografía, es habitual utilizar una forma modificada de tamizado: un rango elegido al azar de números impares de la el tamaño deseado se tamiza contra un número de primos impares relativamente pequeños (típicamente todos los primos menores de 65,000). Los primos candidatos restantes se prueban en orden aleatorio con una prueba de primalidad estándar tal como la prueba de primalidad Miller-Rabin para primos probables.

Por lo que podría hacer algo como esto:

var p = Enumerable.Range(0, numberOfCandidates) 
        .Select(i => RandomOddNumber(bits)) 
        .Where(x => !primesLessThan65000.Contains(x)) 
        .Where(x => PrimalityTest(x)) 
        .FirstOrDefault();