Үлкен кездейсоқ сандарды қалай құру керек C

Ашық кілтті шифрлау алгоритмінде (p және q) пайдалану үшін, 2 ^ 64 сантиметрлі ... (100000000 - 999999999) тәртібінде үлкен кездейсоқ сандарды жасау әдісін іздеймін.

Мен 2 ^ 64-ден (яғни, 100000000-нан кіші) аз санды құрғым келмейді.

Мұны істеуге көмектесетін нәрсе бар ма?

9
[100000000 - 999999999] 900,000,000 түрлі мәндер. Бұл сандар - 64 емес, 30 биттің тәртібі.
қосылды автор chux, көзі
2 ^ 64 көп 999999999 артық.
қосылды автор undur_gongor, көзі

6 жауаптар

rAndom() функциясы 64 биттік жүйеде 64 бит болуы керек. Егер сіз 32 биттік жүйеде болсаңыз, келесі әрекеттерді орындай аласыз:

#include 

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;

Немесе NIX жүйесінде буферде/dev/rAndom кездейсоқ оқи аласыздар:

#include 
#include 
#include 
#include    

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

12
қосылды
Менің

RAND_MAX -де 2 ^ 32 емес, 2 ^ 31 .

қосылды автор Chiel ten Brinke, көзі
num = (num << 32) | rand (); , мүмкін, «егер сіз 32 биттегі болсаңыз», онда RAND_MAX = 2 ^ 31-1 немесе әлдеқайда аз. Содан кейін num = (num << 32) | rand (); әрқашан әрқашан шиыршық num жасайды. num% (999999999 - 100000000) бұл мәселені ортақ үлестірімнің одан да көп жетіспеушілігіне байланысты бөлуге көмектеседі.
қосылды автор chux, көзі
u32 кішірек сандарды біркелкі бөлу деп есептесе, мұндай аралас нөмірі u64 = (u32 << 32) | u32 дегеніміз не?
қосылды автор this, көзі
Бұл «100000000-нан кіші сандарды құрғым келмейді» деген талаптың орындалуын қамтамасыз етпейді.
қосылды автор undur_gongor, көзі
Жақсы, бірақ қазір 805933941 (2 ^ 64 -1 mod 899999999) жоғары сандар төмендегі сандарға қарағанда әлдеқайда аз ықтимал ;-)
қосылды автор undur_gongor, көзі
100000000 төменгі шегін және жоғарғы шегі 999999999 кездейсоқ санын генерациялау үшін num = (%% (999999999 - 100000000)) + 100000000; жолын қосыңыз.
қосылды автор David M. Syzdek, көзі
rand() 2 ^ 32 қажет емес RAND_MAX арқылы шектелген. Сонымен қатар, srand() -ге өту үшін бірдеңе қажет. /dev/random функциясы сонымен қатар басқа платформаларда .
қосылды автор Piotr Praszmo, көзі

8 байтты шығару үшін екі 4-байтты кездейсоқ бүтін сандарды біріктіре аласыз:

#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.

ӨҢДЕУ

@Banthar RAND_MAX міндетті емес 2 ^ 32 дегенді білдірмегендіктен, мен оны 2 ^ 16 дегенде кепілдік деп санаймын төрт 2-байттық сандарды біріктіріңіз:

uint64_t random = 
  (((uint64_t) rand() <<  0) & 0x000000000000FFFFull) | 
  (((uint64_t) rand() << 16) & 0x00000000FFFF0000ull) | 
  (((uint64_t) rand() << 32) & 0x0000FFFF00000000ull) |
  (((uint64_t) rand() << 48) & 0xFFFF000000000000ull);
9
қосылды
Бір-бір: RAND_MAX 2 ^ 32 болуы екіталай. Ол (2 ^ 32) - 1 болуы мүмкін. Дегенмен, бұл өте сирек. (2 ^ 31) - 1 немесе (2 ^ 15) - 1 жалпы мәніне ие INT_MAX секілді. C 2 ^ 16 емес, кем дегенде (2 ^ 15) - 1 болуы үшін RAND_MAX анықтайды.
қосылды автор chux, көзі
| орнына нөмірлерді біріктіру үшін ^ пайдалансаңыз, маскировка туралы алаңдамайсыз.
қосылды автор caf, көзі

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

7
қосылды
2018 жылы тамызда жасалған openssl.org/docs/crypto/rand.html өлі сілтемесі Сілтемедегі проблемалардың бірі тек жауап береді.
қосылды автор chux, көзі
Немесе Windows Vista және Windows Vista жүйесінде BCryptGenRandom жоғары.
қосылды автор Alexey Frunze, көзі
+1: rand() арқылы бұл қауіпсіздік саңылауы ( rand() шығуын болжау қиын емес)
қосылды автор Frank Farmer, көзі

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.

Осылайша сіз үлкен кездейсоқ сандардың аз кездейсоқ сандарын жасай аласыз.

3
қосылды
L = (2 ^ n) * A + B - B диапазоны [0 ... (2 ^ n) -1] болмаса, мәселе. B ауқымы кеңінен (және әлі де күш-2) болса, L = (2 ^ n) * A ^ B қолдануға жақсырақ болады. Ең жақсы L = (max_possible_value_of_B + (type_of_L)) 1) * A + B
қосылды автор chux, көзі
u32 кішірек сандарды біркелкі бөлу деп есептесе, мұндай аралас нөмірі u64 = (u32 << 32) | u32 дегеніміз не?
қосылды автор this, көзі
@ бұл. Менің ойымша, иә, бірақ математик сұраңыз.
қосылды автор Basile Starynkevitch, көзі
L, n, A және b әріптері дегеніміз не? түсіндіре аласыз ба?
қосылды автор Ameen, көзі

Мен, OliCharlesworth-тің, бәлкім, мен брандайтын шығармын, бірақ шкаламен және теңестірумен rand() қолданамын. Бұл stdlib.h бар. Барлық ауқымды жабу үшін, оны басқа шағын рандқа() салыстырудағы бос орындарды толтыру үшін қосу керек.

3
қосылды

Немесе сіз INDEPENDENT тұқымдары бар екі кездейсоқ сандар генераторларын қолданып, олардың шығу нөмірлерін ұсынғандай етіп қойыңыз. Бұл 2 ^ 64 ауқымындағы кезеңмен бірге RNG-тің 64 бит санына байланысты. Уақытқа байланысты әдепкі қоңырауды пайдаланбаңыз, себебі әр генератор үшін бірдей тұқымдар болады. Оңтайлы жол, мен білмеймін ...

1
қосылды