/r/RNG

Photograph via snooOG

Discussion about all things randomness.

/r/RNG

1,224 Subscribers

2

RNG calculator that generates # of attempts

I realize this may not be the right place for this. But does anybody know of an online calculator/program that can generate the number of attempts until a certain number is reached.

For instance I want to generate a random number out of 12,000, say 5,608 And then I’d want the calculator to tell me how many actual attempts it would take to generate 5,608 again out of 1-12,000, because as we know it can take more than 12,000 tries to get that same number.

I know this would probably be pretty easy to code but let’s assume I can’t do this.

5 Comments
2024/04/15
14:22 UTC

1

[Resource Request] I want to learn specifically about RNGs Algorithms (and their variants) and Random Cryptography in general

For context, I have a double degree in physics and computer science and I recently developed a basic secure password generator software made in Java using the SecureRandom class. And this made me very interested in Random Cryptography, RNG Algorithms, their variants and related topics. And I really liked it so much that I want to start studying more about this specific subject to specialize in my academic career, start publishing articles about it and maybe one day become a reference in this.

Reading a few references I found about RNG algorithms, I learned some basic concepts, (for example I saw that, as far as I know, my secure password generator software can be classified as what its called CSPRNG), and I also learned some other variations, such as TRNGs, which has its sources of entropy coming from physical phenomena of chaotic systems (which can be, for example, the movement of fluids in lava lamps like Cloudflare does, or also quantum mechanics based algorithms, or using radio noise, and much more)...

However, in my attempts to research books or materials about this to really study/learn, I noticed that it is very difficult to find books or materials specifically about that. Whenever I tried to search specifically about these things, I either found some superficial results from technology sites speaking superficially about RNGs, or Cryptography books that teachs Cryptography in general, (I mean, not specifically about Random Cryptography or RNGs)...

And, having already made secure password manager software, I know the basics of cryptography and I've already learned a lot more of things along the way, of course, cryptography in its most general form is obviously related to the subject of Random Cryptography and RNGs... But what I'm trying to say is that sometimes it can be very dense to read an entire cryptography book (that teaches cryptography in general) without much relation to Random Cryptography or RNGs, that is what I'm trying to research...

So, I come here humbly to ask:

  1. First, where to start? (besides doing a password generation software, because I already did)
  2. What good books/materials are there on Random Cryptography and RNGs Algorithms?
  3. What scientific papers or authors should I read on the subject?
  4. What types of tests are standards for metrics in the scientific papers on this subject for RNGs algorithms?
  5. Is there something else that I should know? Give me tips please.

5 Comments
2024/04/15
02:40 UTC

3

64 Bit Linear Transformation

With a function that takes a uint64_t n and returns (n+a)*b where an and b are constants, how can I find values for them that would lead to a period o 2^64-1? I can't really brute force it

2 Comments
2024/03/09
22:59 UTC

2

New idea for almost infinite PRNGs

I've been testing a new idea for almost infinite PRNGs.

I'm using multiple LCGs with prime numbers as multiplier, modulus and initial value; the constant does not seem to matter that much, so I'm using 1. I combine the output from each LCG with XOR to produce the final output.

Although LCGs are not particularly good individually, I've found that when several are combined together, the output rapidly becomes excellent (passes all tests in Practrand), and the period also increases significantly.

I've been using LCG parameters selected from a table containing 10million primes from 100003 to 179606689, and I've typically been using 10-20 LCGs. My tests suggest that the period of the combined 20-LCG is equal to the product of the periods of the each individual LCG. So for a 20-LCG RNG, the period would something in the order of 100000000 ^ 20 = 10e160. If another 20-LCG RNG was started whenever the previous RNG repeated (and so on), then the combined period would be in the order of ((10e8 ^ 20) ^ (10e7 ^ 3)) = 10e3360 (if my maths is correct). This could be increased if the table of primes was made bigger.

I recently found that this idea is not new... it's called Wichmann-Hill, but the original definition used just 3 LCGs, whereas I'm suggesting a larger number.

Obviously, I've only been able to test a relatively small number of the total possible RNGs I could create from my primes table, but every one has passed all tests in Practrand.

