https://doi.org/10.31449/inf.v45i2.3109 Informatica 45 (2021) 179–189 179
A Full Cycle Length Pseudorandom Number Generator Based on
Compositions of Automata
Pál Dömösi
Institute of Mathematics and Informatics, University of Nyíregyháza, H-4400 Nyíregyháza, Sóstói út 31/B, Hungary
Faculty of Informatics, University of Debrecen, H-4028 Debrecen, Kassai út 26, Hungary
E-mail: domosi@unideb.hu, domosi.pal@nye.hu
József Gáll and Géza Horváth
Faculty of Informatics, University of Debrecen, H-4028 Debrecen, Kassai út 26, Hungary
E-mail: gall.jozsef@inf.unideb.hu, horvath.geza@inf.unideb.hu
Bertalan Borsos
Faculty of Informatics, Eötvös Loránd University, H-1117 Budapest, Pázmány Péter sétány 1/C, Hungary
E-mail: bertalanborsos@gmail.com
Norbert Tihanyi
Digital14 LLC, xen1thLabs, Cryptography Laboratory, Abu Dhabi, United Arab Emirates
E-mail: norbert.tihanyi@digital14.com
Yousef Al Hammadi
College of Information Technology, United Arab Emirates University
P.O. Box 15551, Al Ain, Abu Dhabi, United Arab Emirates
E-mail: yousef-A@uaeu.ac.ae
Keywords: automata network, NIST test, block cipher, pseudo random number generator, composition of automata,
Gluškov product of automata, temporal product of automata
Received: April 3, 2020
In this paper a new Pseudorandom Number Generator based on compositions of abstract automata is pre-
sented. We show that it has full cycle with length of 2
128
. It is also shown that the output satisﬁes the
statistical requirements of the NIST randomness test suite.
Povzetek: V prispevku je predstavljen nov psevdonakljuˇ cni generator števil.
1 Introduction
In this paper, the authors continue their joint research of
cryptographic tools based on compositions of abstract ﬁnite
automata started in [6].
Random number generators have been used for a wide
variety of ﬁelds and purposes, such as cryptography, pat-
tern recognition, gambling and VLSI testing. [18]. In this
paper a Pseudorandom Number Generator (PRNG) based
on automata theory will be introduced and studied. The
most frequent type of automata theory based pseudoran-
dom generators are implemented on the basis of cellular
automata. The ﬁrst pseudorandom number generator based
on cellular automata was proposed by S. Wolfram [29, 30]
and there are many pseudorandom generators based on cel-
lular automata today. (See [2]-[5], [8]-[16], [19, 20],[23]-
[28]).
A common problem of some well-known pseudorandom
generators based on cellular automata is that they have se-
rious application difﬁculties: some of them can be broken
[1],[17], while in case of others the selection of the key
automaton poses difﬁculties [10].
These reasons, among others, justify the use of new
automata theory-based pseudorandom number generators
based on principles other than cellular automata.
Counter-based random number generation [22] is a rel-
atively new technique for creating a pseudorandom num-
ber generator using only an integer counter as the inter-
nal state of the generator. The state transition function is
an increment by one modulo the size n of the ﬁnite state
set S = f0;:::;n  1g and the complexity comes in
the map from the state to the random sample. Formally,
a counter based random number generator (CBRNG) is a
structureCBRNG = (K;Z
J
;S;f;U;g), where K is the
key space; Z
J
=f0; 1;:::;J  1g, where J is a positive
integer called output multiplicity; S is the state space; U
is the output space; f : S ! S is the state transition
function, s
i
= f(s
i  1
); g : K  Z
J
  S ! U is the
