Question about a new pseudo-random number generator

Question

While investigating non-periodic RNG's (random number generators) for irrational numbers, I came up with a version that actually produces pseudo-random words consisting of $N$ bits, where $N$ is typically a large prime number. Here I explain my RNG. My question is whether it suffers from the same problems as Xorshift RNG's or some other problems. As a starter, the version corresponding to $N=32$ is terrible: its period is $24$. But $N=31$ yields a good generator with a long period and nice statistical properties. In its basic version, it is defined as follows.

Start with a seed $S$. The first random word $B_0$ is $S$. In my case, I picked up the first $N$ binary digits of $\sqrt{2}/2$ for the seed.The $k$-th bit of $B_n$ is denoted as $B_n(k)$. Then $B_{n+1}$ is obtained recursively as follows.

• Shifting step: Create the word $C_{n}$ by shifting the bits of $B_{n}$ by $L$ positions as follows: the $k$-th bit of $C_n$ is equal to $C_n(k)=B_n(\bmod(k+L,N))$ for $k=0,\cdots, N-1$.
• Scrambling step: $B_{n+1}(k)=\bmod(B_{n}(N-k-1)+C_{n}(k),2)$ for $k=0,\cdots, N-1$. In other words, $B_{n+1}(k)=\mbox{ XOR}(B_{n}(N-k-1),C_{n}(k))$. Thus the analogy with Xorshift generators.

$L=2$ seems to work best in most cases. For $L=2$ and $N=7, 11$ or $17$, the period is $2^{N-3}-1$. More generally, if $N$ is prime, the period is of the order $2^N$. Of course, there is no way the period could be higher than $2^N$. So prime values of $N$ produce the best generators, though this might not be true for all primes.

Also, the real number $X_n\in [0,1]$ is defined as follows:

$$X_n=\sum_{k=1}^{N} \frac{B_{n}(k-1)}{2^k}.$$

There is a one-to-one mapping between $B_n$ and $X_n$. I studied the patterns in the distribution of successive values of $X_n$ and haven't found any. For instance, unlike other RNG's (see here and follow-up discussion here), the triplets $(X_n,X_{n+1},X_{n+2})$ do not appear to lie in a small number of parallel planes. Successive values of $X_n$ are asymptotically un-correlated. For modern tests (George Marsaglia, 2020) to assess the quality of a RNG, see here and here.

The underlying idea in the design of my generator is this: take a seed consisting of a large number of random bits, such as a the first $N$ binary digits of a normal number in base $2$. Then if you reverse these bits (the binary digits), the new number is a sequence of bits just as random as the previous one, and uncorrelated to the previous number.

Possible improvements

Consider a $q$-order recursion $B_{n}=f(B_{n-1},\cdots,B_{n-q})$ instead of a first-order one as here. Then the period can be of the order $2^{Nq}$. Such an example for a Xorshift generator is provided here by G. Marsaglia, with $q=4$. It uses four seeds. In our case, if we were to use $q$ seeds, you can pick up $q$ irrational numbers that are linearly independent over the set of rational numbers. Their digits sequences are independent from each other (see section 1.3 in this article for a proof). An example (with $q=4$) is the first $N$ binary digits of the following numbers: $\log 2, \frac{\pi}{4}, \frac{\sqrt{2}}{2}$ and $\exp(-\frac{3}{5})$.

Of course, instead of choosing $\sqrt{2}/2$, one might choose an irrational number impossible to guess, for instance $$\alpha=\zeta(\sqrt{31}\log 5)\cdot\Gamma(e^{73 \sin 7})+\psi_2\Big(5e^{-11\cos 19}\log(53\pi+\sin 101)\Big)$$ Further improvement is obtained by using $N$ digits of $\alpha$ or $\sqrt{2}/2$ starting at position $M$ in their binary expansion, with $M$ very large and kept secret, rather than $M=0$ as in the code below. If you work with $q$ seeds, choose a different $M$ for each seed.

Source code

It also computes the period. If the period is larger than Niter (in the code) it will return $-1$ for the period: you need to increase Niter accordingly. Use for values of $N$ smaller than 45; to eliminate this problem, get the digits of the seed from a table or use a tool such as this one to get millions of digits for the seed.

#!/usr/bin/perl
$N=31;  

$L=2;
$period=-1;
$Niter=50000;

%hash=();

$seed=sqrt(2)/2;

open(OUT,">randx.txt");
print OUT "0\tB";
$x=0;
$word="B";
$s=$seed;
for ($k=0; $k<$N; $k++) {
  $a[$k]=int(2*$s);  # k-th digit of seed
  $s=2*$s-int(2*$s);  
  $b[$k]=$a[$k];
  $x+=$b[$k]/(2**($k+1));
  $word=$word."$b[$k]";
  $hash{$word}=0;
  print OUT "$b[$k]";
}
print OUT "\t$x\n";

for ($iter=1; $iter<$Niter; $iter++) {
  print OUT "$iter\tB";
  $x=0;
  for ($k=0; $k<$N; $k++) { 
    $c[$k]=$b[($k+$L)%$N]; 
  }
  $word2="B";
  $nzero=0;
  for ($k=0; $k<$N; $k++) { 
    $b[$k]=($c[$k]+$b[$N-$k-1])%2;
    $word2=$word2."$b[$k]";
    $x+=$b[$k]/(2**($k+1));
    print OUT "$b[$k]";
  }
  print OUT "\t$x\n";
  if ($period==-1) { 
    if ($hash{$word2} eq "") { 
      $hash{$word2}=$iter; 
    } else {
      $period=$iter-$hash{$word2};
    }
  }
}
close(OUT);
print "$N $L $period\n";

Note

Obviously, one flaw of all RNG's with $q=1$ (first-order recurrence) is that you never see twice the same word within any period cycle. In true randomness, repetition occurs without causing the cycle to repeat itself entirely. As an example, if you pick up 10 integers randomly between $0$ and $3$, some number MUST appear at least twice.

Answer 1

Floating point division varies across platforms especially if the language and the system supports hardware accelerated floating point arithmetic. It is risky to use it in an encryption algorithm standard. You can find a better more secure method if you use a fixed size seed starting at digit m of square root of 2 over 2. The division by 2 is redundant. This is equivalent to 1/(square root of 2). I am pretty sure that this is still irrational but I also think perl will implement these irrational constants differently than some other language. You are giving away too much by using the first N digits of a known irrational constant as part of the standard. It would be harder to attack if you offset true random m digits before sampling the decimal expansion of the irrational. It would be even better to use a hardware TRNG. After that you need to cast the sequence as raw binary data or signed int to eliminate unknown errors resulting from cross platform implementation. I have python libraries that allow very big integers without truncation. If you prefer performance then you are probably working with binary in C.

Answer 2

Please put #!/usr/bin/perl in your source code at the top. I wasted a lot of time trying to figure what you wrote. The last time I had to work on perl code was 23 years ago. It was not obvious to me without the required standard perl syntax that you are deviating from. There was a standards organization deciding this a long time ago to avoid any confusion.

Also, big prime number N needs an encoding scheme that adds salt and puts it in a fixed width binary data type 2^n bits in length. Variable width seeds are easier to attack. There needs to be a user configurable upper limit to N or it can be Nmod(x) if some specific conditions are true. I need to look more at this before I have a clear answer on small seeds from big primes. Cycles are not bad if they are sufficiently large. You are strictly using prime seeds but you can tweak it to use numbers that are or are not coprime with the algorithm itself. That opens up many more ways to implement it where machine speed or storage is limited.