I would be interested to hear what others think, and especially from anyone who has experimented with the same idea.

5 Comments
2024/02/19
17:14 UTC

4

Hardware RNGs

I'm fascinated with RNGs and I found your wiki files. That has a lot of good stuff and things I don't know yet. I'd be glad to be approved for wiki access (editing) if the mod will give it.

There are a couple of things I'd like to say about HWRNGs. One is that they can be deterministic. You can do both types in hardware. You can use a shift register and an XNOR gate (or XOR with more work). You can tap the 2 highest pins of the shift register, XNOR them, and feed that back in as the input. That is an LFSR (linear feedback shift register). LFSRs are deterministic since you always get the same numbers in the same order.

LFSRs tend to inherently have certain weaknesses, namely 2 unless more extensive hardware or coding is used. There will be 1 number it cannot return. The other problem is that if by chance the number it cannot return is somehow put there, it latches up. So there is always a missing result and an unusable seed. If software, you can trap for these conditions. You can use logic to mitigate the seed that cannot be used. That prevents the latching problem but exacerbates the other problem since you not only have a result that cannot be returned but another result is returned twice. So then you replace the output of that number with the unusable seed. So with proper trapping, every number can be used as a seed, and every possible result can be returned.

In a hardware LFSR, XNOR is preferred since the shift register initializes to 0. XNOR is an equality function (only in the 2-input version). So if you take the top 2 bits of the shift register and XNOR them, the 2 starting zeroes become 1. Then you are feeding the 1 back in. But really thinking it through in my head, I realize that for an 8-bit shift register, you'd only get numbers 0-254. 255 is the number that latches the LFSR and cannot be returned. For something like white noise generation in an arcade game (like Asteroids), that might be good enough. The simplest mitigation I know of would be to make it at least a bit wider. So you would get 0-510, but never 511, but if you take only 8 bits, you will have 2 periods, one with and without 255. That is not a perfect solution, and if you add more bits, you get better odds. Of course, you could do other things in terms of trapping, or you could use counters, pause the LFSR, and insert the missing result. Or, you can just settle with it being a result short of a perfectly balanced period. You could combine that with another HWRNG on the same board.


In terms of noise sources, one is shot noise. Schottky noise is a similar phenomenon. You take a diode or transistor (usually with the collector lead clipped or unused) and reverse bias it to its breakdown voltage. Often, that is about 12-18 volts, depending on what diode is used, and 9-12 volts for certain transistors. Theoretically, you should expect nothing since diodes and transistors are supposed to only allow current through in one direction. However, if you block enough current, some electrons will slip through and attempt to conduct. Then you amplify/buffer the output of that. There are at least 2 different things you can do at this point. One is to treat this as an analog signal. So you can send it to an ADC IC or a microcontroller ADC input line. Then you can read bytes or words at a time. Or, you can treat that as a digital signal. You could control the gain using a potentiometer and/or a Zener diode, and then maybe feed that to a Schmitt trigger to clean up the signal, and then clock that into a shift register. (Or, you could even do both, treating the signal as both AM/analog and as FM/digital, and reuse some of the entropy within a different context and span of time.)


Now, I've been pondering designing a true HRNG using mostly 74xx ICs and very few support components. One of the easier ways would be to use ring oscillators. A ring oscillator is just a looping inverter (NOT gate) chain. There are an odd number. It seems that the longer the chain, the more entropy you have, but also, the slower things change. You'd use at least 2 of them of different lengths to get both the effects of entropy and the deterministic aspects of beating/adding/XORing 2 clocks. If 2 clocks that are out of tune with each other were to start at the precise same time and remain the precise same size the entire time of operation, that would be deterministic. However, there are tiny variations in this, and using a ring oscillator as opposed to a crystal oscillator would increase the variations (jitter) present. So using longer inverter chains and multiple inverter chains should increase the entropy. And using 3 of these together is considered good practice. That way, if there is a chance one of the ROs synchronizes to the board frequency, you'd have a 3rd RO to mitigate this.