output function. If Z
J
is a singleton (i.e., Z
J
= f0g)
then we will write g in the form g : K  S ! U and
then we say thatCBRNG has a simple output multiplic-
ity. Given an output function g : K  S! U having a
simple output multiplicity and assume that U   S. We
180 Informatica 45 (2021) 179–189 P. Dömösi et al.
say that the output function g
0
: K  S ! U is a dou-
ble round of the output function g : K  S ! U if for
every k 2 K;s 2 S; g
0
(k;s) = g(k;g(k;s)). In gen-
eral, we say thatg
0
: K  S! U is ak-times round of
g :K  S!U for somek> 2 if for everyk2K;s2S;
g
0
(k;s) = g(k;h(k;s)) such thath : K  S is ak  1-
times round of g : K  S. Finally, the single round of
g :K  S!U is the functiong :K  S!U itself.
TheCBRNG = (K;Z
J
;S;f;U;g) works in discrete
time scale. It starts from a ﬁxed states2 S, called initial
state and a ﬁxed keyk2 K. Then the generated random
number sequence isg(k; 0;f
1
(s));:::;g(k;J  1;f
1
(s));
g(k; 0;f
2
(s));:::;g(k;J   1;f
2
(s));g(k; 0;f
n
(s));
;:::;g(k;J  1;f
n
(s)), where f
1
(s) = f(s);f
2
(s) =
f(f(s)) andf
n
(s) =f(f
n  1
(s)) for every furthern> 2.
In this case, the vector (g(k; 0;f(s));:::g(k;J  1;f(s))
is called the output vector of initial state.
Given aCBRNG = (K;Z
J
;S;f;U;g) we say that its
state transition function f : S ! S has a full cycle if
for every s 2 S;S = ff
n
(s)jn = 1;:::;jSjg, where,
by deﬁnition,jSj denotes the cardinality ofS. Moreover, a
CBRNG is said to have a full cycle or full period if for any
key and initial state s2 S, theCBRNG traverses every
output vector (u
0
;:::;u
J  1
)2U
J
before returning to the
output vector of the initial state.
The following statement is clear.
Proposition 1 A CBRNG = (K;Z
J
;S;f;U;g)
has a full cycle if and only if its state transition function
f : S! S has a full cycle and for every keyk2 K, the
functiong
k
:S!U
J
withg
k
(s) = (g(k; 0;s);:::;g(J  1;s));s2S is bijective.
In this paper we consider CBRNGs having a simple out-
put multiplicity. For CBRNGs,g is complex,f is a simple
counter withf(s) = (s + 1)mod 2
p
, wherep is the state
size in bits and S =f0;:::;p  1g. Applying the ideas
of this construction, in this paper we consider CBRNGs,
where f is a counter, and g is deﬁned by composition of
abstract ﬁnite automata.
2 Preliminaries
We start with some standard concepts and notation. For
all notions and notation not deﬁned here we refer to the
monograph [7]. By an automaton we mean a deterministic
ﬁnite automaton without outputs. In more detail, an au-
tomaton is an algebraic structureA = (A;   ;  ) consisting
of the nonempty and ﬁnite state setA, the nonempty and
ﬁnite input set   , and a transition function  :A    !A:
The transition matrix of an automaton is a matrix with rows
corresponding to each input and columns corresponding to
each state; at the entry of any row indicated by an input
x2   sign and any column indicated by a statea2A the
state  (a;x) is put. If all rows of the transition matrix are
permutations of the state set then we speak about permuta-
tion automaton.
A Latin square of order n is an n  n matrix (with n
rows andn columns) in which the elements of ann-state set
fa
0
;a
1
;:::;a
n  1
g are entered so that each element occurs
exactly once in each ﬁxed (row, column) pair.
In this paper we will consider special compositions of
automata consisting of component automata such that all
components have the same transition matrix of the Latin
square form. We will show that these compositions of au-
tomata are permutation automata, moreover for every state
of these automata compositions it has a very low likeli-
hood that two randomly chosen distinct input signs take
the automaton into the same state. By these properties, we
would like to avoid vulnerability to statistical attacks. Fi-
nally we note that, apart from the trivial cases, the transition
matrices of the considered automata compositions are not
quadratic. Therefore, their transition matrix can not form
Latin squares.
3 Construction
We start with some standard deﬁnitions. (See, for example
[6, 7]).
Let A
i
= (A
i
;   i
;  i
) be automata where i 2
f1;:::;ng; n   1: Take a ﬁnite nonvoid set   and a
feedback function ’
i
: A
1
      A
n
    !   i
for every i 2 f1;:::;ng: A Gluškov-type product of
the automataA
i
with respect to the feedback functions
’
i
(i2f1;:::;ng) is deﬁned to be the automatonA =
A
1
     A
n
(  ; (’
1
;:::;’
n
)) with state set A =
A
1
      A
n
; input set   ; transition function   given
by   ((a
1
;:::;a
n
);x) = (  1
(a
1
;’
1
(a
1
;:::;a
n
;x));:::;
  n
(a
n
;’
n
(a
1
;:::;a
n
;x))) for all (a
1
;:::;a
n
)2 A and
x2   : In particular, ifA
1
=::: =A
n
then we say thatA
is a Gluškov-type power.
Given a functionf : X
1
      X
n
! Y; we say that
f is really independent of its i-th variable if for every
pair (x
1
;:::;x
n
); (x
1
;:::;x
i  1
;x
0
i
;x
i+1
;:::;x
n
)
2 X
1
        X
n
; f(x
1
;:::;x
n
) =
f(x
1
;:::;x
i  1
;x
0
i
;x
i+1
;:::;x
n
): Otherwise we say
that f really depends on its i-th variable. A (ﬁnite)
directed graph (or, in short, a digraph) D = (V;E)
(of order n > 0) is a pair consisting of sets of vertices
V =fv
1
;:::;v
n
g and edges E   V   V: Elements of
V are sometimes called nodes. IfjVj = n then we also
say thatD is a digraph of order n:D is called bipartite
if its vertices can be partioned into two sets A;B such
that every (direct) edge connects a vertex inA to a vertex
in B or vica versa. Further on, we will assume that V
is an ordered set of integers 1;:::n for some positive
integer n: Given a digraphD = (V;E), we say that
the above deﬁned Gluškov product is aD-product if for
every pair i;j 2f1;:::;ng; (i;j) = 2 E implies that the
feedback function ’
i
is really independent of its j-th
variable. Let   be the set of all‘ (preferably 4 or 8) length
binary strings for a given length ‘ > 0. Moreover, let
A
i
= (  ;   ;  Ai
);i = 2;:::;n be copies ofA
1
, and letn
be a positive integer power of 2. Consider the following
A Full Cycle Length Pseudorandom Number. . . Informatica 45 (2021) 179–189 181
simple bipartite digraphs:
D
1
= (f1;:::;ng;f(n=2 + 1; 1); (n=2 +
2; 2);:::; (n;n=2)g),
D
2
= (f1;:::;ng;f(n=4 + 1; 1); (n=4 +
2; 2);:::; (n=2;n=4);
(3n=4+1;n=2+1); (3n=4+2;n=2+2);:::; (n; 3n=4)g),
:::,
D
log
2
n  1
= (f1;:::;ng;f(3; 1); (4; 2); (7; 5); (8; 6);:::;
(n  1;n  3); (n;n  2)g),
D
log
2
n
= (f1;:::;ng;f(2; 1); (4; 3);:::; (n;n  1)g);
D
log
2
n+1
=D
1
.
For every digraph D = (V;E) with D 2
fD
1
;:::;D
log
2
n
g, let us deﬁne the Gluškov-type
power, called two-phaseD-power,A
D
= A
1
      A
n
( 
n
; (’
1
;:::;’
n
)) ofA
1
(withA
1
=A
2
::: =A
n
)
so that for every (a
1
;:::;a
n
); (x
1
;:::;x
n
) 2
  n
; (i;j) 2 E, ’
i
(a
1
;:::;a
n
; (x
1
;:::;x
n
)) =
a
0
j
  x
j
; and ’
j
(a
1
;:::;a
n
; (x
1
;:::;x
n
)) =
a
i
  x
i
, where a
i
  x
i
is the bitwise addition mod-
ulo 2 of a
i
and x
i
, a
0
j
denotes the state into which
’
j
(a
1
;:::;a
n
; (x
1
;:::;x
n
)) takes the automatonA
i
from
its statea
j
; anda
0
j
  x
j
is the bitwise addition modulo 2
ofa
0
j
andx
j
.
1
Next we deﬁne the concept of temporal product of
automata. Let A
t
= (A;   t
;  t
);t = 1; 2 be
automata having a common state set A: Take a ﬁ-
nite nonvoid set   and a mapping ’ of   into
  1
    2
: Then the automatonA = (A;   ;  ) is a temporal
product (t-product) ofA
1
byA
2
with respect to   and’
if for anya2 A andx2   ;  (a;x) =   2
(  1
(a;x
1
);x
2
);
where (x
1
;x
2
) = ’(x): The concept of temporal product
is generalized in the natural way to an arbitrary ﬁnite fam-
ily ofn> 0 automataA
t
(t = 1;:::;n), all with the same
state setA.
Proposition 2 Suppose thatA
1
= (  ;   ;  ) is a permu-
tation automaton. Then for every i = 1;:::; log
2
n, the
D
i
-power ofA
1
also forms a permutation automaton.
Proof. Assume thatA
1
is a permutation automaton. Then,
by deﬁnition, all rows of its transition matrix are permuta-
tions of the state set. Therefore, none of these rows contain
repetition. Consequently, for any statesa;b2A
1
and input
x2   ;  1
(a;x) =  1
(b;x) impliesa =b.
By our above observation, if the D
i
-power A
Di
=
( 
n
;   n
;  Di
) is a permutation automaton, then for every
pair of states (a
1
;:::;a
n
); (b
1
;:::;b
n
) and input sign
(x
1
;:::;x
n
), we have   Di
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) =
  Di
((b
1
;:::;b
n
); (x
1
;:::;x
n
)) that implies
(a
1
;:::;a
n
) = (b
1
;:::;b
n
).
Suppose that A
Di
is not a permutation automaton.
Then, by our observations, there are a pair of dis-
tinct states (a
1
;:::;a
n
); (b
1
;:::;b
n
) and an input sign
(x
1
;:::;x
n
) for which  Di
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) =
  Di
