EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 14, No. 1, 2021, 1-18
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

A hybrid inversive congruential pseudorandom number
generator with high period

Constanza Riera1, Tapabrata Roy2, Santanu Sarkar2, Pantelimon Stănică3,∗

1 Department of Computer science, Electrical Engineering and Mathematical Sciences,
Western Norway University of Applied Sciences, Bergen, Norway
2 Department of Mathematics,Indian Institute of Technology Madras, Sardar Patel Road,
Chennai TN 600036, INDIA
3 Department of Applied Mathematics, Naval Postgraduate School, Monterey,
CA 93943–5216, USA

Abstract. Though generating a sequence of pseudorandom numbers by linear methods (Lehmer
generator) displays acceptable behavior under some conditions of the parameters, it also has un-
desirable features, which makes the sequence unusable for various stochastic simulations. An
extension which showed promise for such applications is a generator obtained by using a first-order
recurrence based upon the inverse modulo a prime or a prime power, called inversive congruential
generator (ICG). A lot of work has been dedicated to investigate the periods (under some condi-
tions of the parameters), the lattice test passing, discrepancy and other statistical properties of
such a generator. Here, we propose a new method, which we call hybrid inversive congruential
generator (HICG), based upon a second order recurrence using the inverse modulo M , a power of 2.
We investigate the period of this pseudorandom numbers generator (PRNG) and give necessary
and sufficient conditions for our PRNG to have periods M (thereby doubling the period of the
classical ICG) and M/2 (matching the one of the ICG). Moreover, we show that the lattice test
complexity for a binary sequence associated to (a full period) HICG is precisely M/2.

2020 Mathematics Subject Classifications: 11B50, 11K36, 11K45
Key Words and Phrases: Pseudorandom numbers, congruences, period, lattice test.

1. Introduction

The linear congruential method is one of the standard methods of generating uniform
pseudorandom numbers (PRNs) in the interval I = [0, 1). In this method, for a (large)
modulus M , a sequence {yn} of integers in ZM = {0, 1, . . . ,M − 1} = Z/MZ is generated
by the linear recursion

yn+1 ≡ ayn + b mod M, n = 0, 1, . . . ; a, b ∈ ZM . (1)

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v14i1.3852

Email addresses: csr@hvl.no (C. Riera), tapabrata.roy.048@gmail.com (T. Roy),
sarkar.santanu.bir1@gmail.com (S. Sarkar), pstanica@nps.edu (P. Stănică)

http://www.ejpam.com 1 c© 2021 EJPAM All rights reserved.



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 2

and then the PRNs are obtained by the normalization

xn = yn/M. (2)

This linear method is popular and has been thoroughly analyzed [15]. However, it has
been found that the linearity of the recursion leads to some drawbacks and as a result,
recently, several nonlinear congruential generators [3–10, 12, 15, 19] have been proposed
and also analyzed [11]. Amongst these, the inversive congruential method (ICG) [17–19],
with modulus M (with M being either a prime or a large power of 2), is one of the most
interesting ones. Here, we consider the case where M = 2ω, for some integer ω ≥ 2. Let
GM = {1, 3, . . . ,M−1} be the set of all positive odd integers less than M. Clearly, for any
u ∈ GM , there is a unique u−1 ∈ GM such that uu−1 ≡ 1 (mod M). The first sequence
{yn} ⊆ GM based upon the inverse modulo M is given by the recursion

yn+1 ≡ ay−1n + b (mod M), n = 0, 1, . . . . (3)

Here a, b ∈ ZM are chosen in such a way that yn+1 ∈ GM whenever yn ∈ GM . The
following result is known (we use per(·) to denote the period of the argument sequence).

Theorem 1 ([19, p.188, Theorem 8.9]). Let M = 2ω, ω ≥ 3. Then the Pseudorandom
Number Generator (PRNG) {yn} corresponding to the inversive congruential generator
with modulus M satisfies per(yn) = M

2 if and only if a ≡ 1 (mod 4) and b ≡ 2 (mod 4).

Later in [14], the authors modified (3) and proposed another nonlinear method, which
we will describe below. For a modulus M = 2ω and y0 ∈ GM , let

yn+1 ≡ ay−1n + b+ cyn (mod M), n = 0, 1, . . . , (4)

where a, b, c ∈ ZM are such that yn+1 ∈ GM , whenever yn ∈ GM . The main result obtained
in [14] is the following theorem.

Theorem 2 ([14]). Let M = 2ω, ω ≥ 3. Then the PRNG {yn} derived from (4) is purely
periodic with period M

2 if and only if a+ c ≡ 1 (mod 4) and b ≡ 2 (mod 4).

In this paper, we propose a new nonlinear method, which we will call hybrid inversive
congruential generator (HICG). For the modulus M = 2ω and y0, y1 ∈ GM , we let

yn+2 ≡ ay−1n+1 + byn + c (mod M), n = 0, 1, . . . , (5)

where a, b, c ∈ ZM are such that yn+2 ∈ GM whenever yn, yn+1 ∈ GM . Then, the PRNs
{xn}, defined by (2), belong to the set HM =

{
1
M ,

3
M , . . . ,

M−1
M

}
. Since some of the

constants in our generator may be zero, equation (5) includes (1) and (3).
In our first result, we show that the period of the HICG sequence is at most M ; further,

we obtain explicit conditions on the involved parameters such that the sequence {yn}
derived from (5) is purely periodic with period M ; moreover, we give explicit conditions
on the parameters to obtain an ultimate period of M/2. Furthermore, we look at the
lattice test passing for a binary sequence obtained via HICG and show that it has a lattice
test complexity (defined in Section 4) equal to M/2.



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 3

2. The maximum period of the HICG is M

Since two consecutive residues modulo M = 2ω will determine the next residue (observe
that our sequence has second order), the maximum period can be at most twice the number

of pairs (residue repetitions allowed) of all odd integers modulo M , that is M2

