C# Un générateur BigInt aléatoire

Question

Je suis sur le point de mettre en œuvre le DSA algorithm, mais il y a un problème:

choisir "p", un nombre premier avec L bits, où 512 < = L < = 1024 et L est un multiple de 64

Comment puis-je implémenter un générateur aléatoire de ce nombre? Int64 a "seulement" 63 bits de longueur.

Answer 1

Vous pouvez générer un nombre aléatoire avec n bits en utilisant ce code:

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

BigInteger p = new BigInteger(bytes); 

Le résultat est, bien sûr, au hasard et non pas nécessairement un nombre premier. Le BigInteger class a été introduit dans le Framework .NET 4.0.

---

Pour générer de grands nombres premiers, Wikipedia says:

Pour les grands nombres premiers utilisés dans la cryptographie, il est habituel d'utiliser une forme modifiée de tamisage: une gamme choisie de manière aléatoire de numéros impairs de la la taille désirée est tamisée par rapport à un nombre de nombres premiers impairs relativement petits (typiquement tous les nombres premiers inférieurs à 65 000). Les amorces candidates restantes sont testées dans un ordre aléatoire avec un test de primalité standard tel que le test de primalité de Miller-Rabin pour les nombres premiers probables.

Ainsi, vous pouvez faire quelque chose comme ceci:

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