((b
1
;:::;b
n
); (x
1
;:::;x
n
).
1
We remark that there areV
1
;V
2
  V withV = V
1
[V
2
andV
1
\
V
2
=; so that for everyj2 V
2
there exists exactly onei2 V
1
with
(j;i)2E. Therefore all the functions’
1
;:::;’n are well-deﬁned.
If (a
1
;:::;a
n
) and (b
1
;:::;b
n
) are distinct then there
exists an index j 2 f1;:::;ng with a
j
6= b
j
.
Put (a
0
1
;:::;a
0
n
) =   Di
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) and
(b
0
1
;:::;b
0
n
) =   Di
((b
1
;:::;b
n
); (x
1
;:::;x
n
)). It is
enough to show that, in this case, (a
0
1
;:::;a
0
n
) 6=
(b
0
1
;:::;b
0
n
).
LetE denote the set of edges inD
i
.
First we suppose (j;k)2 E for somek2f1;:::;ngn
fjg. Then, by deﬁnition, a
0
j
=   A1
(a
j
;a
0
k
  x
k
) and
b
0
j
=   A1
(b
j
;b
0
k
  x
k
). BecauseA
1
is a permutation au-
tomaton, by the assumption a
0
k
= b
0
k
, we get a
j
= b
j
, a
contradiction. Thereforea
0
k
6= b
0
k
. Hence, (a
0
1
;:::;a
0
n
)6=
(b
0
1
;:::;b
0
n
).
Next we assume (k;j)2 E for somej2f1;:::;ngn
fkg. Obviously, by a
0
j
6= b
0
j
we have (a
0
1
;:::;a
0
n
) 6=
(b
0
1
;:::;b
0
n
) and then we are done once again. There-
fore, suppose a
0
j
= b
0
j
. Then, again by deﬁnition, a
0
j
=
  A1
(a
j
;a
k
  x
k
) andb
0
j
=  A1
(b
j
;b
k
  x
k
). BecauseA
1
is a permutation automaton anda
k
6= b
k
,a
0
j
= b
0
j
is pos-
sible only ifa
j
= b
j
, a contradiction. Therefore,a
0
j
6= b
0
j
and thus we obtain (a
0
1
;:::;a
0
n
)6= (b
0
1
;:::;b
0
n
). The proof
is complete. QED
Now we give an alternative proof of Lemma 2 in [6].
Proposition 3 Temporal products of permutation au-
tomata are also permutation automata.
Proof. Obviously, it is enough to prove our statement for
temporal products of two components. Thus, letM =
(M;   ;  M
) be a temporal product of permutation au-
tomataM
1
= (M;   1
;  M1
) andM
2
= (M;   2
;  M2
)
(having the same state set) with respect to   and ’ :
  !   1
    2
. Let m
1
;m
2
2 M be distinct states and
x 2   be an arbitrary input sign ofM. Moreover, let
’(x) = (x
1
;x
2
) for somex
1
2   1
andx
2
2   2
. Then for
every distinct pair m
1
;m
2
2 M of states and x
1
2   1
we have   M1
(m
1
;x
1
) 6=   M2
(m
2
;x
2
). On the other
hand,M
2
is also a permutation automaton. Therefore, be-
cause of  M1
(m
1
;x)6=   M2
(m
2
;x), for everyx
2
2   2
,
  M1
(  M1
(m
1
;x
1
);x
2
)6=   M2
(  M2
(m
2
;x
1
);x
2
). Thus,
using’(x) = (x
1
;x
2
);  M
(m
1
;x)6=  M
(m
2
;x). In other
words, for every distinct pair m
1
;m
2
2 M of states and
input signx2   ;  M
(m
1
;x)6=   M
(m
2
;x). But then all
rows of the transition matrix ofM are permutations of the
state set. This completes the proof. QED
LetB = ( 
n
; ( 
n
)
log
2
n
;  B
) be the temporal prod-
uct ofA
D1
;:::;A
D
log
2
n
with respect to ( 
n
)
log
2
n
and
the identity map ’ : ( 
n
)
log
2
n
! ( 
n
)
log
2
n
, where
A
Di
;i = 1;:::; log
2
n is aD
i
- power of the automaton
A
1
= (  ;   ;  A1
).
From now on we assume thatA
1
is a permutation au-
tomaton having  A1
(a;x)6=  A1
(a;x
0
) for everya;x;x
0
2
  ;x6= x
0
, and we say thatB is a key-automaton with re-
spect to the permutation automatonA
1
called the basic au-
tomaton ofB.
2
Theorem 1 in [6] concerns key automata consisting of
basic automata having a transition table forming a Latin
2
Recall thatn should be a positive integer power of 2.
182 Informatica 45 (2021) 179–189 P. Dömösi et al.
cube. The next statement is formally the same but, of
course, it concerns key automata consisting of basic au-
tomata having a transition table forming a Latin square. By
this fact, the next statement could also be derived from The-
orem [6] using some simpliﬁcation regarding its proof.
We note that the following statement is formally the
same as Theorem 1 [6] which is concerning key automata
consisting of basic automata having a little bit different
structure as basic automata of the present paper. (The tran-
sition table of basic automata in [6] forms a Latin cube
while the transition table of basic automata of the present
paper forms a Latin square.) This fact implies that the
automata compositions discussed in the present paper are
more or less similar to the ones in [6].
For the sake of simplicity, we give a direct proof of the
next statement which, using some simpliﬁcations, can also
be derived from the proof of Theorem 1 in [6] .
Theorem 4 Every key automaton is a permutation automa-
ton.
Proof. Consider a key automaton B =
( 
n
; ( 
n
)
log
2
n
;  B
) and its basic automaton
A
1
= (A
1
;   1
;  1). By the deﬁnition of key automaton,
A
1
is a permutation automaton.
Therefore, using Proposition 2, for every permutation
automatonA
1
and i = 1; 2;:::; log
2
n; theD
i
-power
A
Di
=A
1
     A
n
( 
n
; (’
1
;:::;’
n
)) ofA
1
is a per-
mutation automaton.
Recall that B is a temporal product of
A
D1
;:::;A
D
log
2
n
. Therefore, by Proposition 3, our
proof is done. QED
Proposition 5 Suppose that the transition matrix of an
automatonA
1
= (  ;   ;  ) forms a Latin square. Then for
every i = 1;:::; log
2
n, the transition matrix of theD
i
-
power ofA
1
also forms a Latin square.
Proof. Obviously, if the transition matrix of an automaton
A
i
= (Ai;   ;  ) forms a Latin square thenA is a permu-
tation automaton. But then, by Proposition 2, all ofD
i
-
powers are permutation automata. In other words, the rows
of their transition matrices form a permutation of their state
set. All that is left is to show that the columns of their tran-
sition matrices also have this property.
Consider a D
i
-power A
Di
= ( 
n
;   n
;  Di
) of A
1
having A
Di
= A
1
        A
n
( 
n
; (’
1
;:::;’
n
))
for some i = 1; 2;:::; log
2
n. We should
prove that for every state (a
1
;:::;a
n
) 2   n
and distinct words (x
1
;:::;x
n
); (y
1
;:::;y
n
) 2
  n
,   Di
((a
1
;:::;a
n
); (x
1
;:::;x
n
))
6=   Di
((a
1
;:::;a
n
); (y
1
;:::;y
n
)). Let j 2 f1;:::;ng
be an index with x
j
6= y
j
. Moreover, let E
be the set of edges in D
i
and let us assume that
(i;j) 2 E (with i 2 f1;:::;ng n fjg). Then
x
i
6= y
i
implies   (a
j
;a
i
  x
i
) 6=   (a
j
;a
i
  y
i
).
Therefore, by our construction, the j-th com-
ponents of   Di
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) and
  Di