4 . However,
here, we will show that for any values of the parameters a, b, c and any odd initial conditions
y0, y1 ∈ GM , the (ultimate) period of {yn} can be at most M . Certainly, the sequence may
not be purely periodic, rather ultimately periodic, but for simplicity, shifting the sequence
to that first position of the period, we may assume in this section that the period starts
from y0. Throughout, we will use the notation ∵ as a shorthand for “because/since”.

Theorem 3. Let m = 2ω ≥ 4. The HICG sequence {yn (mod m)} has an ultimate period
less than or equal to m.

Proof. We will show our result by induction. We first note that for m = 4 (and
m = 8), the period is at most m. We now assume that the result holds for m, that is, {yn
(mod m)} has period ` ≤ m, and show that {yn (mod 2m)} has period at most 2m. The
given sequence is yn+2 ≡ ay−1n+1+byn+c (mod 2m). Now, note that (yn+m)−1 ≡ y−1n +m
(mod 2m) for all n. Clearly, in order for the yn to be odd, a + b + c must be odd. And
so, among a, b and c, either all of them are odd or one of them is odd and the others are
even. So, we consider the following four cases.

Case 1. a, b and c are all odd: As yn+2 ≡ ay−1n+1 + byn + c (mod m) has period `,
then we can have the following four subcases:

(i) y` ≡ y0 (mod 2m) and y`+1 ≡ y1 (mod 2m),

(ii) y` ≡ y0 +m (mod 2m) and y`+1 ≡ y1 +m (mod 2m),

(iii) y` ≡ y0 (mod 2m) and y`+1 ≡ y1 +m (mod 2m),

(iv) y` ≡ y0 +m (mod 2m) and y`+1 ≡ y1 (mod 2m).

The first subcase follows immediately, and the period modulo 2m is also ` here. For
the second subcase, we have,

y`+2 ≡ a(y−11 +m) + b(y0 +m) + c (mod 2m)

≡ y2 + (a+ b)m (mod 2m)

≡ y2 (mod 2m) (∵ a+ b is even),

y`+3 ≡ ay−12 + b(y1 +m) + c (mod 2m)

≡ y3 + bm (mod 2m)

≡ y3 +m (mod 2m) (∵ b is odd),

y`+4 ≡ a(y−13 +m) + by2 + c (mod 2m)

≡ y4 + am (mod 2m)



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 4

≡ y4 +m (mod 2m) (∵ a is odd),

y`+5 ≡ a(y−14 +m) + b(y3 +m) + c (mod 2m)

≡ y5 + (a+ b)m (mod 2m)

≡ y5 (mod 2m) (∵ (a+ b) is even).

Proceeding similarly, we have, y`+6 ≡ y6 + m (mod 2m), y`+7 ≡ y7 + m (mod 2m),
y`+8 ≡ y8 (mod 2m), and so on. Now, computationally we can check that for m = 16,
` can be 1, 3, 6, 12. Inductively, it follows that if {yn (mod m)} has period 1 then {yn
(mod 2m)} has period 3 and if {yn (mod m)} has a period that is a multiple of 3 then,
{yn (mod 2m)} can have at most a double period. Thus, in this case, {yn (mod 2m)} can
have the period at most 3m

2 < 2m.
The other two subcases follow similarly and it can be shown that even in these subcases

{yn (mod 2m)} can have period at most 3m
2 < 2m.

Note that, in this case, the proof implies that {yn (mod m)} can have period at most
3m
4 , for all m ≥ 16.

Case 2. a is odd and b and c are even: Here we break the case into the same possible
subcases as above. The first subcase is immediate. For, the second subcase, following
exactly the same procedure as above, we obtain y`+2 ≡ y2 +m (mod 2m), y`+3 ≡ y3 +m
(mod 2m), y`+4 ≡ y4 +m (mod 2m), and so on. Now, it can be checked that for m = 16
the possible periods are 1, 2, 4 and 8. So, inductively, it follows that, the period of {yn
(mod 2m)} can be at most m. The other cases can be similarly dealt with.

Note that, in this case, the proof implies that {yn (mod m)} can have period at most
m
2 , for all m ≥ 16.

Case 3. b is odd and a and c are even: This case follows along the same lines
as the previous case. In this case, one can computationally check that, for m = 16, the
possible periods are 1, 2, 4, 8 and 16. So, the period of {yn (mod 2m)} can be at most 2m.
Therefore, in this case, the proof implies that {yn (mod m)} can have period at most m,
for all m ≥ 16.

