Longest period PRNG in <random>

[highwayman]

uh. Yeah. What the title says. What prng in the <random> header has the longest period? I’m trying to make a super simple stream cipher, and I like being excessive I guess.

[Ganado]

The Mersenne Twister's period is 2^(19937) - 1, which is, let's just say super huge.

I'm not a mathematician, but I know the minstd_* PNRGs can't possibly have a period greater than their modulus, so that leaves their maximum period of being around 2^(31).

The "subtract with carry" engine has a modulus of 2^(word size), and in <random> that's either a word size of 24 or 48, so still no where near MT19937.

https://en.cppreference.com/w/cpp/numeric/random

The choice of which engine to use involves a number of tradeoffs: the linear congruential engine is moderately fast and has a very small storage requirement for state. The lagged Fibonacci generators are very fast even on processors without advanced arithmetic instruction sets, at the expense of greater state storage and sometimes less desirable spectral characteristics. The Mersenne twister is slower and has greater state storage requirements but with the right parameters has the longest non-repeating sequence with the most desirable spectral characteristics (for a given definition of desirable).

[Duthomhas]

Probably the Mersenne Twister, but I could be wrong.

But you would be using the wrong thing. Use a CSRNG instead.
I think that most major C++ compiler/library vendors have fixed the std::random_device by now.

Or, for a shameless plug, you could use my CSPRNG library.
https://github.com/Duthomhas/CSPRNG
_{It will get a minor update someday... but for now it still works just fine.}

PRNGs are for things like videogames and the like, where the results only have to sufficiently approximate randomness.

CSPRNGs are for things where you need actual whitened randomness, like ciphers.

Hope this helps.

[highwayman]

@Ganado, oh. I should have known that lol, thanks!
@duthomas I’m guessing that stands for cryptographically secure prng? um. I think I will. Yes thanks.

[Ganado]

Nah, there's nothing you "should have" known; this stuff is confusing and super math-heavy once you dig into it (at least, it's certainly confusing to me).

[Duthomhas]

Heh, yes, a “cryptographically-secure RNG” is the current way of talking about truly random number generation producing usable stuff.

There is a big halo of <scary heavy math> somehow attached to random number generation, but the scary math stuff is really just proving the PRNG to be correct. Most of everything else is really, shockingly easy.

Heck, strip out all the fancy C++ interface stuff, and you have just a few lines of code to make most high-quality PRNGs work. (Like, ten or fewer! MT is an exception due to its complexity, but it is still pretty small.)

If you want to learn more about the differences between PRNGs and CSPRNGs and how the beasties actually work you can start by Googling around “Aaron Toponce”, who has a pretty good set of introductory readings and videos.

[highwayman]

@duthomas
erm... so, uh. I gonna be completely honest I’ve never used something from git before. How do I do this?

[Duthomhas]

You don't need to. Just use std::random_device.

But if you want to, just click the “clone or download” button and unzip the files to your program’s directory. The “installing” section walks you through compiling it with your project.

Basically the csprng.cpp and csprng.hpp files are just like any other source code files in your (multi-file) project.


The update I am going to make is to default-compile as a library, since so many people have asked about it otherwise. Then all you need to do to use it is the usual ‘link with libcsprng’ stuff.

[highwayman]

Oh, ok. I guess I’ll do that then thanks! :)

[highwayman]

Nah, there's nothing you "should ha...

+

Heh, yes, a “cryptogra...

Oops. These didn’t show up last time I posted sorry.

@Ganado: I just meant that I should have probably thought a bit harder before going to you guys, because ?I already knew half that info. 🤷‍♂️ I absolutely agree too, that math is too much for me. I’m hoping to learn fast though...
@duthomas: how are they truly random, but still usable? Are they still deterministic? Because I’m pretty sure that’s how stream ciphers are supposed to work and now I’m a tad bit confused. Is it just truly random as in "we can find no correlation/connection/whatever-you-call-it between each generated number"? Thanks for the research tip btw!

[dutch]

libsodium is a good CSPRNG.
Assuming you're on windows, it has precompiled binaries for Visual Studio and MinGW.
https://download.libsodium.org/doc/installation

On Ubuntu Linux, I installed pre-compiled binaries like this:

sudo apt-get install -y libsodium-dev

And compiled the following program like this:

g++ -std=c++14 -Wall -W -pedantic rndbytes.cpp -o rndbytes -lsodium

#include <iostream>
#include <iomanip>
#include <sodium.h>

int main()
{
    if (sodium_init() < 0) {
        std::cerr << "libsodium couldn't be initialized\n";
        return 1;
    }

    unsigned char rndbytes[32];
    
    // fill rndbytes with random bytes
    randombytes_buf(rndbytes, sizeof rndbytes);

    std::cout << std::hex << std::setfill('0');
    for (size_t i = 0; i < sizeof rndbytes; ++i)
        std::cout << std::setw(2) << int(rndbytes[i]) << ' ';
    std::cout << '\n';
}

[highwayman]

I’m using Ubuntu, but the problem is it’s not my computer, it’s someone else’s server (Repl.it, an online ide), and they don’t allow sudo and of course I don’t know the password. Kinda gets annoying at time like these lol.

[jonnin]

super simple...
KISS then. If you know a documented period, count, and re-seed it around the period barrier.

[highwayman]

Hm.. I’ll look into it...
Just so you know guys my question was answered a long time ago by duoas. Not that I’m complaining though lol.