((a
1
;:::;a
n
); (y
1
;:::;y
n
)) are distinct as we stated.
Now we assume (i;j)2 E (with i2f1;:::;ngnfjg).
If   (a
i
;a
j
  x
j
) 6=   (a
i
;a
j
  y
j
) then the i-th
components of   Di
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) and
  Di
((a
1
;:::;a
n
); (y
1
;:::;y
n
)) are distinct again. There-
fore, let   (a
i
;a
j
  x
j
) =   (a
i
;a
j
  y
j
). But then, by
x
i
6=y
i
; we receive  (a
i
;a
j
  x
j
)  x
i
6=  (a
i
;a
j
  y
j
)  y
i
.
Obviously, this leads to   (a
j
;  (a
i
;a
j
  x
j
)  x
i
) 6=
  (a
j
;  (a
i
;a
j
  y
j
)  y
i
). Thus we get again that the
j-th component of   Di
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) and
  Di
((a
1
;:::;a
n
); (y
1
;:::;y
n
)) are distinct. This ﬁnishes
the proof. QED
Obviously, if the automatonA
1
has a transition table
forming a Latin square then it is a permutation automaton.
Therefore, it can be a basic automaton of an appropriate
key automaton.
Observation 6 Consider a key automatonB for which its
basic automatonA
1
has a transition table forming a Latin
square. Then for every state a ofB, the probability that
its two random signs takeB froma into the same state is
((2j  j  1)=j  j
3
)
n=2
, where   is the set of states ofA
1
and
n is the number of (identical) component automata in each
D
i
power (i = 1;:::; log
2
n) for whichB is a temporal
product of theseD
i
powers.
Proof. Denote byM = ( 
n
; ( 
n
)
log
2
n  1
;  M
) the
temporal product consisting of the ﬁrst log
2
n  1 com-
ponentsA
Di
;i = 1;:::; log
2
n  1 of the key automaton
B = ( 
n
; ( 
n
)
log
2
n
;  B
) and consider the log
2
n-th com-
ponentA
D
log
2
n
= ( 
n
;   n
;  D
log
2
n
) ofB. By Proposition
2 and Proposition 3,M is a permutation automaton. There-
fore, for every state (a
1
;:::;a
n
)2   n
ofM its random
input signsw2 ( 
n
)
log
2
n  1
takeM into each state with
the same probabbiliy 1=j  n
j.
Consider a ﬁxed state (c
1
;:::;c
n
) 2   n
and a ran-
domly chosen pair w
1
;w
2
2 ( 
n
)
log
2
n  1
ofM and de-
note by (a
1
;:::;a
n
); (a
1
;:::;a
n
)2 M the pair of states
inM such that  M
((c
1
;:::;c
n
);w
1
) = (a
1
;:::;a
n
) and
  M
((c
1
;:::;c
n
);w
2
) = (a
1
;:::;a
n
).
Moreover consider a randomly chosen pair
(x
1
;:::;x
n
); (y
1
;:::;y
n
)2   n
of input signs ofA
D
log
2
n
,
and assume that   D
log
2
n
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) =
  D
log
2
n
(b
1
;:::;b
n
); (y
1
;:::;y
n
)). For everyi = 1;:::;n,
there exists a single i 2 f1;:::;ng such that either
(i;j) 2 E or (j;i) 2 E, where E denotes the set of
edges in the digraphD
log
2
n
. There are the following
cases. If (i;j) 2 E then   (a
i
;  (a
j
;a
i
  x
i
)  x
j
)
and   (b
i
;  (b
j
;b
i
  y
i
)   y
j
)) will be the i-th and
  (a
j
;a
i
  x
i
) and   (b
j
;b
i
  y
i
) will be the j-th
component of   D
log
2
n
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) and
  D
log
2
n
(b
1
;:::;b
n
); (y
1
;:::;y
n
)), respectively. By the
assumption   D
log
2
n
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) =
  D
log
2
n
(b
1
;:::;b
n
); (y
1
;:::;y
n
)), we have
  (a
i
;  (a
j
;a
i
  x
i
)  x
j
) =   (b
i
;  (b
j
;b
i
  y
i
)  y
j
)
and   (a
j
;a
i
  x
i
) =   (b
j
;b
i
  y
i
) By the sec-
ond equality, we can write the ﬁrst one in the form
  (a
i
;  (a
j
;a
i
  x
i
)  x
j
) =   (b
i
;  (a
j
;a
i
  x
i
)  y
j
).
Recall that the transition matrix of A
1
forms a Latin
square. Therefore, by these considered equalities,a
i
= b
i
if and only ifx
j
=y
j
anda
j
=b
j
if and only ifx
i
=y
i
.
On the other hand, for everyk = 1;:::;n, there arej  j
2
A Full Cycle Length Pseudorandom Number. . . Informatica 45 (2021) 179–189 183
cases havinga
k
=b
k
andx
k
=y
k
,a
k
;b
k
;x
k
;y
k
2   . Of
course, all of these cases take thei-th andj-th components
ofA
D
log
2
n
into the same state.
In addition, every element of   appears exactlyj  j-
times in the transition table ofA
1
because it forms a Latin
square. Moreover, we can consider only nonequal pairs of
quadruplets.
Hence there arej  j(j  j  1) number of quadruple possi-
bilitiesa
i
;b
i
;x
i
;y
i
2   ;i = 1;:::;n havinga
i
6=b
i
;x
i
6=
y
i
taking thei-th andj-th components ofA
D
log
2
n
into the
same state.
In sum, we have that the probability that   (a;x) and
  (b;y) coincide for a random quadruple a;b;x;y2   is
(2j  j
2
 j   j)=j  j
4
= (2j  j  1)=j  j
3
.
By our constructions, the digraphD
log
2
n
hasn=2 edges.
Consequently, the probability that a random quadruple
(a
1
;:::;a
n
); (b
1
;:::;b
n
); (x
1
;:::;x
n
); (y
1
;:::;y
n
) 2
  n
has the property  D
log
2
n
((a
1
;:::;a
n
); (x
1
;:::;x
n
)) =
  D
log
2
n
(b
1
;:::;b
n
); (y
1
;:::;y
n
)) is ((2j  j  1)=j  j
3
)
n=2
.
We remark that if we have an implementation withj  j =
256 andn = 16 then the considered probability is ((512  1)=256
3
)
8
  1=2
120
.
By our investigations, we receive that the probabil-
ity of the equality   B
((c
1
;:::;c
n
);w
1
(x
1
;:::;x
n
)) =
  B