Case 4. c is odd and a and b are even: Here we break the case into the same
possible subcases as in Case 1. The first subcase follows immediately. For, the other
subcases we can easily check that y`+2 ≡ y2 (mod 2m), y`+3 ≡ y3 (mod 2m), y`+4 ≡ y4
(mod 2m), and so on. Now, in this case, one can observe that for m = 16 the period is
(ultimately) 1. So, in this case, the (ultimate) period of {yn (mod 2m)} is again 1 ≤ 2m.
Note that, in this case, the proof implies that {yn (mod m)} has period 1, for all m ≥ 16.

Example 1. Consider the first case, i.e., a, b and c are all odd. Let m = 16, and let the
period of the sequence be 6. Then {y0, y1, y2, y3, y4, y5} is the core of the sequence modulo
16. Consider now the same sequence modulo 32. We show that the period can be at most
12 modulo 32. The first subcase would give a period of 6. For the second subcase, i.e.,
y6 ≡ y0 + 16 and y7 ≡ y1 + 16 (all congruences are modulo 32 in this example), we can



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 5

easily calculate that y8 ≡ y2, y9 ≡ y3 + 16, y10 ≡ y4 + 16, y11 ≡ y5, y12 ≡ y6 + 16 ≡ y0 and
y13 ≡ y7 + 16 ≡ y1. And so, {y0, y1, . . . , y11} is the core of the sequence and the period is
12. The other two subcases are similar.

Remark 1. Note that, from the proof, one can actually infer, for m ≥ 16, that the HICG
sequence {yn (mod m)} has an (ultimate) period less than or equal to 3m

4 , if a, b and c are
odd; less than or equal to m

2 , if a is odd and b and c are even; less than or equal to m, if
b is odd and a and c are even; and, finally, the period is always 1, if c is odd and a and b
are even.

3. General periodicity analysis of the sequence

Let M = 2ω; ω ≥ 3, y0 and y1 are chosen at random from GM .

3.1. Conditions when the period of the sequence is M

Theorem 4. The PRNG {yn} derived from (5) (regardless of the odd initial conditions
y0, y1) is purely periodic with period M and the set {y0, y1, . . . , yM−1} gives the set GM ,
uniformly distributed (that is, every element will occur exactly twice), if and only if

a ≡ 0 (mod 2), a+ b ≡ 1 (mod 4) and c ≡ 2 (mod 4).

Proof. We show this in two steps.

Necessity: Let us assume that for the sequence (5) and for any y0, y1 ∈ GM , the pe-
riod of yn is M and {y0, y1, . . . , yM−1} gives the set GM with every element occurring
exactly twice. We will prove that a is even, a+ b ≡ 1 (mod 4) and c ≡ 2 (mod 4). With-
out loss of generality we may take y0 = y1 = 1. Now, it is easy to check that under the
above assumption on the parameters a, b, c, if we reduce every element modulo 4 (respec-
tively, 8), the period of {yn (mod 4)} (respectively, {yn (mod 8)}) is 4 (respectively, 8)
and {y0, y1, y2, y3} (respectively, {y0, y1, . . . , y7}) gives the set G4 = {1, 3} (respectively,
G8 = {1, 3, 5, 7}) with every element occurring exactly twice.

Now, for our convenience, for the rest of the necessary part we consider every equality
as a modulo 8 operation and hence (5) reduces to

yn+2 = ayn+1 + byn + c,

since t ≡ t−1 (mod 8), for every odd integer t. Also, we recall that we have y0 = y1 = 1.
By absurd, we now assume that a + b is even. Then, y2 = a + b + c ≡ 3 (mod 4)

implies that c is odd. So, let a + b = 2d and c = 1 + 2e for some integers d and e. We
have, y2 = 1 + 2(d+ e) where d+ e = 1 + 2f, f ∈ Z is odd (since y2 ≡ 3 (mod 4)). Then,
from y3 ≡ 3a+ b+ c ≡ 3 (mod 4) we have 3 + 2a ≡ 3 (mod 4) and thus a is even. We let
a = 2g, g ∈ Z. Thus, y4 ≡ 3a+ 3b+ c ≡ 1 (mod 4) yields 3(2d) + 1 + 2e = 1 + 2(d+ e) =
3 + 4f ≡ 3 (mod 4), which is a contradiction. Hence, a+ b is odd.



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 6

Suppose now that a+b ≡ 3 (mod 4), and so a+b = 3+4h, h ∈ Z. From y2 = a+b+c ≡ 3
(mod 4), we have, c = 4l, l ∈ Z. Then, y3 = ay2 + b + c = a(3 + 4(h + l)) + b + c =
3 + 2a+ 4(h+ l)(a+ 1) ≡ 3 (mod 4) gives a = 2r, r ∈ Z and so, from a+ b = 3 + 4h, b is
odd. Thus, y3 = ay2+b+c = 3+4(h+`+r). Thus, y4 = ay3+by2+c = 1+4(h+l)(b+1) ≡ 1
(mod 8) (as b is odd). However, the periodicity modulo 4 implies that y4 ≡ 1 (mod 4), and
therefore, y4 ≡ 1 or 5 (mod 8). But, 1 has already occurred twice. So, y4 ≡ 5 (mod 8),
which contradicts y4 ≡ 1 (mod 8).

Hence, a+ b ≡ 1 (mod 4) which implies c ≡ 2 (mod 4) and a is even (the parity of a
can be deduced, for instance, from y2 ≡ a + b + c ≡ 3 (mod 4) and y3 ≡ 3a + b + c ≡ 3
(mod 4); then, 2a ≡ 0 (mod 4)).

Sufficiency: Let now a be even, a+ b ≡ 1 (mod 4) and c ≡ 2 (mod 4), and y0, y1 ∈ GM .
First, we will prove that yn ∈ GM for all n ≥ 0, that is, yn is odd under these assumptions.
Now, y0 and y1 are odd. Suppose that yn is odd. Then,

yn+2 = ay−1n+1 + byn + c ≡ yn ≡ 1 (mod 2).

We will now prove that the period is M . We first rewrite the sequence (5) as

yn+2 ≡ (a+ b)yn + cyn+1 + αn (mod M)

where
αn = a(y−1n+1 − yn) + c(1− yn+1).

So, (
yn
yn+1

)
≡ A

(
yn−1
yn

)
+

(
0

αn−1

)
(mod M) where A =

(
0 1

a+ b c

)
.

Thus, we have, (
yn
yn+1

)
≡ An

(
y0
y1

)
+Rn (mod M) (6)

where

Rn =
n−1∑
i=0

Ai
(

0
αn−1−i

)
.

Taking into account the fact that a+ b ≡ 1 (mod 4) and c ≡ 2 (mod 4), from [16] or [19,
p.188] we have for m = 2h, h ≥ 2,

Am ≡
(

2mp+m+ 1 2mq + 3m
2mq + 3m 2mp+ 3m+ 1

)
(mod 4m) (7)

for some integers p and q.
First, we will show that for m = 2h, 2 ≤ h ≤ ω − 1,

Rm ≡
(
m
m

)
(mod 2m). (8)



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 7

