Information Technology Reference
In-Depth Information
A Study on the Pseudorandom Properties of
Sequences Generated Via the Additive Order
Honggang Hu and Guang Gong
Department of Electrical and Computer Engineering, University of Waterloo,
Waterloo, Ontario N2L 3G1, Canada
h7hu@uwaterloo.ca, ggong@calliope.uwaterloo.ca
Abstract. In this paper, we study the randomness properties of se-
quences generated by a function via the additive order. We derive some
conditions under which such sequences have the maximum period. The
autocorrelation is also studied. For the case of large
, nontrivial upper
bounds are given; for the binary case, experimental results show that
the autocorrelation of two types of sequences is small compared with the
period of sequences.
p
1
Introduction
For any n
1, let
F p n be the finite field of order p n ,where p is a prime number,
and let
{
α 1 , ..., α n }
be an ordered basis of
F p n over
F p . For any 0
i<p n ,we
define ξ i by
ξ i = i 1 α 1 + ... + i n α n ,
if
i = i 1 + i 2 p + ... + i n p n− 1 , 0
i k <p, k =1 , 2 , ..., n.
p n
1
i =0
ξ i } i =0 by extending
Furthermore, we obtain the sequence
{
{
ξ i }
with period
p n , i.e., ξ i + p n = ξ i for any i
0. For any function A ( x )from
F p n to
F p ,we
s i } i =0 by
define the sequence S =
{
s i = A ( ξ i ) ,i =0 , 1 , 2 , ... .
(1)
The sequence S in (1) is called a sequence generated by A ( x ) via the additive
order.
The additive order is related to the counter-mode encryption (CTR mode
encryption) of block ciphers [5], and it is also related to some Golay complemen-
tary sequences [2,10]. These two applications are the motivations of our study
for this topic.
To study the pseudorandom properties of sequences generated via the additive
order is also interesting itself [3]. The additive order is different from the conven-
tional order in sequence design, and the randomness properties of the sequences
from this order are hardly to determine. Suppose that A ( x ) is a function which
generates a sequence with good pseudorandom properties using the conventional
 
Search WWH ::




Custom Search