((c
1
;:::;c
n
);w
2
(y
1
;:::;x
n
)) is ((2j  j  1)=j  j
3
)
n=2
,
whenever w
1
(x
1
;:::;x
n
) and w
2
(y
1
;:::;x
n
) are ran-
domly chosen input signs ofB. QED
Theorem 7 Every key automaton transition function can
be applied as an output function of a counter-based pseudo
random number generator.
Proof. As the proof of our statement, we give a con-
struction of an appropriate counter based PRNG (CBRNG)
CBRNG = (K;Z
J
;S;f;U;g) having this property. First
of all, consider a counter which realizes the state function
asf(n) = n + 1modm, wherem is a sufﬁciently large
positive integer (preferably m = 2
128
), and n is given
as a ﬁxed-length binary number (preferably with 128-bit
length). For sake of simplicity, assume thatCBRNG has a
simple output multiplicity, i.e., letZ
J
=f0g be a single-
ton (although it may have more than one element). Thus
the state space is S =f0;:::;m  1g. The elements of
S may be considered binary strings of ﬁxed length. There-
fore, we may assume thatS coincides with the state set   n
of the key automaton. We assumeK  S  ( 
n
)
2log
2
n
,
whereS =   n
is the state set, and ( 
n
)
2log
2
n
is the in-
put set of the key automatonB = ( 
n
; ( 
n
)
log
2
n
;  B
).
The ﬁrst component of the elements of K are consid-
ered as possible seeds of the random number generator
and the second one is an input element ofB. The output
spaceU and the state spaceS coincide. The output func-
tion g : K  S ! U is given as g(k; (a
1
;:::;a
n
)) =
b
1
jjb
2
jj:::jjb
n
;k2 K; (a
1
;:::;a
n
)2 S(=   n
), where
b
1
jjb
2
jj:::jjb
n
is the concatenation of b
1
;:::;b
n
as bi-
nary strings and (b
1
;:::;b
n
) is a state of the key automa-
tonB with (b
1
;:::;b
n
) =  B
((a
1
;:::;a
n
); (x
1
;:::;x
n
)),
where the concatenation a
1
jj:::jja
n
of a
1
;:::;a
n
as bi-
nary strings is given bya
1
jj:::jja
n
=s+kmodm, where
s +kmodm is thek-th state of the state spaceS starting
from the state s, s2 S is the ﬁrst component of the key
(s;x
1
jj:::jjx
n
)2K andx
1
jj:::jjx
n
is the second one.
Finally, for every w = a
1
jj:::jja
n
; (a
1
;:::;a
n
)2 S,
put w = (a
1
;:::;a
n
). Then we can consider the dou-
ble round g
0
: K  S ! U of g : K  S ! U (with
U = S) such that for evey pairk2 K;s2 S,g
0
(k;s) =
g(k;g(k;s)). Similarly, for everyk > 2, we can consider
thek-times roundg
00
: K  S! U ofg : K  S! U
(with U = S) such that for evey pair k 2 K;s 2 S,
g
00
(k;s) = g(k;h(k;s)), where h : K  S ! U is a
(k  1)-times round ofg : K  S! U. This completes
the proof. QED
By Proposition 1, Theorem 3, and Theorem 7, we can
derive the following.
Corollary 8 LetCBRNG = (K;Z
J
;S;f;U;g) be a
counter based pseudorandom number generator with sim-
ple output multiplicity (i.e., Z
J
=f0g) and assume that
its output function is deﬁned by the transition function of a
given key automaton. ThenCBRNG has a full cycle.
Proof. Of course, because the state transition f of
CBRNG (having a simple output multiplicity) is a sim-
ple counter with f(s) = (s + 1) mod 2
p
, where p is
the state size in bits and S = f0;:::;p  1g, f has a
full cycle. Moreover, by Theorem 4, the key automaton
B = ( 
n
; ( 
n
)
log
2
n
;  B
);n > 1 is a permutation au-
tomaton, therefore, for every input sign x 2 ( 
n
)
log
2
n
,
g
x
:   n
!   n
withg
x
(y) =   B
(y;x) is a bijective map-
ping of   n
onto itself. By Proposition 1, that means that
CBRNG (having a simple output multiplicity) has a full
cycle. QED
Next we give an example and then we study the security
of ourCBRNG.
4 Example
In this section we show a simple example.
Consider the following transition table of an automaton
A = (f0; 1g;f0; 1g
2
;  ):
  00 01 10 11