It can be checked (tediously by hand, but computationally easily) that (8) holds for m = 4
(i.e., h = 2). Now, let us assume that it holds for m = 2h. Then, from this hypothesis,
(6) and (7), and using the fact that yi’s are odd, we have,

ym ≡ y0 + 2m(py0 + qy1) +m(y0 + 3y1) + 4mT0 +m+ 2mS0

= y0 +m+ 2mU0 (mod M),

ym+1 ≡ y1 + 2m(qy0 + py1) + 3m(y0 + y1) + 4mT1 +m+ 2mS1

= y1 +m+ 2mU1 (mod M),

for some integers T0, T1, S0, S1, U0 and U1. Now, it follows clearly from above that

y−1m ≡ y−10 +m+ 2mV0 and y−1m+1 = y−11 +m+ 2mV1 (mod M),

for some integers V0 and V1 (inverses are considered in ZM ). Then, as a is even and c ≡ 2
(mod 4), we get from above that

αm = a(y−1m+1 − ym) + c(1− ym+1)

≡ a(y−11 +m+ 2mV1 − y0 −m− 2mU0) + c(1− y1 −m− 2mU1)

≡ a(y−11 − y0) + c(1− y1) + 2am(V1 − U0)−mc− 2mcU1

≡ α0 + 2m+ 4mW0 (mod M),

for some integer W0. So, as a+ b ≡ 1 (mod 4) and c ≡ 2 (mod 4) we have,

ym+2 ≡ (a+ b)ym + cym+1 + αm

≡ (a+ b)y0 + cy1 + α0 + (a+ b)(m+ 2mU0)

+ c(m+ 2mU1) + 2m+ 4mW0

≡ y2 +m+ 2mU2 (mod M),

for some integer U2. Proceeding similarly as above, for all 0 ≤ k ≤ m− 1, we have

ym+k ≡ yk +m+ 2mUk (mod M)

y−1m+k ≡ y
−1
k +m+ 2mVk (mod M)

αm+k ≡ αk + 2m+ 4mWk (mod M),

for integers Uk, Vk and Wk. Now, using the above analysis, we get (we let I be the identity
matrix of the appropriate dimension),

R2m ≡
2m−1∑
i=0

Ai
(

0
α2m−1−i

)
(mod 4m)

≡
m−1∑
i=0

Ai
(

0
α2m−1−i

)
+

2m−1∑
i=m

Ai
(

0
α2m−1−i

)
(mod 4m)



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 8

≡
m−1∑
i=0

[
Ai
(

0
αm−1−i

)
+Ai

(
0

2m

)]
+Am

m−1∑
i=0

Ai
(

0
αm−1−i

)
(mod 4m)

≡ (I +Am)Rm + 2m
m−1∑
i=0

Ai
(

0
1

)
(mod 4m)

≡ (
I +Am

2
)2Rm + 2m

m−1∑
i=0

Ai
(

0
1

)
(mod 4m)

≡ (
I +Am

2
)

(
2m
2m

)
+ 2m

m−1∑
i=0

Ai
(

0
1

)
(mod 4m)

≡
(

2m
2m

)
+ 2m

m−1∑
i=0

Ai
(

0
1

)
(mod 4m)

≡
(

2m
2m

)
(mod 4m)

[ ∵
m−1∑
i=0

Ai
(

0
1

)
≡ 0 (mod 2), i.e.,

m−1∑
i=0

Ai
(

0
1

)
is even].

Therefore, (8) follows by induction. So, by the previous arguments, we conclude that for
m = 2h, h ≥ 2 and 0 ≤ k ≤ m− 1,

ym+k ≡ yk +m (mod 2m)

y−1m+k ≡ y−1k +m (mod 2m)

αm+k ≡ αk + 2m (mod 4m).

Then in particular for m = M we see that yM+k ≡ yk (mod M), and for m = M
2 that

yM
2
+k ≡ yk + M

2 (mod M), so the period is M .

Now, for M = 8 one can check that under the given conditions (i.e., a is even, a+b ≡ 1
(mod 4) and c ≡ 2 (mod 4)), the period of {yn} is exactly eight and every element of
G8 = {1, 3, 5, 7} occurs exactly twice in {y0, y1, . . . , y7}. Moreover, it is easy to verify that
for any m = 2h, h ≥ 3, if the period of {yn (mod m)} is exactly m and every element
of Gm occurs exactly twice in {y0, y1, . . . , ym−1} then the period of {yn (mod 2m)} is
exactly 2m and every element of G2m occurs exactly twice in {y0, y1, . . . , y2m−1}. Hence,
the period of yn is M and {y0, y1, . . . , yM−1} represents GM , with every element occurring
exactly twice.

Remark 2. Computationally, and using the proof of Theorem 3, taking a random set
of initial conditions, we obtain that these are the only conditions for a, b, c under which
we obtain period 16 (modulo 16). From the proof of Theorem 3, this would imply that,
regardless of frequency, we can only attain the maximal period M for any initial conditions
if a ≡ 0 (mod 2), a+ b ≡ 1 (mod 4) and c ≡ 2 (mod 4).



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 9

3.2. Conditions when the period of the sequence is M/2

Theorem 5. The PRNG {yn} derived from (5) is purely periodic with period M/2, re-
gardless of the odd initial conditions y0, y1, and the set {y1, y2, . . . , yM

2
} = GM if and only

if

a ≡ 1 (mod 4), b ≡ 0 (mod M
2 ) and c ≡ 2 (mod 4).

Proof. We show this in two parts.

Necessity: Let us assume that for the sequence (5) and for any y0, y1 ∈ GM , the pe-
riod of yn is M

2 and {y1, y2, . . . , yM
2
} = GM . We will prove that a ≡ 1 (mod 4), b ≡ 0