Then, where you would go from this would be to use a shift register to make bytes (or words, doubles, quads) out of the input stream. You could apply whitening as you make them and even have multiple RO units to increase yield. For instance, you could have 2 RO units and take turns switching between them and whitening the stream. Then you can complete an evaluation of 2 bits each cycle. That would allow each shift register to have moved twice before you evaluate it. And really, you can tap off 2 points on the shift register, XOR them for a control signal, and if they XOR to 1, then the higher of the 2 bits is used for the output. And if they XNOR to 1, maybe use another source altogether such as an LFSR, or conversely, rotate the shift register and maybe only use an LFSR as the output when you've exhausted rotating the shift registers.

And you could get fancy with this if you wanted. I've wondered what would happen if you take 2 ROs to drive 2 different sets of counters. Then take another oscillator to drive a multiplexer (mux). That sounds more deterministic than above, but you could use a wider mux and either 2 ROs to switch it, or an oscillator and another counter. So, if you use a quad mux, what would the other 2 inputs be? One could come from a shift register with ROs A and B XORed together. For a 4th input, one could add the counters. And if one uses an 8-channel mux? Maybe add an LFSR. XOR the LFSR with the other shift register, and do 2 other things. Like maybe have 2 more shift registers and XOR a bit from the LFSR with A for one and B for the other. Or options to invert the counters, etc.


Another note. I read how someone used a 555 timer and an Arduino to make random numbers. To me, it blurs the line between deterministic and nondeterministic. But in practice, it may be more nondeterministic. So the 555 is configured to produce sawtooth waves. There is a line that is normally used that you can leave floating to possibly improve the entropy. Then the output is fed into the ADC line on the Arduino. Then some whitening is done using code. That seems to produce acceptable results and pass most Monte Carlo tests. Some others will read the line with nothing connected to it and get reasonable enough random numbers.

Now, one thing that stands out to me here is that the 555 approach may not be all that different from using a ring oscillator driving a counter. The sawtooth wave is sampled at different points on it, depending on the CPU/MCU clock. Then that is converted to a digital result, ranging from 0-255 (or 0-65535) or whatever. It seems this could be easily simulated digitally. Just use a ring oscillator and counter ICs. The increasing count is like the increasing amplitude of the sawtooth wave, and then it rolls over to zero, just like the sudden drop of the sawtooth wave.

8 Comments
2024/02/16
14:40 UTC

12

Collatz-Weyl Generators

This is two line PRNG which I named CWG128:

static __uint128_t c[4]; // c[0] must be odd

__uint128_t CWG128(void){
c[1] = (c[1] >> 1) * ((c[2] += c[1]) | 1) ^ (c[3] += c[0]);
return c[2] >> 96 ^ c[1];
}

By using different c[0], you can initialize 2^127 independent streams, using random numbers or just a counter, but then you have to skip 96 outpus to decorelate states of the generators.

One of the simplest generator based on the original Collatz sequences is:

static __uint128_t x, weyl, s; // s must be odd

bool Collatz_Weyl(void){
x = (-(x & 1) & (x + ((x + 1) >> 1)) | ~-(x & 1) & (x >> 1)) ^ (weyl += s);
return x & 1;
}

It returns one bit in each iteration. It can produce 2^127 bits, until the Weyl sequence will loop. It is bassically just a Collatz funtion combined with a Weyl sequence, to prevent short cycles:

static __uint128_t x, weyl, s; // s must be odd

bool Collatz_Weyl(void){
if(x % 2 == 1){x = (3*x+1)/2;}
else{x = x/2;}
x ^= (weyl += s);
return x & 1;
}

Several authors have previously tried to use Collatz sequences to generate randomness. For example, Givens R. in "On Conway’s generalization of the 3x + 1 problem" considered certain generalizations, functions that generated sequences very slowly diverging to infinity. The problems have always been short cycles or divergence to infinity. The use of Weyl sequences and modulo operation eliminates these problems - the number of schemes that we can create this way is as huge as number of generalizations of Collatz-type functions we can think of. For example generator:

static __uint128_t x, weyl, s; // s must be odd
 
bool Five_x_Weyl(void){
if(x % 2 == 1){x = (5*x+1)/2;} 
else{x = x/2;} 
x ^= (weyl += s); 
return x & 1; 
}

