How to generate large random numbers C

问题:

I'm looking for a way to generate large random numbers on the order of 2^64 in C... (100000000 - 999999999), to use in a public key encryption algorithm (as p and q).

I do not want to generate a number smaller than 2^64 (that is, smaller than 100000000).

Is there anything that could help me to do this?

回答1:

random() returns a long which on a 64bit system should be 64 bits. If you are on a 32bit system you could do the following:

#include <inttypes.h>

uint64_t num;

/* add code to seed random number generator */

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

// enforce limits of value between 100000000 and 999999999
num = (num % (999999999 - 100000000)) + 100000000;

Alternatively on a NIX system you could read /dev/random into your buffer:

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <inttypes.h>   

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

// enforce limits of value between 100000000 and 999999999
num = (num % (999999999 - 100000000)) + 100000000;

A

回答2:

You could combine two 4-byte random integers to produce an 8-byte one:

#include <stdint.h>
...
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.

EDIT

Since @Banthar commented that RAND_MAX is not necessarily 2 ^ 32, and I think it is guaranteed to be at least 2 ^ 16, you could combine four 2-byte numbers just to be sure:

uint64_t random = 
  (((uint64_t) rand() <<  0) & 0x000000000000FFFFull) | 
  (((uint64_t) rand() << 16) & 0x00000000FFFF0000ull) | 
  (((uint64_t) rand() << 32) & 0x0000FFFF00000000ull) |
  (((uint64_t) rand() << 48) & 0xFFFF000000000000ull);

回答3:

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

回答4:

I know I'll probably get b____slapped by OliCharlesworth, but use rand() with a scale and offset. It's in stdlib.h In order to cover the whole range you should add that to another smaller rand() to fill in the gaps in the mapping.

回答5:

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<<n (bitwise left-shift) for the power-of 2 operation.

So you can make a large random number of of smaller random numbers.

回答6:

Or, you could use two random number generators with INDEPENDENT seeds and put their output numbers together as suggested. That depends whether you want a 64 bit number of a RNG with a period in the range of 2^64. Just don't use the default call that depends on the time, because you will get identical seeds for each generator. The right way, I just don't know ...