0 0 1 1 0
1 1 0 0 1
Letn = 4 and assume that all ofA
1
;A
2
;A
3
;A
4
coin-
cide withA. Then log
2
n = log
2
4 = 2 and thus
D
1
= (f1;:::; 4g;f(3; 1); (4; 2)g),
D
2
= (f1;:::; 4g;f(2; 1); (4; 3)g).
Suppose that either a counter or a pseudorandom number
generator sends an input (1; 0; 1; 0; 1; 0; 1; 0) to the key au-
tomatonB which is the temporal product ofA
D1
andA
D2
.
Assume thatB is in the state (0; 1; 1; 0).
Denote, in order, ’
i
;a
i
;a
0
i
;x
i
;i 2 f1; 2; 3; 4g the
feedback functions, the state components, the next state
components, and the input components ofA
D1
. Then
’
1
((0; 1; 1; 0); 1; 0; 1; 0) = (a
3
  x
3
;x
1
) = (1   1; 1) = (0; 1), ’
2
((0; 1; 1; 0); 1; 0; 1; 0) = (a
4
 
184 Informatica 45 (2021) 179–189 P. Dömösi et al.
x
4
;x
2
) = (0  0; 0) = (0; 0), moreover   (0; (0; 1)) =
1(= a
0
1
) and   (1; (0; 0)) = 1(= a
0
2
), and thus
’
3
((0; 1; 1; 0); 1; 0; 1; 0) = (a
0
1
  x
1
;x
3
) = (1  1; 1) =
(0; 1), ’
4
((0; 1; 1; 0); 1; 0; 1; 0) = (a
0
2
  x
2
;x
4
) = (1  0; 0) = (1; 0). Thus   (1; (0; 1)) = 0(= a
0
3
) and
  (0; (1; 0)) = 1(=a
0
4
).
Next we denote by ’
i
;a
i
;a
0
i
;x
i
;i 2 f1; 2; 3; 4g the
feedback functions, the state components, the next state
components, and the input components ofA
D2
. Recall
that (a
1
;a
2
;a
3
;a
4
) coincides with the new state ofA
D1
.
Then (a
1
;a
2
;a
3
;a
4
) = (1; 1; 0; 1) and (x
1
;x
2
;x
3
;x
4
) =
(1; 0; 1; 0), where (x
1
;x
2
;x
3
;x
4
) consists of the last four
components of the input (1; 0; 1; 0; 1; 0; 1; 0) of the key au-
tomaton.
Then ’
1
((1; 1; 0; 1); 1; 0; 1; 0) = (a
2
  x
2
;x
1
) =
(1  0; 1) = (1; 1), ’
3
((1; 1; 0; 1); 1; 0; 1; 0) = (a
4
  x
4
;x
3
) = (1  0; 1) = (1; 1), moreover   (1; (1; 1)) =
1(= a
0
1
) and   (0; (1; 1)) = 0(= a
0
3
)), and thus
’
2
((1; 1; 0; 1); 1; 0; 1; 0) = (a
0
1
  x
1
;x
2
) = (1  1; 0) =
(0; 0), ’
4
((1; 1; 0; 1); 1; 0; 1; 0) = (a
0
3
  x
3
;x
4
) = (0  1; 0) = (1; 0). Thus   (1; (0; 0)) = 1(= a
0
2
) and
  (1; (1; 0)) = 0(=a
0
4
).
Hence the actual pseudorandom output is (1; 1; 0; 0)
which is also the next state.
5 Implementation
Next we give a detailed explanation of the enclosed
pseudocode of our implementation. (See Algorithm
ACBRNG.)
The procedure parameters are the number of random
blocks (SIZE), the input word (INPUT ) of the key
automaton, the transition matrix of the basic automaton
(AUT ), and the initial (seed) state of the key automaton
(JSTATE).
Each of the generated random blocks consists of 128
random strings and each of the random strings is 128 bits
long. Thus, the size of the generated random blocks is 2048
Kbyte.
The key automaton is a four-component temporal prod-
uct of automata which are (D
1
;D
2
;D
3
;D
4
)-powers of the
basic automaton. The digraphsD
1
;D
2
;D
3
;D
4
are deﬁned
by the matrixP [4][16]. Each of theD
1
;D
2
;D
3
;D
4
pow-
ers consists of sixteen copies of the basic automaton which
has 256 states and 256 input signs. Thus, the transition
matrix AUT of the basic automaton is a 256  256-type
matrix, where each state and input sign can be represented
by a 8-bit binary string.
The connection digraphs D
1
;D
2
;D
3
;D
4
are stored in
the four consecutive row vectors of the 4  16-type con-
nection matrixP .
We will considerROUND = 1; 2; 3 rounds of the out-
put function ofCBRNG.
The four row vectors of the 4  16-type input matrix
INPUT represent four consecutive input signs of the four
(D
1
;D
2
;D
3
;D
4
)-powers, the key automaton of which the
temporal product consists.
Thus the matrixINPUT represents a single input sign
of the key automaton.
The main structure of the implementation is the follow-
ing.
1. Read the number SIZE of the input block, the input
word INPUT of the key automaton, the transition matrix
AUT of the basic automaton, and the initial (seed) state
JSTATE of the key automaton.
2. Store the initial (seed) state JSTATE in a working
storage ISTATE.
3. GenerateSIZE number of random blocks as follows.
4. Consider the ISTATE as a 128-bit length binary
number and fput
ISTATE =ISTATE + 1mod 2
128
.
5. Repeat the following procedure ROUND-times.
We could not pass the NIST test for ROUND = 1 and
ROUND = 2 but we were successful forROUND = 3.
6. Each of the ROUND number of repeti-
tions operates on the actual value of the actual
key automaton state (ISTATE) by the consecutive
element (the consecutive input sign) of the input
word (INPUT ) .
7. The operation of the states of (D
1
;D
2
;D
3
;D
4
) –
products by the consecutive input sign (i.e., the consecu-
tive column vector of the matrixINPUT ) determined by
the transition table (AUT ) of the basic automaton and the
digraphsD
1
;D
2
;D
3
;D
4
deﬁned by the matrixP [4][16].
8. Collect the records of the pseudorandom block OAR-
RAY .
9. Output the consecutive pseudorandom block OAR-
RAY .
6 Experimental results
We implemented Algorithm ACBRNG in C++ in order to
measure the actual running time and statistical properties of
the generator. The test environment was a 2017 MacBook
Pro equipped with 7th Generation Kaby Lake 2.9 GHz Intel
Core i7 processor (7820HQ) using 16 GB RAM. We have
generated 1 GB of random data and applied the NSIT SP-
800-22 statistical randomness test.
6.1 NIST test
The National Institute of Standards and Technology (NIST)
published a statistical package consisting of 15 statistical
tests that were developed to test the randomness of arbi-
trarily long binary sequences produced by either hardware
or software based cryptographic random or pseudorandom
number generators [21]. In case of each statistical test a set
of P-values was produced. Given a signiﬁcance level  , if
the P-value is less than or equal to  then the test suggests
that the observed data is inconsistent with our null hypoth-
esis, i.e. the ’hypothesis of randomness’, so we reject it.
A Full Cycle Length Pseudorandom Number. . . Informatica 45 (2021) 179–189 185
Table 1: Parameters used for NIST Test Suite
Test Name Block length
Block Frequency 128
Non-overlapping Template 9
Overlapping Template 9
Approximate Entropy 10
Serial 16
Linear Complexity 500
We used  = 0:01 as it is common in such problems in
cryptography and PRNG testing. An   of 0.01 indicates
that one would expect 1 sequence in 100 sequences to be
rejected under the null hypothesis. Hence a P-value ex-
ceeding 0.01 would mean that the sequence would be con-
sidered to be random, and a P-value less than or equal to
0:01 would lead to the conclusion that the sequence is non-
random. One of the most important characteristics of a
PRNG is the indistinguishability from true random sources.
That is, the evaluation of their output utilizing statistical
tests should not provide any means by which to distinguish
them computationally from a truly random source.
6.2 Minimum rounds to achieve
randomness
ACBRNG has a cycle length of 2
128
, however this does not
yet mean that ACBRNG is really producing good quality
random numbers. Consider the simple generator
k mod 2
128
; (k2 0::: 2
128
) (1)
If we start k = 0 and increment by 1 then the genera-
tor has a 2
128
cycle length, however it is not random at
all. ACBRNG has a more complex structure, but statisti-
cal tests were needed to check for possible weaknesses. In
order to test the quality of ACBRNG the NIST statistical
tests were performed using the same parameters as for the
AES candidates in order to achieve the most reliable and
comparable results. First the input parameters - such as the
sequence length, sample size, and signiﬁcance level - were
ﬁxed. Namely, these parameters were set to 2
20
bits, 300
binary sequences, and   = 0:01, respectively. Exact pa-
rameters can be seen in Table 1.
One Round ACBRNG We started the ACBRNG with
a low entropy random seed. The running time was 4.5
sec using 8 parallel threads. Applying only one round
(ROUND = 1 in line 25 ) ACBRNG did not pass the
NIST requirements. More precisely, we have failed in al-
most every statistical test using one round. So one can con-
clude that only one round is not complex enough, and fur-
ther investigation was needed. We would like to note, that
surprisingly all Random Excursions tests from NIST were
passed after one round.
Two Rounds ACBRNG Using ROUND = 2 sur-
prisingly almost every statistical test was passed. The run-
ning time was 8.4 sec using 8 parallel threads. Only two
non-overlapping templates were unsatisﬁed, which is quite
a good achievement after two rounds. We did not expect
such good quality random numbers and p-value distribu-
tion after two rounds. One can conclude that using only
two rounds is enough to reach good quality random num-
bers and pass the NIST test.
Three Rounds ACBRNG After only three rounds
ACBRNG did pass every requirement of the NIST statis-
tical test suite. It has turned out that the output of the al-
gorithm (usingROUND = 3) can not be distinguished in
polynomial time from true random sources using the NIST
statistical test. The running time was 12.25 sec using 8
parallel threads. The exact p-values of the evaluation of
the ACBRNG for ROUND = 3 are shown in Table 2.
We also tested the uniformity of the distribution of thep-
values obtained by the statistical tests included in NIST.
The uniformity of p-values provide no additional informa-
tion about the PRNG. We have also shown that the propor-
tions of binary sequences which passed the 0:01 level lie in
the required conﬁdence interval (see e.g. [21]).
7 Conclusion and further research
In this paper a full cycle length pseudorandom number gen-
erator (ACBRNG) based on compositions of automata was
presented. We have seen that it produces promising results
in terms of statistical randomness and passed all statistical
tests included in the NIST test suite. We can see that the
running time of the generator is efﬁcient enough for prac-
tical use. In order to consider this generator cryptograph-
ically secure, formal veriﬁcation of its security would be
necessary which is a direction that might be worth investi-
gating.
References
[1] Bao, F.: Cryptoanalysis of a partially known cellular
automata cryptosystem. IEEE Trans. on Computers,
53 (2004), 1493-1497; https://doi.org/10.
1109/TC.2004.94
[2] Bilan, S., Bilan, M., Bilan, S: Novel pseudoran-
dom sequence of numbers generator based cellular
automata. Information Technology and Security, V ol.
3(1), 2015, pp. 38-50. https://doi.org/10.
20535/2411-1031.2015.3.1.57710
[3] Bhattacharjee, K., Das, S., Paul, D.: Pseudo-random
Number Generation using a 3-state Cellu lar Automa-
ton. Internat. J. of Modern Physics, vol 28, No 6,
186 Informatica 45 (2021) 179–189 P. Dömösi et al.
Table 2: Results for the uniformity of p-values and the proportion of passing sequences
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-value Prop Test name
24 34 30 31 25 30 26 33 30 37 0:828458 297=300 Frequency
34 29 32 27 21 26 20 35 31 45 0:068287 296=300 BlockFrequency
29 32 36 31 31 24 31 27 29 30 0:964295 298=300 CumulativeSums
26 30 31 30 33 27 24 38 28 33 0:840081 295=300 CumulativeSums
32 22 25 35 36 25 32 30 41 22 0:198690 300=300 Runs
34 34 34 31 37 23 33 23 29 22 0:437274 298=300 LongestRun
22 26 23 35 35 32 34 39 29 25 0:334538 296=300 Rank
33 28 31 29 33 30 34 31 25 26 0:973936 296=300 FFT
30 30 21 35 40 29 29 28 25 33 0:514124 296=300 NonOverLappingTemp
43 30 24 29 34 27 32 22 31 28 0:339799 296=300 NonOverLappingTemp
: : : : : : : : : : : : NonOverLappingTemp
                                                NonOverLappingTemp
