1
$\begingroup$

I discovered what appears to be a good quality pseudorandom number generator, but I have not subjected it to any statistical tests beyond bit frequency, bit pair frequency, and least-significant bit frequency tests. It generates a block of bytes by evolving deterministically, starting with a seed state. I'm new to Stack Exchange, so please bear with me.

Here is the process (test example):

start with a 32-byte sequence (256 bits) and an integer variable k, and for each byte X(i),

  1. $s = 7 - (X[i+1]+X[i+2]) \bmod 15$
  2. $X[i] = ((X[i] + k) * 2^s) \bmod 255$
  3. $k = k + X(i)$

and I implemented this process in C as follows:

    #define CYCLES 1 // full cycles per byte of the seed size per evolution
    unsigned int i, j;  
    unsigned char a, k;  
    int s;  
    for (i = 0; i < 32*CYCLES; i++) {  
        a = X[i%32]+k;  
        s = 7-(X[(i+1)%32]+X[(i+2)%32])%15;  
        for (j = 0; j < abs(s); j++) {  
            if (s<0) {  
                a = ((a&1)==1)?((a>>1)+128):(a>>1);  
            }  
            else {  
                a = ((a&128)==128)?((a<<1)+1):(a<<1);  
            }  
        }  
        X[i%32] = a;  
        k += a;  
    }  

The C implementation of modular multiplication by powers of uses bitwise operations and differs in only one way from an algebraic method: when a = 255, the output is always 255. This is essentially a rotation of the byte abs(s) times to the left when the sign is positive, and the right when it is negative.

If I initialize the array X with a seed value such as "ABCDEFGHIJKLMNOPQRSTUVWXYZ012345" and evolve it 32 times, then map out the resulting bits or do basic tests for randomness, it appears to be very similar to true randomness. Am I missing something, or is this a good PRN generator?

PNG map of output first 256 states after 32 initial steps

$\endgroup$
8
  • 1
    $\begingroup$ Unfortunately, We don't analyze those kinds of questions, here. If you want to test it use NIST tests and look for the next-but test. And the harder, prove that there is no distinguisher for it. $\endgroup$
    – kelalaka
    Feb 18 at 8:23
  • 2
    $\begingroup$ What is the output, the internal states? the key $k$ can become too large. $\endgroup$
    – kelalaka
    Feb 18 at 8:26
  • $\begingroup$ For the output, I took the binary value of all 32 bytes X in sequence, once at each subsequent stage of evolution. At any given time, the key is always a fixed size. What do you mean that it can become too large? You are right that I need to test it. I only hoped for help to see past myself, for any glaring problems. Thanks for replying. $\endgroup$ Feb 18 at 9:37
  • 1
    $\begingroup$ Look at RC4, that might enlighten you. Also if you output all stages, it should be a matter of time to determine the stage. and see nvlpubs.nist.gov/nistpubs/SpecialPublications/… $\endgroup$
    – kelalaka
    Feb 18 at 9:46
  • 1
    $\begingroup$ If you output X then I suppose you're not trying to generate a secure RNG? If so please see here. It would be more of a Computer Science topic. $\endgroup$
    – Maarten Bodewes
    Feb 18 at 12:25
-1
$\begingroup$

What could possibly be an advantage of your method from directly sampling the bytes from the prime number distribution?

Like:

Start at some integer $k$ and sample the 8 bits as: $k*30+\lbrace -13,-11,-7,-1,1,7,11,13\rbrace$, each time when it is a prime number, you set the bit at that position to 1, otherwise to 0. If your sampled Byte is $<= 64$ use k-= Byte, otherwise use k+= Byte for the next sample.

Isn't this much simpler than your method, or am I missing something of importance?

$\endgroup$
3
  • $\begingroup$ Is there a name for this method? $\endgroup$ Feb 19 at 7:29
  • $\begingroup$ I don't think so, you only need to know maybe that $2*3*5 = 30$ is the 3rd Primorial which then can be used like a basis, because there exist maximally 8 possible positions for prime numbers when using the 3rd primorial as a basis. Maybe you should simply investigate the prime numbers on your own, if you are interested in how and why all the generative models are possibly working, at theier lowest levels, before they get translated and reformulated in some mathematically higherlanguage and symbols. $\endgroup$
    – Eugen
    Feb 20 at 2:56
  • $\begingroup$ Try for example to draw the prime number positions, you will see a very familar image, just like the one you have posted above. $\endgroup$
    – Eugen
    Feb 20 at 2:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.