3
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ So XOR with left shift then reverse? So I guess for even $N$ at least, grouping the $k$th and $(N-1-k)$th bit into one, it's a linear cellular automaton on $A^{\mathbb{Z}_n}$ with alphabet $A = \mathbb{Z}^2_2$? $\endgroup$
    – Ville Salo
    Oct 4, 2020 at 8:40
  • $\begingroup$ In any case if it's late near over $\mathbb{Z}_2$ probably it's not very secure. $\endgroup$
    – Ville Salo
    Oct 4, 2020 at 8:43
  • 3
    $\begingroup$ This looks similar in idea to the S-boxes used in AES, DES and similar cryptosystems. (The details are more complicated but they typically apply a permutation of the input bits, then apply a fixed function to small blocks, and iterate these steps for a large number of rounds.) When they were developed, there was a lot of research into necessary and sufficient conditions for security. Maybe these translate into guarantees of good pseudo-random behaviour here? At least, that's where I would start looking. $\endgroup$ Oct 4, 2020 at 10:44
  • 1
    $\begingroup$ Another feature (if $N$ prime): the distribution of zero's in $B_n$ follows a Binomial distribution as expected, when computed on many many $B_n$'s. Also the correlation between the number of zero's in $B_n$ versus $B_{n+1}$ is rather close to zero ($0.06$ in one of my tests). And $X_n$ follows a uniform distribution on $[0, 1]$ when $N$ is large. $\endgroup$ Oct 4, 2020 at 15:46
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 7, 2020 at 10:38

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This can be done without arithmetic operations, just bit operations (except to get the first $N$ digits of the seed). The choice of $\sqrt{2}/2$ was the most basic example in $[0, 1]$. In practice you are going to choose a number impossible to guess, such as (say) $\frac{11}{41} \log 17 +$ $ \sin(73\sqrt{97})\cdot $ $\arctan(e^{53}) + $ $(\frac{111}{71})^{\pi\log 7} +$ $\zeta(\frac{9}{5})\cdot $ $\Gamma(\pi^{\log 5})+ $ $ 131\psi_0(2^{-\sin 3})$. $\endgroup$ Oct 7, 2020 at 1:07
  • 1
    $\begingroup$ @ Acacia: Good point about not using the first $N$ digits, but rather $N$ digits starting at a position $m$ with $m$ large. I updated my question accordingly, using the notation $M$ instead of $m$, see section 'possible improvements'. $\endgroup$ Oct 7, 2020 at 9:30
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I added the Perl directive in the code. The reason not to use $N>45$ is because of machine precision resulting in digits of the seed $X_0$ being wrong beyond that, but that's easy to change. Also if the period is lager than Niter, the Perl script won't be able to identify the period and return it as -1: you need to increase Niter accordingly. Note that it is not the seed that is prime, but the number of bits $N$. The seeds need to be random enough, thus the choice of the first $N$ digits of $\sqrt{2}/2$ for the seed. $\endgroup$ Oct 5, 2020 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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