22 21 30 44 38 32 23 31 35 24 0:043745 295=300 OverlappingTemp
32 44 35 29 28 26 20 23 34 29 0:132132 298=300 Universal
28 27 18 36 40 26 33 37 23 32 0:122325 297=300 ApproximateEntropy
17 15 23 20 20 21 16 27 17 18 0:707944 194=194 RandomExcursions
22 20 21 13 25 16 19 17 21 20 0:791218 193=194 RandomExcursions
: : : : : : : : : : : : RandomExcursions
                                                RandomExcursions
22 17 15 16 23 23 20 21 23 14 0:729339 192=194 RandomExcursionsV
18 18 17 19 23 27 19 17 17 19 0:838872 193=194 RandomExcursionsV
: : : : : : : : : : : : RandomExcursionsV
                                                RandomExcursionsV
31 28 27 22 27 39 26 36 35 29 0:514124 296=300 Serial
30 32 22 36 32 22 33 30 35 28 0:637119 294=300 Serial
32 28 31 26 34 24 32 37 36 20 0:449672 296=300 LinearComplexity
A Full Cycle Length Pseudorandom Number. . . Informatica 45 (2021) 179–189 187
Algorithm ACBRNG
1: procedure ACBRNG(SIZE, INPUT, AUT, JSTATE) . 1. Read the input parameters.
2: fori = 0! 15 do . 2. Put the seed into working storage.
3: ISTATE[i] JSTATE[i] . 3. JSTATE is the initial (seed) state of the key automaton.
4: end for
5: forkk = 0!SIZE do . 4. SIZE number of pseudorandom blocks are generated
6: form = 0! 127 do
7: x 0
8: forj = 15! 0 do
9: ifx = 0 then
10: ifISTATE[j] = 255 then
11: ISTATE[j] 0
12: else
13: ISTATE[j] ISTATE[j] + 1
14: x 1
15: end if
16: end if
17: STATE[j] ISTATE[j]
18: end for
19: forf = 0!ROUND do . 5. Passes NIST test withROUND = 3.
20: fori = 0! 3 do . 6. Key automaton state transition.
21: forj = 0! 15 by 2 do . 7.D
1
;D
2
;D
3
;D
4
-power state transitions.
22: k P [i][j]
23: l P [i][j + 1]
24: a
1
 STATE[k]
25: a
2
 STATE[l]  INPUT [l][i]
26: STATE[k] AUT [a
1
][a
2
]
27: a
1
 STATE[l]
28: a
2
 STATE[k]  INPUT [k][i]