(mod M
2 ) and c ≡ 2 (mod 4). We consider y0 = y1 = 1 (there is no contradiction here

with the inferred assumption that every residue occurs once only, since we consider the
uniformity of the sequence starting with index 1; certainly, we could have taken y0 = 1,
y1 = 3, but we preferred to start “at a zero time” and start counting the distribution
of our sequence at index 1). Now, it is easy to check that under the above assumption
if we reduce every element modulo 4 (respectively, 8), the period of {yn (mod 4)} (re-
spectively, {yn (mod 8)}) is 2 (respectively, 4) and {y1, y2} = G4 = {1, 3} (respectively,
{y1, y2, y3, y4} = G8 = {1, 3, 5, 7}). We have,

yn+2 ≡ ayn+1 + byn + c (mod 4), and
yn+2 ≡ ayn+1 + byn + c (mod 8).

As y0 = y1 = 1, we have, y2 ≡ 3 (mod 4), y3 ≡ 1 (mod 4), y4 ≡ 3 (mod 4) and y3 ≡ 5
(mod 8), y5 ≡ 1 (mod 8).

By absurd, we assume that a is even. Then, y2 ≡ a + b + c ≡ 3 (mod 4) gives b + c
is odd. So, let a = 2d′ and b + c = 1 + 2e′ for some integers d′ and e′. We have,
y2 = 1 + 2(d′ + e′) where d′ + e′ = 1 + 2f ′, is odd for some f ′ ∈ Z (since y2 ≡ 3 (mod 4)).
Then, y3 ≡ 3a+ b+ c ≡ 3 + 2a ≡ 3 (mod 4). Which is a contradiction. So a is odd.

Now, let a = 3 + 4g′, g′ ∈ Z and from y2 ≡ a + b + c ≡ 3 (mod 4) we have b + c =
4h′, h′ ∈ Z. Then, y3 ≡ ay2 + b+ c ≡ a(3 + 4(g′ + h′)) + b+ c ≡ 3a+ 4(g′ + h′) + b+ c ≡ 1
(mod 8). Which contradicts y3 ≡ 5 (mod 8).

So, a ≡ 1 (mod 4). Let a = 1 + 4l′, l′ ∈ Z. So, b + c = 2 + 4r′ for some integer r′

(∵ y2 ≡ a + b + c ≡ 3 (mod 4)). Now, y4 ≡ ay3 + by2 + c ≡ 5a + (3 + 4(l′ + r′))b + c ≡
7 + 2b + 4(l′ + r′) + 4b(l′ + r′) (mod 8). Hence, y4 ≡ 3 + 2b (mod 4) and so from y4 ≡ 3
(mod 4) we have, b is even.

Next, let b = 2 + 4s′. Then, from above, we have, y4 ≡ 3 + 4(l′+ r′) (mod 8). So, y5 ≡
ay4+by3+c ≡ 3a+4a(l′+r′)+5b+c ≡ 3a+b+c+4(l′+r′) ≡ 5 (mod 8) contradicting the
fact y5 ≡ 1 (mod 8). Thus, b ≡ 0 (mod 4) and hence, c ≡ 2 (mod 4). We will next show
that b ≡ 0 (mod M

2 ). By our assumption, the period is M
2 and {y1, y2, . . . , yM

2
} = GM .

Now, clearly every element in GM has a unique inverse in GM and so,

M
2∑
i=1

yi =

M
2∑
i=1

y−1i =

M
2
−1∑

i=0

(2i+ 1) =
M2

4
.



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 10

Again, as yM
2
+1 ≡ y1 (mod M), we have the sequence of equivalent congruences

M
2
−1∑

i=0

yi+2 ≡

M
2
−1∑

i=0

(ay−1i+1 + byi + c) (mod M),

M
2∑
i=1

yi ≡ a

M
2
−1∑

i=0

y−1i+1 + b

M
2
−1∑

i=0

yi + c

M
2
−1∑

i=0

1 (mod M),

M
2∑
i=1

yi ≡ a

M
2∑
i=1

y−1i + b (y0 +

M
2∑
i=1

yi − yM
2

) + c
M

2
(mod M),

M2

4
≡ aM

2

4
+ b (y0 +

M2

4
− yM

2
) + c

M

2
(mod M),

0 ≡ b (y0 − yM
2

) (mod M) (∵ c is even and ω ≥ 3).

Now, in our case, we have, y0 = y1 = 1. And so, from above, we have,

b (y1 − yM
2

) ≡ 0 (mod M).

Next, note that, in our case yM
2
− y1 ≡ 2 (mod 4) and so, b ≡ 0 (mod M

2 ).

Sufficiency: As b ≡ 0 (mod M
2 ) so, byn ≡ b (mod M) and so (5) reduces to

yn+2 ≡ ay−1n+1 + (b+ c) (mod M),

where a ≡ 1 (mod 4) and (b + c) ≡ 2 (mod 4). So, by (1), the period of {yn} is M
2 and

{y1, y2, . . . , yM
2
} = GM .

Remark 3. Note that, for some initial conditions, we can obtain period equal to 8
(mod 16) for other values of a, b and c where a is odd and b and c are even, or where
b is odd and a and c are even. Thus, the conditions of Theorem 5 are only necessary if
the period is M

2 , regardless of initial conditions.

4. Lattice testing for a binary sequence associated to HICG

Let {yn} be our HICG sequence with some initial conditions. In the spirit of the known
Blum-Micali PRN [1], we define a pseudorandom binary sequence {zn} by zn = f(yn),
where f : GM → {0, 1} is given by

f(x) =

