Hoe grote willekeurige getallen te genereren C

Ik ben op zoek naar een manier om grote willekeurige getallen te genereren in de orde van grootte van 2 ^ 64 in C ... (100000000 - 999999999), om te gebruiken in een algoritme voor codering met openbare sleutels (als p en q).

Ik wil geen getal kleiner dan 2 ^ 64 genereren (dat wil zeggen, kleiner dan 100000000).

Is er iets dat mij kan helpen om dit te doen?

9
[100000000 - 999999999] is 900.000.000 verschillende waarden. Dit zijn getallen in de orde van 30 bits, niet 64.
toegevoegd de auteur chux, de bron
2 ^ 64 is veel groter dan 999999999.
toegevoegd de auteur undur_gongor, de bron

6 antwoord

rEENndom() retourneert een lEENnge tijd die op een 64bit-systeem 64 bits moet zijn. EENls je een 32bit-systeem gebruikt, kun je het volgende doen:

#include 

uint64_t num;

/* EENdd code to seed rEENndom number generEENtor */

num = rEENnd();
num = (num << 32) | rEENnd();

// enforce limits of vEENlue between 100000000 EENnd 999999999
num = (num % (999999999 - 100000000)) + 100000000;

EENls EENlternEENtief op een NIX-systeem zou je/dev/rEENndom in je buffer kunnen lezen:

#include 
#include 
#include 
#include    

int fd;
uint64_t num; 
if ((fd = open("/dev/rEENndom", O_RDONLY) == -1)
{
    /* hEENndle error */
};
reEENd(fd, &num, 8);
close(fd);

// enforce limits of vEENlue between 100000000 EENnd 999999999
num = (num % (999999999 - 100000000)) + 100000000;

EEN

12
toegevoegd
Op mijn pc is RAND_MAX 2 ^ 31 , niet 2 ^ 32 .
toegevoegd de auteur Chiel ten Brinke, de bron
num = (num << 32) | rand (); is waarschijnlijk zwak gegeven "Als u een 32bit" gebruikt, is RAND_MAX waarschijnlijk 2 ^ 31-1 of veel minder. Vervolgens num = (num << 32) | rand (); genereert altijd een onbewerkt aantal met enkele bits gewist in dezelfde positie. num% (999999999 - 100000000) helpt dit probleem rond te verdelen maar gaat ten koste van nog meer gebrek aan een uniforme distributie.
toegevoegd de auteur chux, de bron
Ervan uitgaande dat kleinere getallen u32 gelijkmatig verdeeld zijn, is zo'n gecombineerd getal u64 = (u32 << 32) | u32 ook?
toegevoegd de auteur this, de bron
Dit zorgt er niet voor dat de vereiste "Ik wil geen kleiner nummer dan ... 100000000" genereren, wordt gehaald.
toegevoegd de auteur undur_gongor, de bron
Beter, maar nu zijn de cijfers boven 805933941 (2 ^ 64 -1 mod 899999999) iets minder waarschijnlijk dan de onderstaande nummers ;-)
toegevoegd de auteur undur_gongor, de bron
Voeg de regel num = (num% (999999999 - 100000000)) + 100000000; toe om een ​​willekeurig aantal van de onderlimiet van 100000000 en de bovengrens van 999999999 te genereren.
toegevoegd de auteur David M. Syzdek, de bron
rand() is gelimiteerd door RAND_MAX die niet noodzakelijk 2 ^ 32 is. En u moet nog steeds iets doorgeven aan srand() . /dev/random -functionaliteit is ook beschikbaar op andere platforms .
toegevoegd de auteur Piotr Praszmo, de bron

Je zou twee willekeurige bytes van 4 bytes kunnen combineren om een ​​8-byte te produceren:

#include 
...
uint64_t random = 
  (((uint64_t) rand() <<  0) & 0x00000000FFFFFFFFull) | 
  (((uint64_t) rand() << 32) & 0xFFFFFFFF00000000ull);

Since rand returns int, and sizeof(int) >= 4 on almost any modern platform, this code should work. I've added the << 0 to make the intent more explicit.