29: STATE[l] AUT [a
1
][a
2
]
30: end for
31: end for
32: end for
33: fori = 0! 15 do . 8. Collect the records of the pseudorandom block OARRAY
34: OARRAY [m][i] STATE[i]
35: end for
36: end for
37: PRINT(&OARRAY ) . 9. Print the next random block.
38: end for
39: end procedure
188 Informatica 45 (2021) 179–189 P. Dömösi et al.
ppp. 1-23, 2017,https://doi.org/10.1142/
S0129183117500784
[4] Chakraborty,K. and . Chowdhury, D. R. : CSHR:
Selection of cryptographically suitable hybrid cellu-
lar automata rule. International Conference on Cel-
lular Automata for Research and Industry, ACRI,
Springer, pp. 591-600, 2012.https://doi.org/
10.1007/978-3-642-33350-7_61
[5] Dogaru, R. and Dogaru,I.: FPGA implementation
and evaluation of two cryptographically secure hybrid
cellular automata. Proc. Communications (COMM)
2014, 10th International Conference on Communi-
cations, pp. 1-4, 2014. https://doi.org/10.
1109/ICComm.2014.6866740
[6] Dömösi, P., Gáll, J., Horváth, G., Tihanyi, N. Some
Remarks and Tests on the Dh1 Cryptosystem Based
on Automata Compositions Informatica (Slovenia),
vol 43, 2 (2019), pp. 199-207. https://doi.
org/10.31449/inf.v43i2.2687
[7] Dömösi, P. and Nehaniv, C. L. Algebraic theory of
automata networks. An introduction. SIAM Mono-
graphs on Discrete Mathematics and Applications,
11. Society for Industrial and Applied Mathematics
(SIAM), Philadelphia, PA, 2005. https://doi.
org/10.1137/1.9780898718492
[8] Guan, S. U. and Tan, S. K.: Pseudorandom num-
ber generation with self-programmable cellular au-
tomata. IEEE Transactions on Computer-Aided De-
sign of Integrated Circuits and Systems, vol. 23,
pp. 1095-1101, 2004. https://doi.org/10.
1109/TCAD.2004.829808
[9] Guan, S.-U. and Zhang, S.: Pseudorandom number
generation based on controllable cellular automata.
Future Generation Computer Systems, vol. 20, pp.
627-641, 2004. https://doi.org/10.1016/
S0167-739X(03)00128-6
[10] Guan, P.: Cellular automaton public key cryptosys-
tem. Complex Systems, 1 (1987), 51-56].
[11] Hoe, D. H. K., Comer, J. M., Cerda, J. C., Martinez,
C. D., Shirvaikar,M. V .: Cellular Automata-Based
Parallel Random Number Generators Using FPGAs.
International Journal of Reconﬁgurable Computing,
V ol. 2012, 2012, pp. 1-13, Article ID 219028
https://doi.org/10.1155/2012/219028
[12] Hortensius, P. D., Mcleod, R. D., Pries, W.,Miller,
D M., and Card, H C.: Cellular Automata- Based
Pseudorandom Number Generators for Built-In self-
Test, IEEE transactions on Computer-Aided Design,
vol. 8, pp 842-859,1989.https://doi.org/10.
1109/43.31545
[13] Kang, B., Lee, D., and Hong, C.: High-
Performance Pseudorandom Number Generator Us-
ing Two-Dimensional Cellular Automata. 4th
IEEE International Symposium on Electronic De-
sign, Test and Applications (delta 2008), Hong
Kong, 2008, pp. 597-602. https://doi.org/
10.1109/DELTA.2008.46
[14] Kar, M., Rao, D. C., Rath, A. K.: Generating PNS
for Secret Key Cryptography Using Cellular Automa-
ton. International Journal of Advanced Computer Sci-
ence and Applications, V ol. 2, No. 5, 2011, pp. 101-
105. https://doi.org/10.14569/IJACSA.
2011.020517
[15] Madghuri, A.: Hybrid Cellular Automata-Based
Pseudo Random Sequence Generator for BIST Imple-
mentation. International Journal of Research Studies
in Science, Engineering and Technology V olume 2,
Issue 9, September 2015, pp. 72-76 ISSN 2349-4751
(Print) & ISSN 2349-476X (Online)
[16] Martin, B., Sole, P.: Pseudo-random Sequences Gen-
erated by Cellular Automata. International Confer-
ence on Ralations, Orders and Graphs: Interaction
with Computer Scince, May 2008, Mandia, Tunisia,
Nouha editions, 2008, pp. 401-410.
[17] Meier, W. and Staffelbach, O.: Analysis of pseudo
random sequences generated by cellular automata.
In: Davies, D. W. (ed.), Proc. Conf. Advances in
Cryptology – EUROCRYPT ’91, Workshop on
the Theory and Application of Cryptographic Tech-
niques, Brighton, UK, April 8-11, 1991, LNCS 547
Springer-Verlag, Berlin, 1991, 186-199 https://
doi.org/10.1007/3-540-46416-6
[18] Menezes, A., van Oorschot,P., and Vanstone, S.:
Handbook of Applied Cryptography, CRC Press,
1996.
[19] Ping,P., Xu, F., and Wang, X.-J.: Gener-
ating high-quality random numbers by next
nearest-neighbor cellular automata. Advanced
material Research, vol. 765, pp. 1200-1204,
2013. https://doi.org/10.4028/www.
scientific.net/AMR.765-767.1200
[20] ] Ruboi, C. F., Encinas, L. H., White, S. H., del Rey,
A. M., Sancher, R.: The use of Linear Hybrid Cellular
Automata as Pseudorandom bit Generators in Cryp-
tography. Neural Parallel & Scientiﬁc Comp. 12(2),
2004, pp. 175-192. http://hdl.handle.net/
10261/21253
[21] Rukhin, A., Soto, J., Nechvatal, J.,Smid, M.,
Barker, E., Leigh, S., Levenson, M.,Vangel, M.,
Banks, D., Heckert, A., Dray, J., V o, S.: NIST
Special Publication 800-22 (2010).: A Statisti-
cal Test Suite for Random and Pseudo Random
A Full Cycle Length Pseudorandom Number. . . Informatica 45 (2021) 179–189 189
Number Generators for Cryptographic Applications.
National Institute of Standards and Technology,
https://nvlpubs.nist.gov/nistpubs/legacy/sp/
nistspecialpublication800-22r1a.pdf, downloaded in
March 2020. https://doi.org/10.6028/
NIST.SP.800-22r1a
[22] Salmon, J., Moares, M., Dror, R., Shaw, D. Par-
allel random numbers: as easy as 1; 2; 3. Proc.
2011 Intern. Conf. for High Performance Comput-
ing, Networking, Storage and Analysis, Article
No. 16. doi:10.1145/2063384.2063405. https://
doi.org/10.1145/2063384.2063405
[23] Seredynski, F., Bouvry, P., and Zomaya A. Y .:
Cellular automata computations and secret key
cryptography. Parallel Computing, vol. 30, pp.
753-766, 2004. https://doi.org/10.1016/
j.parco.2003.12.014
[24] Shin,SH., Kim,DS., Yoo, KY . : A 2-Dimensional
Cellular Automata Pseudorandom Number Gen-
erator with Non-linear Neighborhood Relation-
ship. In: Benlamri R. (eds) Networked Dig-
ital Technologies. NDT 2012. Communications
in Computer and Information Science, vol 293.
Springer, Berlin, Heidelberg.https://doi.org/
10.1007/978-3-642-30507-8_31
[25] Sipper, M., Tomassini, M. Generating parallel ran-
dom number generators by cellular programming. In-
ternational Journal of Modern Physics C. 7 (2), pp.
181–190, 1996. https://doi.org/10.1142/
S012918319600017X
[26] Sukhinin, B.M.: High-speed pseudorandom sequence
generators based on cellular automata. Applied dis-
crete mathematics, No 2, 2010, pp. 34 – 41.https:
//doi.org/10.17223/20710410/8/5
[27] Sukhinin B.M.: Development of generators of pseu-
dorandom binary sequences based on cellular au-
tomata. Science and education, No 9, 2010, pp. 1
– 21.
[28] Tomassini, M., Sipper, M., and Perrenoud, M.: On
the Generation of High-Quality Random Numbers by
Two-Dimensional Cellular Automata, IEEE Trans-
actions on Computers, vol. 49, pp. 1146-1151, 2000.
https://doi.org/10.1109/12.888056
[29] Wolfram, S.,: Cryptography with Cellular Automata.
In: C. W. Hugh, ed., Proc. Conf. Advances in Cryp-
tology—CRYPTO’85, Santa Barbara, Calif., USA,
Aug. 18-22, 1985, LNCS 218, Springer-Verlag,
Berlin, 1986, pp. 429-432. https://doi.org/
10.1007/3-540-39799-X_32
[30] Wolfram, S.: Random Sequence Generation by
Cellular Automata. Advances in Appl. Math., vol.
7, 1986, pp. 429-432. https://doi.org/10.
1016/0196-8858(86)90028-X
190 Informatica 45 (2021) 179–189 P. Dömösi et al.