{
0 if x < M

2

1 if x > M
2 .

A Sagemath code with the parameters ω = 64, a = 1886906, b = 706715, c = 807782, y0 =
430227 and y1 = 1725239 has been provided in the Appendix which will generate 108



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 11

PRNs. As for the linear and inversive congruential generator, one can define an s-
dimensional lattice test for our hybrid sequence (of period, say T ) for the characteris-
tics 2 (hence of 2ω modulus). For the binary sequence (defined above) {zn} passes the
L-dimensional lattice test if the vectors

{Zn : Zn = (zn, zn+1, . . . , zn+L−1), for 0 ≤ n < T},

span FL2 (we will write below span(·) for the span of a set of vectors). We call the smallest
dimension, with notation `(z), such that {zn} passes the `(z)-dimensional lattice test,
but not the (`(z) + 1)-dimensional lattice test, the lattice test complexity. The lattice
test complexity is known for the inversive congruential generator (see [6, 19], for more on
this generator). It is known that for a prime characteristic p, the inversive congruential
generator over Fp will pass the s-dimensional lattice test in Fp if and only if s ≤ d, where d
is the degree of the polynomial g representing the sequence zn modulo p, that is, g(n) = zn
in Fp (see [2], for more on the connection between linear complexity and lattice tests).

To show our result, we shall be using below the following known result [13].

Proposition 1. The rank of a circulant matrix C of order n is n − d, where d is the
degree of the greatest common divisors of 1− xn and the associated polynomial of C.

Theorem 6. Let {yn} be the HICG sequence modulo M = 2ω, ω ≥ 2, with some initial
conditions, of full period M (see Theorem 4 for conditions on the parameters). The lattice
test complexity of the associated binary sequence {zn} is `(z) = M

2 .

Proof. Let Zn =
(
zn, zn+1, . . . , zn+M

2
−1

)
. Computationally, one can check that for

M = 4, the vectors {Zn} will not span FL2 if L = 3, rather they will span FL2 if L = 2.
From the construction of the vectors Zn, we see that if we can show that the vectors
{Zn} for L = M

2 span FL2 , then the corresponding vectors will also span FL2 , for all

L ≤ M
2 . Therefore, it suffices to show that {Z0, Z1, . . . , ZM−1} span F

M
2
2 . We know that,

yM
2
+k ≡ yk + M

2 (mod M) and so zM
2
+k = zk where 0 = 1 and 1 = 0. To show our claim,



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 12

we need to prove that the matrix

Z =



Z0

Z1

Z2
...

ZM
2
−2

ZM
2
−1

ZM
2

ZM
2
+1

ZM
2
+2

...
ZM−2
ZM−1



=



z0 z1 z2 . . . zM
2
−2 zM

2
−1

z1 z2 z3 . . . zM
2
−1 z0

z2 z3 z4 . . . z0 z1
...

zM
2
−2 zM

2
−1 z0 . . . zM

2
−4 zM

2
−3

zM
2
−1 z0 z1 . . . zM

2
−3 zM

2
−2

z0 z1 z3 . . . zM
2
−2 zm

2
−1

z1 z2 z3 . . . zM
2
−1 z0

z2 z3 z4 . . . z0 z1
...

zM
2
−2 zM

2
−1 z0 . . . zM

2
−4 zM

2
−3

zM
2
−1 z0 z1 . . . zM

2
−3 zM

2
−2


has rank at least M

2 , which is equivalent to the fact that ZT has rank at least M
2 .

To achieve that goal, we define a circulant matrix C of order M , whose first M
2 rows

form ZT (we just add M
2 rows to ZT accordingly to make it of order M). Now the

associated polynomial of C is

g(x) =

M
2
−1∑

i=0

zix
i +

M−1∑
i=M

2

zi−M
2
xi

=

M
2
−1∑

i=0

zix
i + x

M
2

M
2
−1∑

i=0

(zi + 1)xi

=
(

1 + x
M
2

) M
2
−1∑

i=0

zix
i + x

M
2

M
2
−1∑

i=0

xi

= (1 + x)
M
2

M
2
−1∑

i=0

zix
i + x

M
2 (1 + x)

M
2
−1

= (1 + x)
M
2
−1((1 + x)

M
2
−1∑

i=0

zix
i + x

M
2 )

(all operations are considered modulo 2 here).

Thus, gcd
(
g(x), 1− xM

)
= gcd

(
g(x), (1 + x)M

)
= (1 + x)

M
2
−1. Hence, by Proposition 1,

the rank of C is M −
(
M
2 − 1

)
= M

2 + 1. Now, it is easy to check that k-th and the

(M2 + k)-th row of C add up to the row with all 1’s; k = 1, 2, . . . , M2 . So, it is clear that



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 13

the rank of the (M2 + 1)×M matrix, C, formed by the first M
2 + 1 rows is of rank M

2 + 1.
Again, ZT is simply obtained by deleting the last row of C, and so, it has rank at least
M
2 .

It is perhaps customary to define the lattice passing testing using the set {Z0 + Zn}.
We preferred for simplicity to use Zn, but a similar result holds for this set, as well. We
need the following lemma, which will certainly follow from general results (see [21]), but
we provide here a simple proof for completeness.

Lemma 1. Let M = 2ω, ω ≥ 2 and C be an M ×M binary circulant matrix. Then C is
nonsingular if and only if there is an odd number of 1’s in each row of C.

Proof. First note that as C is circulant so every row has same number of 1’s as any
row is some permutation of the first row. So, it is enough to look at the first row of C,

say (a0, a1, . . . , aM−1). Let a(x) =
M−1∑
i=0

aix
i be the associated polynomial of C. Now, C is

nonsingular if and only if the rank of C is M , if and only if gcd
(
a(x), (1 + x)M

)
= 1 (using

Proposition 1 and the fact that M is a power of 2). Clearly, gcd
(
a(x), (1 + x)M

)
can either

be 1 or some power of (1 + x). Again, (1 + x) | a(x), if and only if a(1) = 0, if and only if
there are an even number of ai’s that are 1. Or, in other words gcd (a(x), (1 + x)n) = 1 if
and only if there are an odd number of ai’s that are 1, that is, each row contains an odd
number of 1’s.

Theorem 7. Under the conditions of Theorem 6, the set {Z ′n = Zn + Z0;n = 1, 2, . . .}
spans F

M
2
2 .

Proof. Let S = span{Z ′n;n = 1, 2, . . .}. Then, clearly, the vectors, Z ′n + Z ′n+1 =
Zn + Zn+1 ∈ S for all n = 1, 2, . . . , M2 . Then, it is sufficient to show that the M

2 ×
M
2

matrix

Z ′ =


Z ′1 + Z ′2
Z ′2 + Z ′3
Z ′3 + Z ′4

...
Z ′M

2

+ Z ′M
2
+1

 =


Z1 + Z2

Z2 + Z3

Z3 + Z4
...

ZM
2

+ ZM
2
+1


has rank M

2 .
Now, it is easy to check that Z ′ is a left circulant binary matrix of order M

2 ×
M
2 .

Again, Z1 +Z2 = (z1 + z2, z2 + z3, z3 + z4, . . . , zM
2
−1 + z0, z0 + z1) = (z1 + z2, z2 + z3, z3 +

z4, . . . , zM
2
−1 + z0 + 1, z0 + z1). Every element among z0, z1, . . . , zM

2
−1 occurs exactly twice

in Z1 + Z2 and an extra 1 occurs in the second of the last term. Therefore, there are odd
number of 1’s in each row of Z ′. Hence, by Lemma 1, we infer that Z ′ has rank M

2 .



P. Stănică et al. / Eur. J. Pure Appl. Math, 14 (1) (2021), 1-18 14

5. Further comments and research problems

We wondered whether, besides the stochastic uses of HICG (and from our experiments,
it seems that taking M = 264 performs very well), if one can also have some cryptographic
applications of our sequence. Taking the least significant bit of every residues of {yn}
and applying randomness tests on it, revealed too many patterns and the p-values were
low. However, by taking the most significant bit (see the previous section) up to half the
period (because for a HICG of period 2m, ym+k ≡ yk +m (mod 2m)), we were pleasantly
surprised to see that for that bit sequence corresponding to half of a period and applying
the NIST randomness suite tests (sts), our sequence passed all of the tests in multiple runs,
and the p-values were above the 0.01 significance level (we do not go into details of the
sts suite and the randomness requirements here). We visually display in Figure 1 below
the outcome of such an experiment run with the parameters ω = 64, a = 1886906, b =
706715, c = 807782, y0 = 430227 and y1 = 1725239 and 108 PRNs. Also with the same

Random Number Test

0.0

0.2

0.4

0.6

0.8

1.0

p
-V

a
lu

e

A
P
P
R

O
X

IM
A

T
E
 E

N
T
R

O
P
Y
 T

E
S
T
 

B
L
O

C
K

 F
R

E
Q

U
E
N

C
Y
 T

E
S
T
 

C
U

M
U

L
A

T
IV

E
 S

U
M

S
 (

F
O

R
W

A
R

D
) 

T
E
S
T

F
F
T
 T

E
S
T
 

F
R

E
Q

U
E
N

C
Y
 T

E
S
T
 

L
IN

E
A

R
 C

O
M

P
L
E
X

IT
Y

L
O

N
G

E
S
T
 R

U
N

S
 O

F
 O

N
E
S
 T

E
S
T
 

N
O

N
 O

V
E
R

L
A

P
P
IN

G
 T

E
M

P
L
A

T
E
S
 T

E
S
T

O
V

E
R

L
A

P
P
IN

G
 T

E
M

P
L
A

T
E
 O

F
 A

L
L
 O

N
E
S
 T

E
S
T
 

R
A

N
D

O
M

 E
X

C
U

R
S
IO

N
S
 V

A
R

IA
N

T
 T

E
S
T
 

R
A

N
D

O
M

 E
X

C
U

R
S
IO

N
S
 T

E
S
T
 

R
A

N
K

 T
E
S
T

R
U

N
S
 T

E
S
T

S
E
R

IA
L
 T

E
S
T

U
N

IV
E
R

S
A

L
 S

T
A

T
IS

T
IC

A
L
 T

E
S
T

Significance Level=0.01

NIST Random Number Test Suite for 108 digits of HICG

Figure 1: The NIST STS applied to HICG

parameters and 109 PRNs we ran the Dieharder Test which also showed promising results
which are being visually displayed in Figure 2 (Here the 109 bits are partitioned into
31249999 32-bit numbers which are further converted to decimal numbers and then the
Dieharder Test is run). We further computed the linear complexity profile of such a binary
sequence for 105 bits and found an excellent profile. We display such an experiment in
Figure 3.

While these observations were not initially the purpose of the paper, we just want to
point them out as by-products. Further investigation is warranted.

There are several works (see [20] and the references therein) devoted to the computation
of the discrepancy of the inversive congruential generator. Certainly, a similar inquiry can
be addressed for our generator, and we leave the computation of the discrepancy (and its
bounds) for our HICG for a subsequent project, or to the interested reader.



REFERENCES 15

Random Number Test

0.0

0.2

0.4

0.6

0.8

1.0

p
-V

a
lu

e

B
ir

th
d
a
y
s
 T

e
s
t

O
v
e
rl

a
p
p
in

g
 5

 P
e
rm

u
ta

ti
o
n
s
 T

e
s
t

3
2

x
3

2
 B

in
a
ry

 R
a
n
k
 T

e
s
t

B
it

s
tr

e
a
m

 T
e
s
t

O
v
e
rl

a
p
p
in

g
 P

a
ir

s
 T

e
s
t

O
v
e
rl

a
p
p
in

g
 Q

u
a
d
ru

p
le

s
 T

e
s
t

D
N

A
 T

e
s
t

C
o
u
n
t 

th
e
 1

's
 (

S
tr

e
a
m

) 
T
e
s
t

C
o
u
n
t 

th
e
 1

's
 (

B
y
te

) 
T
e
s
t

P
a
rk

in
g
 L

o
t 

T
e
s
t

2
d
 C

ir
c
le

 (
M

in
im

u
m

 D
is

ta
n
c
e
) 

T
e
s
t

3
d
 S

p
h
e
re

 (
M

in
im

u
m

 D
is

ta
n
c
e
) 

T
e
s
t

S
q
u
e
e
z
e
 T

e
s
t

S
u
m

s
 T

e
s
t

R
u
n
s
 T

e
s
t

Significance Level=0.01

Dieharder Random Number Test Suite for 109 bits of HICG

Figure 2: The Dieharder test applied to HICG

0 20000 40000 60000 80000 100000

Bits

0

10000

20000

30000

40000

50000

L
in

e
a
r 

C
o
m

p
le

x
it

y
 

Figure 3: The linear complexity profile of HICG

In the spirit of our paper, for a modulus M = 2ω and y0, y1 ∈ GM , one can define

yn+2 ≡ ay−1n+1 + by−1n + cyn+1 + dyn + e (mod M), n = 0, 1, . . . , (9)

where a, b, c, d, e ∈ ZM are such that yn+2 ∈ GM , whenever yn, yn+1 ∈ GM . The study of
such a generator (which includes as particular cases every other type of first-order linear
and inversive congruential generator) is certainly an intriguing problem.

Finally, all of our considerations, results and inquiries can be investigated for an odd
characteristic.

References

[1] Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences
of pseudorandom bits. SIAM J. Comput., 13(4):850–864, 1984.

[2] Gerhard Dorfer and Arne Winterhof. Lattice structure and linear complexity profile of



REFERENCES 16

nonlinear pseudorandom number generators. Appl. Algebra Engrg. Comm. Comput.,
13(6):499–508, 2003.

[3] Jürgen Eichenauer, Jürgen Lehn, and Alev Topuzoğlu. A nonlinear congruential pseu-
dorandom number generator with power of two modulus. Math. Comp., 51(184):757–
759, 1988.

[4] J. Eichenauer-Herrmann, H. Grothe, H. Niederreiter, and A. Topuzoğlu. On the
lattice structure of a nonlinear generator with modulus 2α. J. Comput. Appl. Math.,
31(1):81–85, 1990. Random numbers and simulation (Lambrecht, 1988).

[5] Jürgen Eichenauer-Herrmann. Inversive congruential pseudorandom numbers avoid
the planes. Math. Comp., 56(193):297–301, 1991.

[6] Jürgen Eichenauer-Herrmann. Inversive congruential pseudorandom numbers: a tu-
torial. International Statistical Review, 560:2(193):167–176, 1992.

[7] Jürgen Eichenauer-Herrmann. Statistical independence of a new class of inversive
congruential pseudorandom numbers. Math. Comp., 60(201):375–384, 1993.

[8] Jürgen Eichenauer-Herrmann. On generalized inversive congruential pseudorandom
numbers. Math. Comp., 63(207):293–299, 1994.

[9] Jürgen Eichenauer-Herrmann and Harald Niederreiter. Lower bounds for the discrep-
ancy of inversive congruential pseudorandom numbers with power of two modulus.
Math. Comp., 58(198):775–779, 1992.

[10] Reza Rezaeian Farashahi and Igor E. Shparlinski. Pseudorandom bits from points on
elliptic curves. IEEE Trans. Inform. Theory, 58(2):1242–1247, 2012.

[11] Domingo Gómez, Jaime Gutierrez, and Álvar Ibeas. Attacking the Pollard generator.
IEEE Trans. Inform. Theory, 52(12):5518–5523, 2006.

[12] Honggang Hu, Lei Hu, and Dengguo Feng. On a class of pseudorandom sequences
from elliptic curves over finite fields. IEEE Trans. Inform. Theory, 53(7):2598–2605,
2007.

[13] A. W. Ingleton. The rank of circulant matrices. J. London Math. Soc., 31:632–635,
1956.

[14] Takashi Kato, Li-Ming Wu, and Niro Yanagihara. On a nonlinear congruential pseu-
dorandom number generator. Math. Comp., 65(213):227–233, 1996.

[15] Donald E. Knuth. The Art of Computer Programming, Volume II: Seminumerical
Algorithms, 2nd Edition. Addison-Wesley, Reading, MA, 1981.

[16] J. Mc Laughlin. Combinatorial identities deriving from the nth power of a 2 × 2
matrix. Integers, 4:A19, 15, 2004.



APPENDIX 17

[17] Harald Niederreiter. The serial test for congruential pseudorandom numbers gener-
ated by inversions. Math. Comp., 52(185):135–144, 1989.

[18] Harald Niederreiter. Recent trends in random number and random vector genera-
tion. Ann. Oper. Res., 31(1-4):323–345, 1991. Stochastic programming, Part II (Ann
Arbor, MI, 1989).

[19] Harald Niederreiter. Random number generation and quasi-Monte Carlo methods,
volume 63 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society
for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992.

[20] Harald Niederreiter and Igor E. Shparlinski. Exponential sums and the distribution
of inversive congruential pseudorandom numbers with prime-power modulus. Acta
Arith., 92(1):89–98, 2000.

[21] Oystein Ore. Some studies on cyclic determinants. Duke Math. J., 18:343–354, 1951.

Appendix

Sage Code with the parameters ω = 64, a = 1886906, b = 706715, c =
807782, y0 = 430227 and y1 = 1725239:

n=64
N=2ˆn

a =1886906
b =706715
c =807782
y0 =430227
y1 =1725239

y=y0
z=y1

pr in t (”0 ,0 ,” , end = ’ ’) , # as y0 and y1 are l e s s than N/2 ,
i n i t i a l two PRNs are s e t to be 0 .

f o r i in range ( 2 , 1 0 0 ) :
w=a∗z . inverse mod (N)+b∗y+c
w=w%N
i f (w<N/ 2 ) :

p r in t (”0 ,” , end = ’ ’)
e l s e :

p r in t (”1 ,” , end = ’ ’)
y=z



APPENDIX 18

z=w