Produces good quality pseudorandom bits as well.

Paper:

https://arxiv.org/abs/2312.17043

6 Comments
2024/01/18
22:23 UTC

2

Acura MDX HDD Shuffle

(I don’t know crap about RNGs) The Acura MDX has an HDD music source where you can upload CDs to build up a playlist, and it has a Random setting that shuffles the music. The shuffle kind of sucks, playing a much smaller variety of songs than there is available (anecdotal, heard many accounts though). I was curious what makes the shuffle system tick, anyone know or know how to determine?

2 Comments
2024/01/15
20:48 UTC

2

Gas Tube Number Generator

https://www.sensitiveresearch.com/Objects/GTNG/

Discovered today while hunting around for the General Radio 1390B using general terms (I couldn't remember the company name, but knew it had a gas tube in it).

0 Comments
2024/01/10
17:56 UTC

6

Rubik's Cube RNG

An Idea

The other night I got to thinking about manual, by-hand, non-electronic random number generators. We're already familiar with flipping coins, tossing dice, shuffling playing cards, drawing lottery balls from a spinning tumbler, and shaking paper, but what else is there? I have a 3×3 Rubik's Cube on my bookshelf and thought that might work.

The Math

The number of unique permutations for different sized N×N cubes is well known:

Scrambling the Cube

The goal is scrambling the cube enough times to put it in one of those unique states such that it's improbable for an adversary to duplicate. The trick is in figuring out how many scrambles are necessary to create that security margin. It's critical that each smaller cube has the uniform possibility of reaching every position (except the center for odd-number N×N cubes), and that each position has the uniform possibility of seeing every possible rotation.

For the 3×3 Rubik's Cube God's Number is 26. This means that every possible permutation of the 3×3 cube can be solved in 26 quarter turns or less. In other words, you cannot scramble a 3×3 cube worse than one that requires 26 quarter turns to solve.

The World Cube Association's official TNoodle software averages 18-19 turns from a solved state before presenting a 3×3 cube to the contestant to solve. Note that each twist is not a quarter turn however—some are half turns.

As such, it seems reasonable to assume that 18-26 turns (quarter or half) might be sufficient for scrambling a 3×3 cube preventing someone else from blindly duplicating it. More rigor should be done here to confirm this, however.

Security Margins

If we were to use TNoodle as a ballpark number for the number of turns necessary to maximize the work of an adversary wishing to duplicate the final state, then for each N×N cube, it would look something like this:

N×NTurnsBits per scramble512 bits
2×2112124 scrambles
3×319658 scrambles
4×4441524 scrambles
5×5602473 scrambles
6×6803852 scrambles
7×71005321 scramble
8×8???7221 scramble

The World Cube Association doesn't have contests for 8×8 cubes, so it's not an option in the TNoodle software. However, considering the above pattern of approximately 20 turns per N×N cube, it seems reasonable that at 8×8 cube would require 120 turns to sufficiently scramble the cube.

Other than an 8×8 cube, the 3×3 cube remains the most efficient when it comes to maximizing the security per turn. For a 512-bit RNG, you need to record the state of 8 separate scrambles of 19 turns each. This is a total of 152 turns.

How-To

Obviously, scrambling the cube should be done blind. This would remove any influence or bias you might have on the cube trying to put specific colors into specific positions. Scrambling the cube behind your back while counting the turns might be the best approach. Once the cube is sufficiently scrambled, all you have left to do is record all 6 faces. You could do this face-by-face or layer-by-layer.

For example, you could record the top face from the top left smaller cube working left-to-right then top-to-bottom ending with the lower right smaller cube. The take the same approach with the right face, back face, left face, and bottom face.

If you wished to do it layer-by-layer, then again, you could start with the upper left smaller cube on the top face ending with the bottom right smaller cube. Then record all outer colors on the top row, starting with the front face, then right face, bottom face, and ending with the left face. Move to the middle row following the same pattern, then the bottom row, and end with recording the faces on the bottom row.

All HWRNGs have inherent biases, and this Rubik's Cube RNG is no different. When you know the color pattern of one of the smaller cubes, this provides information about what's left with the remaining smaller cubes, as the position and orientation of each smaller cube is dependent on the others. So we'll need to whiten the RNG to remove the bias. This is best accomplished by running the output through a cryptographic hashing function, such as SHA-3.

Example

Knowing that each scramble provides about 65 bits of symmetric security for a 3×3 cube, if I wished to generate a 256-bit symmetric key, then I would need to record the output for scrambles. Suppose they were (O=orange, G=green, Y=yellow, W=white, R=red, B=blue):

ScrambleTopLeftFrontRightBackBottom
1GOOYWGRRBYRBOOBOWRWGYRGWYBWOOGBRGRWRWBOYBYBWWGYGOYRBGY
2OYWWWOROGGGBWOBOYGWWROGBROBWORRRGWWOYGYRBBYYGYGORYRWBB
3YORYWWWGBRRRYOWWBWBOYRGGOGROOWWRWYBOGYBBBBGGOBRGOYRGYY
4YWWBWWWYGBYBRORGOGOWWYGOYWGORRBRYRRBBGOOBGYYROOYGYBWGR

I could then get my 256-bit key via:

$ cat << '.' | sha3sum -a 256
GOOYWGRRBYRBOOBOWRWGYRGWYBWOOGBRGRWRWBOYBYBWWGYGOYRBGY
OYWWWOROGGGBWOBOYGWWROGBROBWORRRGWWOYGYRBBYYGYGORYRWBB
YORYWWWGBRRRYOWWBWBOYRGGOGROOWWRWYBOGYBBBBGGOBRGOYRGYY
YWWBWWWYGBYBRORGOGOWWYGOYWGORRBRYRRBBGOOBGYYROOYGYBWGR
.
dc4ca75eaeb54aff44aacc19e4b6c842e1016af3ec607a835847ad821611caf5  -

Gotchas

When recording the colors with an odd N×N cube, don't be tempted to put the center squares into a certain position (EG, white on top). When you're done scrambling, just place it on the table and start recording, regardless of orientation.

This RNG is obviously error-prone. As a HWRNG, it's not important that the process can be repeated, so mistakes are generally okay. However, you really should make every effort to be as accurate as possible. The more mistakes you introduce transcribing the colors, the more you could be reducing the security margin.

Taking two photos of the cube with your phone might be a better idea, where each photo can see all the colors of 3 unique faces. Concatenate both photos and hash with SHA-3, then you don't need to worry about being error-prone with the transcription. This does reduce the elegance a bit though of being "by hand", but then again, you're still relaying on SHA-3, so meh.

The scrambling process is kinda slow. Obviously this isn't going to be something you want to do regularly. Instead, rather than using the output directly, you would be better off sending the output once to a CSPRNG and using the CSPRNG going forward to get your keys. So seed your kernel RNG, then use that for everything cryptographically related:

$ echo 'GOOYWGRRB...' > /dev/random

THIS PART IS CRITICAL: Once you've recorded the colors of the cube, you need to destroy the transcription (or photos) as well as further scrambling the cube. This also means erasing the command(s) from your shell history. Remember, the goal is to make the adversary reproducing the state as difficult as theoretically possible. Kind of defeats the purpose if you leave the state lying around for them to discover.

However, it does beg the question: if you want to use the cube again as an RNG, should you start from a solved state, or is carrying the previous state into the next okay? My intuition tells me that carrying the state along with you is fine, so long as you continue to provide the sufficient number of twists for your cube (after destroying the previous state). But solving it "resets" the cube giving the adversary no information about any previous states should they come in possession of your cube. Solving it also could be good practice. Shrug.

2 Comments
2023/12/01
04:32 UTC

2

Xoshiro 256 ss Vs pp

I can't really find any difference on the net. Can you explain it to me?

3 Comments
2023/11/02
07:53 UTC

6

Secure random generator optimized for Microchip AVR

Following up on my AVR-optimized non-secure PRNGs, I've attempted to create a secure version. I'm not a cryptographer, so buyer beware. The design is loosely inspired by ChaCha20, but optimized for 8-bit operations available on the AVR.

Testing a highly reduced round version with PractRand, it produces better results than similarly reduced ChaCha. Because of the internal cipher feedback construction, it is not trivially reversible so there's no need for an addition step at the end, saving code and RAM space. Compared to ChaCha, the obvious downside is that it runs very poorly on modern 64 bit superscalar architectures.

Speed and code size (on AVR) are better than the best optimized ChaCha implementation I could find, and the code structure is very simple to understand and easy to modify for specific applications. Of course, if you care about proven security and interoperability, ChaCha is a much better choice, but for highly constrained applications, such as a firmware bootloader, this may be useful. Also, of course, if you just need a high quality random generator with random seek function, you can use this too. Another application could be a whitening function for a true random generator. Just start with a random state, and repeatedly call the dance() function with some true random bits in the IV parameters, without resetting the state.

Code is available on github, with test vector and generic C version for testing:

https://github.com/Arlet/pseudo-random-number-generator/tree/main/avr/dance

1 Comment
2023/09/20
06:48 UTC

7

New design for 128 bit PRNG on Arduino

I came up with a new design for a PRNG optimized for Microchip AVR used in Arduino project. It uses a 128 bit state, and similar ideas using ADC, EOR and SWAP as my previous version. The specific sequence of the round function was determined by a genetic algorithm and testing the sequences using PractRand, like I did last time.

It runs in 155 cycles, and you could potentially use all 16 byte of the state as random numbers. The actual round function is 72 cycles. The rest is all used for memory load/store and other overhead.

https://github.com/Arlet/pseudo-random-number-generator/blob/main/avr/rand16.S

While this code was not meant to be secure, I don't see an obvious way where you could extract the internal state from a series of 32 bit random outputs, but I'm not ruling it out. If someone has a clue, I'd be happy to hear either way.

If you initialize the state as all zeroes, and call the rand16() function once, you get the following state output:

67 63 8b 97 8c 0a aa 61 b6 b6 9f 21 ed fc e7 2a
2 Comments
2023/09/07
18:16 UTC

2

A very general xoshiro/xoroshiro implementation

David Blackman & Sebastiano Vigna introduced the xoshiro/xoroshiro family of pseudorandom number generators. They are very efficient and have a relatively small footprint but still display excellent statistical properties.

There are C versions of the generators available at the author's website. Wrapping those routines so they conform to the C++ std::uniform_random_bit_generator concept is a trivial exercise. Once that is done you can use the generators to drive any of the distributions in the standard C++ library.

We have a single header file xoshiro.h implementation of the generators that does just that but which is distinguished in a number of other ways:

  1. The library classes are templatized across all of the many parameters that define a specific xoshiro/xoroshiro variant. This means you can instantiate any member of the xoshiro/xoroshiro family.
  2. Of course, only a very limited number of those have ever been properly vetted for suitability as being “good”. Therefore we provide some simple type aliases for the recommended default generators. The overall default is just xso::rng (everything is in the xso namespace).
  3. Efficient jump ahead methods are provided that work for arbitrary jump sizes. The jump sizes can be enormous which means you can partition a single random number stream into non-overlapping sub-streams that are large enough for parallel processing applications. There is a xso::partition class that makes this easy to do.
  4. By optionally incorporating the extra header-only bit library for linear algebra over GF(2) you can access extra functions to extract the transition matrix for any xoshiro/xoroshiro generator. This is the key to the mathematical analysis of a generator.
  5. The library is also fully documented. The documentation site includes an explanation of how we implemented the jump techniques which were originally discovered by Haramoto et al.

The code is available here. It has a permissive MIT License.

0 Comments
2023/09/04
16:59 UTC

9

Fast, high quality PRNG for Arduino (Microchip AVR)

I made a PRNG for Arduino in AVR assembly language. The routine accepts a pointer to a 7 byte state, updates the state, and returns a 32 bit random number using standard register convention.

The period is guaranteed to be at least 2^48 numbers. Excluding call/ret overhead, the routine runs in 51 cycles, so is much faster than standard library version and has better quality as well. It's also faster than the small JSF32 PRNG which takes 500 cycles. The output has been verified with BigCrush and PractRand (up to 16TB). There are no bad seed values.

Code can be found here: https://github.com/Arlet/pseudo-random-number-generator/blob/main/avr/good-32-bit.S

10 Comments
2023/07/26
13:45 UTC

4

Looking for a way to do xorshift32 jump ahead

I've recently been reverse engineering the mechanics in a game where the xorshift32 algorithm is used, specifically with a, b, and c values of 13, 17, and 5. I need to be able to jump N seeds forward so that I can use parallel processing to speed up searches. However, everywhere I looked only showed code. jump polynomials, and examples from xorshift128 and higher. Based on what I've found, it seems possible to do jump ahead with xorshift32, but I can't seem to find out how. I'd appreciate it if anyone had knowledge on this and could help me out.

3 Comments
2023/07/25
00:06 UTC

4

Is this a known PRNG algorithm? And is it possible to find the lowest input values from a given range of outputs without brute force?

I've been reverse engineering an old N64 game, and came across this PRNG used to turn any 10-character user-inputted code into a random gang. Here's a C++ implementation of the PRNG:

uint64_t refactored64BitPRNG(uint64_t seed) {

    const int bitToCheck[30] = { 3,  7, 15, 19, 41, 52,
                                 6, 11, 17, 27, 55, 60,
                                10, 14, 35, 39, 44, 61,
                                 2,  8, 25, 31, 38, 57,
                                 8, 20, 24, 33, 49, 56 };

    for (unsigned int outerLoop = 0; outerLoop < 5; outerLoop++) {

        for (unsigned int middleLoop = 0; middleLoop < 128 + bitToCheck[(outerLoop * 6) + 5]; middleLoop++) { // loop between 180 and 189 times

            seed = (seed << 1) | ((seed >> 63) & 1); // wrapped bitshift

            uint64_t toggleBit = 1;

            for (unsigned int innerLoop = 0; innerLoop < 6; innerLoop++) {

                toggleBit = toggleBit ^ ((seed >> bitToCheck[(outerLoop * 6) + innerLoop]) & 1); // toggle if the checked bit is a 1

            }

            seed = seed ^ toggleBit; // toggle least significant bit if an even number of checked bits were 1s

        }

    }

    return seed;

}

I've tried looking through a few possible early PRNG algorithms, to see if I can work out whether this one was custom made, or an existing type, but none of the algorithms I've looked at match this one.

It's a reverseable 64-bit PRNG, but as the game only uses the lowest 33 bits of the output to calculate the gang, there are many different outputs that translate to the same gang type (2^31). My aim is to find the input from these with the most leading 0s (as this translates to the fewest characters to input, and most of the outputs reverse into input codes with more than the 10 characters that the game allows you to enter). Currently, I'm using brute force, reversing every one of the 2^31 possible outputs to find the inputs with the most leading 0s, but I wonder if this class of PRNG is sufficiently predictable to be able to rule out some and reduce the space of outputs to try reversing?

4 Comments
2023/07/10
12:16 UTC

2

Any xorshift browser or app

I need a browser app or an RNG app that does RNG calculation based on the older xorshift algorithm. Do you know any browser/app that can run on iOS? Would Chrome allow me to switch back to xorshift in the developer settings?

2 Comments
2023/07/08
01:15 UTC

4

The input variables of xoroshiro and xoroshift

What are the realtime input variables used in these random number generation algorithms? Time, cursor point, some calculations based on the previous number? I’d appreciate your help

Misspelling edit: xorshift :)

5 Comments
2023/07/08
01:06 UTC

7

Who can I contact with to get an opinion about my PRNG?

For last two yers I was working on some family of PRNGs. I just finished my paper on it. But no expert in the field has seen this generator.

Any idea who I can contact with to show my paper? I would like to check wether there are no factual errors. I know many experts, but they are neither retired or didn't write me back. Prof. Lemire, prof. Melissa O'Neil, prof. Vigna, Donald Knuth, Richard Brent, Pierre L'ecuyer - I have tried or ruled out trying with them (they didn't write back or are very old).

Or maybe I should just sent a paper to journal and the reviewer assesses the substantive value? What if it doesn't, what if it misses something?

10 Comments
2023/06/26
20:27 UTC

Back To Top