The masking with 0x00000000FFFFFFFF and 0xFFFFFFFF00000000 is to prevent overlapping of the bits in the two numbers in case sizeof(int) > 4.

Bewerken

Omdat @Banthar heeft opgemerkt dat RAND_MAX niet noodzakelijk 2 ^ 32 is, en ik denk dat het ten minste 2 ^ 16 is, kunt u combineer vier 2-byte-nummers om zeker te zijn:

uint64_t random = 
  (((uint64_t) rand() <<  0) & 0x000000000000FFFFull) | 
  (((uint64_t) rand() << 16) & 0x00000000FFFF0000ull) | 
  (((uint64_t) rand() << 32) & 0x0000FFFF00000000ull) |
  (((uint64_t) rand() << 48) & 0xFFFF000000000000ull);
9
toegevoegd
Off-by-one: RAND_MAX is zeer onwaarschijnlijk 2 ^ 32 . Dit kan (2 ^ 32) - 1 zijn. Maar zelfs dat is ongewoon. Waarschijnlijker is het hetzelfde als INT_MAX met een gemeenschappelijke waarde van (2 ^ 31) - 1 of (2 ^ 15) - 1 . C geeft aan RAND_MAX ten minste (2 ^ 15) - 1 , niet 2 ^ 16 .
toegevoegd de auteur chux, de bron
Als u ^ gebruikt om de getallen te combineren in plaats van | , hoeft u zich geen zorgen te maken over de maskering.
toegevoegd de auteur caf, de bron

You're looking for a cryptographic-strength PRNG, like openssl/rand: http://www.openssl.org/docs/crypto/rand.html

7
toegevoegd
openssl.org/docs/crypto/rand.html dode link in augustus 2018 Een van de problemen met een antwoord op een link.
toegevoegd de auteur chux, de bron
Of BCryptGenRandom op Windows Vista en hoger.
toegevoegd de auteur Alexey Frunze, de bron
+1: gebruik rand() want dit is een beveiligingslek (het voorspellen van de uitvoer van rand() is niet erg uitdagend)
toegevoegd de auteur Frank Farmer, de bron

You can make a large number L out of smaller numbers (e.g. A & B). For instance, with something like L = (2^ n)*A + B where ^ denotes exponentiation and n is some constant integer (e.g. 32). Then you code 1< (bitwise left-shift) for the power-of 2 operation.

U kunt dus een groot willekeurig aantal kleinere willekeurige getallen maken.

3
toegevoegd
L = (2 ^ n) * A + B is een probleem als het bereik van B niet [0 ... (2 ^ n) -1] is. Het is beter om L = (2 ^ n) * A ^ B te gebruiken als het bereik B groter is (en nog steeds een macht van 2). Het beste is om L = (max_possible_value_of_B + (type_of_L) 1) * A + B
toegevoegd de auteur chux, de bron
Ervan uitgaande dat kleinere getallen u32 gelijkmatig verdeeld zijn, is zo'n gecombineerd getal u64 = (u32 << 32) | u32 ook?
toegevoegd de auteur this, de bron
@deze. Ik denk dat ja, maar je moet een wiskundige vragen.
toegevoegd de auteur Basile Starynkevitch, de bron
wat betekenen de letters L, n, A en b ? zou je het kunnen uitleggen?
toegevoegd de auteur Ameen, de bron

Ik weet dat ik waarschijnlijk b____ gesolliciteerd krijg door OliCharlesworth, maar gebruik rand() met een schaal en offset. Het is in stdlib.h Om het hele bereik te dekken, moet je dat toevoegen aan een andere kleinere rand() om de gaten in de toewijzing in te vullen.

3
toegevoegd

Of u kunt twee willekeurige-nummergeneratoren gebruiken met ONAFHANKELIJKE zaden en hun uitvoergetallen bij elkaar voegen zoals voorgesteld. Dat is afhankelijk of u een 64-bits nummer van een RNG wilt met een periode in het bereik van 2 ^ 64. Gebruik gewoon niet de standaardoproep die afhangt van de tijd, want je krijgt identieke zaden voor elke generator. De juiste manier, ik weet het gewoon niet ...

1
toegevoegd