^{1}

^{*}

^{1}

^{1}

^{2}

^{1}

^{3}

Pseudo-random sequences with long period, low correlation, high linear complexity, and uniform distribution of bit patterns are widely used in the field of information security and cryptography. This paper proposes an approach for generating a pseudo-random multi-value sequence (including a binary sequence) by utilizing a primitive polynomial, trace function, and
*k*-th power residue symbol over the sub extension field. All our previous sequences are defined over the prime field, whereas, proposed sequence in this paper is defined over the sub extension field. Thus, it’s a new and innovative perception to consider the sub extension field during the sequence generation procedure. By considering the sub extension field, two notable outcomes are: proposed sequence holds higher linear complexity and more uniform distribution of bit patterns compared to our previous work which defined over the prime field. Additionally, other important properties of the proposed multi-value sequence such as period, autocorrelation, and cross-correlation are theoretically shown along with some experimental results.

Sequences of numbers generated by using an algorithm are referred to as a pseudo-random sequence. Pseudo-random sequences are inseparable parts in information technology as well as in modern electronics. They are used in both communication (such as cellular telephones and GPS signals) and cryptographic applications (such as key stream for stream cipher, sampling data for simulations, timing measurements in radar systems, error correcting codes in satellite communications, and so on). In most cases, it is important to have the reproduce ability of the pseudo-random sequence [

Other geometric sequences having prominent pseudo-random properties are the Mersenne Twister (MT) [

Our previous work on binary sequence [

n = k ( p m − 1 ) q − 1 .

The period and autocorrelation properties of the proposed sequence explained based on some experimental results only.

The authors in this paper proposed a multi-value sequence (including a binary sequence) by applying a primitive polynomial, trace function, and k-th power residue symbol over the sub extension field F q . The k-th power residue symbol is an extended version of the Legendre symbol. In details, the proposed multi-value sequence generation procedure is as follows: let p be an odd characteristic prime and m be the extension degree of a primitive polynomial f ( x ) over the extension field F p m . It is well known that using the primitive polynomial makes it possible to generate a maximum length vector sequence over F p m . Let ω be a zero of the primitive polynomial f ( x ) and it’s a primitive element in F p m ∗ . Then the sequence

T = { t i | t i = Tr p m | q ( ω i ) , i = 0,1,2, ⋯ , p m − 2 }

becomes a maximum length sequence of having a period of p m − 1 , where, Tr p m | q ( ⋅ ) is the trace function over the sub extension field F q . It maps an element of the extension field F p m to an element of the sub extension field F q . After the trace calculation, a non-zero constant element A is added to the trace values. This non-zero A can be any arbitrary element within the sub extension field F q such as A ∈ { 1,2, ⋯ , q − 1 } . Then, the k-th power residue symbol is utilized for mapping the trace sequence T to a k-value sequence more specifically a multi-value sequence.

The authors recently started to consider the sub extension field F q during the sequence generation procedure, whereas, almost all our previous works on pseudo-random sequence [

This section explains some fundamental concepts of the finite field theory such as a primitive polynomial, trace function, k-th power residue symbol, and dual basis. Then, multi-value sequence is introduced along with its properties such as period, autocorrelation, cross-correlation, linear complexity, and distribution of bit patterns.

Consider a polynomial f ( x ) of degree m over prime field F p . If it is not factorized into smaller degree polynomials over the prime field F p , it is called an irreducible polynomial. Consider the smallest number e such that x e − 1 is divisible by f ( x ) over F p , it is known that e becomes a factor of p m − 1 . Then f ( x ) is especially called a primitive polynomial, when e is equal to p m − 1 . Its zero ω belongs to the extension field F p m and it becomes a primitive element in F p m that generates every non-zero element in F p m as its power ω i (for i = 0 , 1 , 2 , ⋯ , p m − 2 ). According to Fermat’s little theorem, the following property between F p m and its base field F p holds [

Property 1. Let g be a generator of F p m ∗ , g ( q − 1 ) / ( p − 1 ) becomes a non-zero element in prime field F p and is also a generator of F p ∗ . □

This work utilizes the trace function to map an element of the extension field X ∈ F p m to an element of the sub extension field x ∈ F q as,

List of symbols | |
---|---|

p | odd prime number |

m | positive integer, mainly denotes the extension degree |

m ′ | one of the factors of m |

q | power of the odd prime q = p m ′ |

k | prime factor of q − 1 such as k | ( q − 1 ) |

F p | odd characteristic prime field |

F p m | an extension field (base p and extension degree m) |

F q | sub extension field |

F q ∗ | multiplicative group of F q , excluding the 0 such as F q ∗ = F q − { 0 } |

f ( x ) | a primitive polynomial |

ω | root of an irreducible polynomial |

g | generator of a group |

A | an arbitrary element in F q ∗ |

Tr p m | q ( ⋅ ) | trace function maps F p m element to F q element |

ϵ k | primitive k-th root of unity |

f k ( ⋅ ) | mapping function maps F q element to F k element |

S | proposed sequence in this paper |

n | period of a sequence |

R S ( ⋅ ) | autocorrelation of a sequence S |

R S ^ , S ( ⋅ ) | cross-correlation between the sequences S and S ^ |

x = Tr p m | q ( X ) = ∑ i = 0 m m ′ − 1 X p i m ′ . (1)

A crucial point, the above trace becomes an arbitrary element in F q and the trace function has a linearity property over the sub extension field F q as follows,

Tr p m | q ( a X + b Y ) = a Tr p m | q ( X ) + b Tr p m | q ( Y ) , (2)

where a , b ∈ F q and X , Y ∈ F p m . In this paper, the following property is important [

Property 2. For each arbitrary element α ∈ F q , the number of elements in F p m whose trace with respect to F q becomes α is given by p m / q = p m − m ′ and the number of non-zero elements in F p m whose trace is zero is given by ( p m / q ) − 1 = p m − m ′ − 1 . □

As an extension of the Legendre symbol, this paper considers the k-th power residue symbol ( a / q ) k for an arbitrary element a in F q and a prime factor k of q − 1 as follows:

( a / q ) k = a ( q − 1 ) / k = ( 0 , if a = 0 , 1 = ϵ k 0 , else if a is a k -th PR in F q ∗ , ϵ k i , otherwise a isa k -th PNR in F q ∗ , (3)

where PR and PNR stand for Power Residue and Power Non-Residue respectively. The ϵ k is a primitive k-th root of unity that exists in F q and 0 ≤ i < k . It becomes a Legendre symbol when k = 2 [

To represent the exponent i in Equation (3), this paper uses the following notations and it should be noted that the following notation excludes the case of a = 0 .

i = log ϵ k ( ( a / q ) k ) = log ϵ k ( a ( q − 1 ) / k ) . (4)

This paper utilizes the power residue symbol to map an element in F q to an element in F k . Regarding the power residue symbol ( a / q ) k , the following property holds.

Property 3. For each i from 0 to k − 1 , the number of non-zero elements in F q such that

( a / q ) k = ϵ k i (5)

is given by ( q − 1 ) / k . □

Dual basis that is used for some proofs shown in this paper is defined as follows:

Definition 1. Let F p m be a finite field and F q be a finite extension of F p m . Then the two bases A = { α 0 , α 1 , ⋯ , α m − 1 } and B = { β 0 , β 1 , ⋯ , β m − 1 } of F q over F p m are said to be the dual (or complementary) bases if

Tr p m | q ( α i β j ) = ( 1, if i = j , 0, otherwise (6)

where 1 ≤ i , j ≤ m − 1 . □

The dual basis of an arbitrary basis is uniquely determined in [

Property 4. Let A and B be a basis and its dual basis of F q over F p m , respectively. Based on the definition of dual basis and the linearity of the trace function, if α l be a basis of A in F p m is a non-zero sub extension field element, then,

Tr p m | q ( α l β j ) = α l Tr p m | q ( β j ) = ( 1, if j = l , 0, otherwise, (7)

where 0 ≤ l , j ≤ m − 1 . Thus, when α l = 1 , Tr p m | q ( β l ) = 1 . □

This paper introduces a k-value sequence, more specifically a multi-value sequence as follows.

Let multi-value sequence S is denoted as

S = { s i } , i = 0 , 1 , 2 , ⋯ , n − 1 , ⋯ (8)

where s i ∈ { 0,1, ⋯ , k − 1 } and n be the period of the sequence such as s i = s n + i .

The autocorrelation of a sequence is a scope for measuring how much the original sequence varies from its each shift value. After observing this property some special characteristic about the sequence can be found such as its period, some pattern of it, and so on [

R S ( x ) = ∑ i = 0 n − 1 ϵ ˜ k s i + x − s i , (9)

where ϵ ˜ k is a primitive k-th root of unity over the complex number ℂ . It follows that,

R S ( 0 ) = ∑ i = 0 n − 1 ϵ ˜ k 0 = n . (10)

The cross-correlation is as important as the autocorrelation property. It is calculated between two different sequences of having the same period and it explains the sharing of some partial information between two sequences. In addition, if multiple sequences are used in any application (such as in security application), in that case, it is important to analyze the similarities between those sequences. To do so, the cross-correlation property needs to be evaluated. Considering the security aspects, the value of the cross-correlation preferred to be low because the higher value of cross-correlation, the more similar the sequences to each other [

R S ^ , S ( x ) = ∑ i = 0 n − 1 ϵ ˜ k s ^ i + x − s i , (11)

where ϵ ˜ k is a primitive k-th root of unity over the complex number ℂ [

The linear complexity (LC) of a sequence is closely related to how difficult it is to guess the next bit after observing the previous bits of a sequence. Since this paper considers k-value sequence with coefficients { 0,1, ⋯ , k − 1 } , the linear complexity of sequence S having a period of n is defined as follows.

LC ( S ) = n − deg ( gcd ( x n − 1, h S ( x ) ) ) , (12)

where h S ( x ) of S = { s i } is defined over F k as,

h S ( x ) = ∑ i = 0 n − 1 s i x i . (13)

It should be noted that gcd ( x n − 1, h S ( s ) ) in Equation (12) needs to be calculated over F k , where k is a prime number and k | ( q − 1 ) . It is said that linear complexity of pseudo-random sequence for security applications is preferred to be high.

From the viewpoint of security, the distribution of bit patterns is as important as the linear complexity. If a sequence holds uniform distribution of bit patterns, then it becomes difficult to guess the next bit after observing the previous bit patterns. For example, let’s assume a binary sequence having a period of 12 as S 12 = { 1,0,1,0,1,0,1,0,1,0,1,0 } . If we observe the 1-bit pattern in this sequence, then we can find that it has uniform distribution of 1 and 0. In other words, 1 and 0 appears same in number. However, when we check 2-bit patterns on S 12 , we find that it only has two type of patterns (10 and 01). In this case, we can easily predict the next bit patterns after observing the previous patterns. Therefore, it is also essential to evaluate the distribution of bit patterns of a sequence to confirm its randomness.

Let ω be a primitive element in the extension field F p m , n be the period of the proposed multi-value sequence, m be a composite number which denotes the extension degree of the primitive polynomial, and m ′ be one of the factors of m. This paper proposes the following sequence S by utilizing the trace function and k-th power residue symbol as follows:

S = { s i } , s i = f k ( Tr p m | q ( ω i ) + A / p ) k . (14)

Here k is a prime number as well as a factor of q − 1 such as k | ( q − 1 ) . To make the above equation more simpler, from here on Tr p m | q ( ⋅ ) will be represented as Tr ( ⋅ ) . Therefore, the above equation becomes,

S = { s i } , s i = f k ( Tr ( ω i ) + A / p ) k . (15)

Finally, a mapping function f k ( ⋅ ) is used to translate the vector sequence generated by the k-th power residue symbol to a multi-value sequence. The mapping function f k ( ⋅ ) is defined as follows:

f k ( x ) = ( 0, if x = 0, log ϵ k ( ( x / p ) k ) , otherwise . (16)

As mentioned in Section 2.3, f k ( x ) with a fixed ϵ k maps an arbitrary element x ∈ F q to an element in F k . For example, by utilizing the parameter p = 5 and k = 3 , the sequence values will be in the range of { 0,1,2 } , all of these values are the elements of F 3 . In addition, let us fixed [1 4 3] be as a 3-rd primitive root of unity in F q . Then, all of the sequence values can be represented as a exponent of this primitive root ϵ 3 . More details of this example are shown in

Property 5. Consider x , y ∈ F q . If x ≠ 0 and y ≠ 0 ,

f k ( x ) ± f k ( y ) = f k ( x y ± 1 ) . (17)

Based on Section 2.3 and Property 3, the mapping function also satisfies the following equation, it should be noted that, here C is a non-zero element in F q .

∑ v = 0 k − 1 ϵ ˜ k v = 0. (18a)

∑ u = 1 p − 1 ϵ ˜ k f k ( u ) = ∑ u = 1 p − 1 ϵ ˜ k f k ( u − 1 ) = ( p − 1 k ) ∑ v = 0 k − 1 ϵ ˜ k v = 0. (18b)

∑ u = 1 p − 1 ϵ ˜ k f k ( C u ) = ∑ u = 1 p − 1 ϵ ˜ k f k ( C u − 1 ) = 0. (18c)

This section, firstly mathematically prove the cross-correlation property of the proposed multi-value sequence, then it explains the autocorrelation property, and finally the period is introduced. Additionally, these properties are also observed based on some experimental results.

The cross-correlation is calculated between two different sequences of having the same period. These two different sequences S ^ and S can be defined as,

S ^ = { s ^ i | s ^ i = f k ( Tr ( ω i ) + B / p ) k } , (19a)

S = { s i | s i = f k ( Tr ( ω i ) + A / p ) k } . (19b)

Here, A and B are non-zero elements in F q . They can be represented with a generator g that exists in the sub extension field F q and they hold the following relation.

B = g h A , (20)

where the index term h satisfies 0 ≤ h ≤ q − 2 relation. In addition, here g needs

Output of Tr ( ⋅ ) | Output of ( a / p ) k | ϵ 3 = [ 1 4 3 ] | Output of f k ( ⋅ ) | |
---|---|---|---|---|

1 | [ | [3 1 2] | [1 4 3]^{2} | 2 |

2 | [ | [1 4 3] | [1 4 3]^{1} | 1 |

3 | [ | [3 1 2] | [1 4 3]^{ 2} | 2 |

4 | [ | [1 4 3] | [1 4 3]^{1} | 1 |

5 | [0 1 2] | [ | [1 4 3]^{0} | 0 |

6 | [0 2 4] | [ | [1 4 3]^{0} | 0 |

7 | [0 3 1] | [1 4 3] | [1 4 3]^{1} | 1 |

8 | [0 4 3] | [3 1 2] | [1 4 3]^{2} | 2 |

9 | [1 1 2] | [ | [1 4 3]^{0} | 0 |

10 | [1 2 4] | [3 1 2] | [1 4 3]^{2} | 2 |

11 | [1 3 1] | [ | [1 4 3]^{0} | 0 |

12 | [1 4 3] | [3 1 2] | [1 4 3]^{2} | 2 |

13 | [2 1 2] | [ | [1 4 3]^{0} | 0 |

14 | [2 2 4] | [1 4 3] | [1 4 3]^{1} | 1 |

15 | [2 3 1] | [3 1 2] | [1 4 3]^{2} | 2 |

16 | [2 4 3] | [ | [1 4 3]^{0} | 0 |

17 | [3 1 2] | [ | [1 4 3]^{0} | 0 |

18 | [3 2 4] | [3 1 2] | [1 4 3]^{2} | 2 |

19 | [3 3 1] | [3 1 2] | [1 4 3]^{2} | 2 |

20 | [3 4 3] | [1 4 3] | [1 4 3]^{1} | 1 |

21 | [4 1 2] | [ | 0 | 0 |

22 | [4 2 4] | [1 4 3] | [1 4 3]^{1} | 1 |

23 | [4 3 1] | [1 4 3] | [1 4 3]^{1} | 1 |

24 | [4 4 3] | [1 4 3] | [1 4 3]^{1} | 1 |

to be given by ω ( p m − 1 ) / ( q − 1 ) , which used in the following proofs^{2}. The cross-correlation of these two sequences S ^ and S is calculated as,

R S ^ , S ( x ) = ∑ i = 0 n − 1 ϵ ˜ k f k ( Tr ( ω i + x ) + g h A ) − f k ( Tr ( ω i ) + A ) , (21)

^{1}In this example, we fixed [1 4 3] as a 3^{rd} primitive root of unity that exists in F q . Therefore, every element can be represented as a power of this 3^{rd} primitive root ϵ 3 .

^{2}Since ω is a generator of F p m ∗ , therefore g = ω ( p m − 1 ) / ( q − 1 ) becomes a generator of F q ∗ .

where n is the period of these two sequences and according to the following section, it is given by p m − 1 . Furthermore, when h = 0 , then the value of A and B becomes exactly equal to each other, therefore, the cross-correlation becomes the autocorrelation of S .

Theorem 1. The cross-correlation between the sequence S ^ and S given by Equation (21) is as follows.

R S ^ , S ( x ) = ( p m − m ′ + ( p m − 1 − p m − m ′ ) ϵ ˜ k f k ( g h ) , if x = h n ¯ , p m − m ′ ( ϵ ˜ k f k ( A ( g h − g j ) ) + ϵ ˜ k − f k ( A ( 1 − g h − j ) ) − ϵ ˜ k f k ( g j ) ) − ϵ ˜ k f k ( g h ) , else if x = j n ¯ , p m − 2 m ′ − ϵ ˜ k f k ( g h ) , otherwise, (22)

where n ¯ = n / ( q − 1 ) = ( p m − 1 ) / ( q − 1 ) and h satisfies the relation in Equation (20) as well as 0 ≤ j ≠ h ≤ q − 2 . □

The proof for each case of Equation (22) is explained below. It should be noted that i holds the relation 0 ≤ i < n = ( p m − 1 ) and it is mainly appeared at summations. Furthermore, in the following section m / m ′ is denoted as r.

In this case, the cross-correlation between the sequences S ^ and S becomes as follows:

R S ^ , S ( x ) = ∑ i = 0 n − 1 ϵ ˜ k f k ( Tr ( ω i + h n ¯ ) + g h A ) − f k ( Tr ( ω i ) + A ) = ∑ i = 0 n − 1 ϵ ˜ k f k ( g h ( Tr ( ω i ) + A ) ) − f k ( Tr ( ω i ) + A ) . (23)

According to Property 5 and depending on the condition of whether or not Tr ( ω i ) + A = 0 , the above equation can be rewritten as follows:

R S ^ , S ( x ) = ∑ Tr ( ω i ) + A = 0 ϵ ˜ k f k ( g h ⋅ 0 ) − f k ( 0 ) + ∑ Tr ( ω i ) + A ≠ 0 ϵ ˜ k ( g h ( Tr ( ω i ) + A ) ) − f k ( Tr ( ω i ) + A ) . (24)

Thus, the above equation becomes as,

R S ^ , S ( x ) = ∑ Tr ( ω i ) + A = 0 ϵ ˜ k 0 + ∑ Tr ( ω i ) + A ≠ 0 ϵ ˜ k f k ( g h ) . (25)

It should be noted that g h ≠ 0 . Therefore, according to Property 2, the cross-correlation between the sequence S ^ and S for the case of x = h n ¯ holds the following relation.

R S ^ , S ( x ) = p m − m ′ + ( p m − 1 − p m − m ′ ) ϵ ˜ k f k ( g h ) . (26)

In this case, the cross-correlation between the sequences S ^ and S becomes as follows:

R S ^ , S ( x ) = ∑ i = 0 n − 1 ϵ ˜ k f k ( Tr ( ω i + j n ¯ ) + g h A ) − f k ( Tr ( ω i ) + A ) = ∑ i = 0 n − 1 ϵ ˜ k f k ( g j Tr ( ω i ) + g h A ) − f k ( Tr ( ω i ) + A ) . (27)

According to Property 5, depending on the condition whether or not Tr ( ω i ) + A = 0 and g j Tr ( ω i ) + g h A = 0 following relation is obtained.

R S ^ , S ( x ) = ∑ g j Tr ( ω i ) + g h A ≠ 0 Tr ( ω i ) + A = 0 ϵ ˜ k f k ( A ( g h − g j ) ) + ∑ g j Tr ( ω i ) + g h A = 0 Tr ( ω i ) + A ≠ 0 ϵ ˜ k − f k ( A ( 1 − g h − j ) ) + ∑ g j Tr ( ω i ) + g h A ≠ 0 Tr ( ω i ) + A ≠ 0 ϵ ˜ k f k ( ( g j Tr ( ω i ) + g h A ) ( Tr ( ω i ) + A ) − 1 ) . (28)

For example, if Tr ( ω i ) + A = 0 and j ≠ h , then,

g j Tr ( ω i ) + g h A = A ( g h − g j ) ≠ 0. (29)

Depending on Property 2, first and second summations in Equation (28) respectively becomes as follows:

∑ g j Tr ( ω i ) + g h A ≠ 0 Tr ( ω i ) + A = 0 ϵ ˜ k f k ( A ( g h − g j ) ) = p m − m ′ ϵ ˜ k f k ( A ( g h − g j ) ) , (30)

∑ g j Tr ( ω i ) + g h A = 0 Tr ( ω i ) + A ≠ 0 ϵ ˜ k − f k ( A ( 1 − g h − j ) ) = p m − m ′ ϵ ˜ k − f k ( A ( 1 − g h − j ) ) , (31)

where the following facts and conditions should be noted for the above two summations:

• In this paper, the parameter A is not 0 and A ∈ F q .

• The case of Tr ( ω i ) + A = 0 , g j Tr ( ω i ) + g h A ≠ 0 .

• While g j Tr ( ω i ) + g h A = 0 , Tr ( ω i ) + A ≠ 0 .

Assume, X i = Tr ( ω i ) + A ≠ 0 . Then the third summation in Equation (28) becomes as follows:

∑ g j Tr ( ω i ) + g h A ≠ 0 Tr ( ω i ) + A ≠ 0 ϵ ˜ k f k ( ( g j Tr ( ω i ) + g h A ) ( Tr ( ω i ) + A ) − 1 ) = ∑ g j Tr ( ω i ) + g h A ≠ 0 Tr ( ω i ) + A ≠ 0 ϵ ˜ k f k ( g j + A ( g h − g j ) X i − 1 ) . (32)

Now all of the possible values of X i ∈ F q needs to be consider to resolve Equation (32). According to Property 2 and considering the exceptions for the first and second summations in Equation (28), following relations are obtained,

# { i | X i = 0 } = p m − m ′ , (33a)

# { i | X i = A ( 1 − g − j ) } = p m − m ′ , (33b)

# { i | X i = A } = p m − m ′ − 1 , (33c)

# { i | X i = u } = p m − m ′ , (33d)

here 0 ≤ i < n and for each u ∈ q − { 0, A , A ( 1 − g h − j ) } . The cases of Equation (33a) and Equation (33b) respectively comply the first and second summations in Equation (28).

Furthermore, assume Y i = g j + A ( g h − g j ) X i − 1 this is the input of mapping function f k ( ⋅ ) as defined in Equation (32). Hence, considering the cases of X i = A ( 1 − g h − j ) and X i = 0 , the value of Y i in Equation (32) cannot be 0 and g j , respectively. These two cases already separated in Equation (28) as the first and second summations. As a consequence, Equation (32) can be rewritten as in Equation (34). In order to conform, the case of Y i = g j part (B) is added in Equation (34). Furthermore, part (C) in Equation (34) is for adjusting the number of cases of X i = A , which mentioned in Equation (33c). Therefore, (18b) holds at part A in Equation (34).

Hence, the cross-correlation of the sequence S ^ and S becomes as follows for the case of x = j n ¯ , j ≠ h ,

∑ g j Tr ( ω i ) + g h A ≠ 0 Tr ( ω i ) + A ≠ 0 ϵ ˜ k f k ( g j + A ( g h − g j ) X i − 1 ) = ( ϵ ˜ k f k ( g h ) − ϵ ˜ k f k ( g h ) ) + ( p m − m ′ ϵ ˜ k f k ( g j ) − p m − m ′ ϵ ˜ k f k ( g j ) ) + ∑ g j Tr ( ω i ) + g h A ≠ 0 Tr ( ω i ) + A ≠ 0 ϵ ˜ k f k ( g j + A ( g h − g j ) X i − 1 ) = [ ∑ g j Tr ( ω i ) + g h A ≠ 0 Tr ( ω i ) + A ≠ 0 ϵ ˜ k f k ( g j + A ( g h − g j ) X i − 1 ) + p m − m ′ ϵ ˜ k f k ( g j ) _ (B) + ϵ ˜ k f k ( g h ) _ (C) ] _ (A) − p m − m ′ ϵ ˜ k f k ( g j ) − ϵ ˜ k f k ( g h ) = 0 _ (A) − p m − m ′ ( ϵ ˜ k f k ( g j ) ) − ϵ ˜ k f k ( g h ) = − p m − m ′ ( ϵ ˜ k f k ( g j ) ) − ϵ ˜ k f k ( g h ) . (34)

R S ^ , S ( x ) = p m − m ′ ϵ ˜ k f k ( A ( g h − g j ) ) + p m − m ′ ϵ ˜ k − f k ( A ( 1 − g h − j ) ) − p m − m ′ ϵ ˜ k f k ( g j ) − ϵ ˜ k f k ( g h ) = p m − m ′ ( ϵ ˜ k f k ( A ( g h − g j ) ) + ϵ ˜ k − f k ( A ( 1 − g h − j ) ) − ϵ ˜ k f k ( g j ) ) − ϵ ˜ k f k ( g h ) . (35)

In this case, the cross-correlation between the sequences S ^ and S becomes as follows:

R S ^ , S ( x ) = ∑ i = 0 n − 1 ϵ ˜ k f k ( Tr ( ω i + x ) + g h A ) − f k ( Tr ( ω i ) + A ) . (36)

Here, x is not divisible by n ¯ and ω x does not belongs to F q . We assume the following basis G in F p m , by using this ω x as,

G = { ω x ,1, γ 2 , γ 3 , ⋯ , γ r − 1 } . (37)

Again let T be the dual basis of G .

T = { θ 0 , θ 1 , θ 2 , θ 3 , ⋯ , θ r − 1 } . (38)

Assume that ω i can be represented with θ as follows:

ω i = ∑ l = 0 r − 1 v i , l θ l . (39)

Then, ω i + x is given by

ω i + x = ∑ l = 0 r − 1 v i , l θ l ω x . (40)

Based on Property 4, initial value of ω i is as,

Tr ( ω i ) = v i , 1 . (41)

As previously mentioned that, W and B are the dual bases to each other, therefore Tr ( ω i + x ) can be expressed as follows:

Tr ( ω i + x ) = v i , 0 . (42)

After substituting these trace values, Equation (36) becomes as follows.

R S ^ , S ( x ) = ∑ i = 0 n − 1 ϵ ˜ k f k ( v i ,0 + g h A ) − f k ( v i ,1 + A ) . (43)

Based on Equation (18), the above equation is rewritten as,

R S ^ , S ( x ) = ∑ v i , 0 + g h A = 0 v i , 1 + A = 0 ϵ ˜ k 0 + ∑ v i , 0 + g h A = 0 v i , 1 + A ≠ 0 ϵ ˜ k − f k ( v i , 1 + A ) + ∑ v i , 0 + g h A ≠ 0 v i , 1 + A = 0 ϵ ˜ k f k ( v i , 0 + g h A ) + ∑ v i , 0 + g h A ≠ 0 v i , 1 + A ≠ 0 ϵ ˜ k f k ( ( v i , 0 + g h A ) ( v i , 1 + A ) − 1 ) . (44)

According to Equation (18b) and ω i holds the relation 0 ≤ i < n , which actually represents every non-zero element in F p m , therefore, the second and third summations holds the following relations.

∑ v i , 0 + g h A = 0 v i , 1 + A ≠ 0 ϵ ˜ k − f k ( v i , 1 + A ) = 0. (45a)

∑ v i , 0 + g h A ≠ 0 v i , 1 + A = 0 ϵ ˜ k f k ( v i , 0 + g h A ) = 0. (45b)

In addition, by considering the sub extension field F q and fixing the values of v i ,0 and v i ,1 the first summation holds the following relation as,

∑ v i , 0 + g h A = 0 v i , 1 + A = 0 ϵ ˜ k 0 = p m − 2 m ′ . (45c)

Considering the same calculation procedure of Equation (34), the fourth summation in Equation (44) becomes as follows:

∑ v i , 0 + g h A ≠ 0 v i , 1 + A ≠ 0 ϵ ˜ k f k ( ( v i , 0 + g h A ) ( v i , 1 + A ) − 1 ) = p m − 2 m ′ ∑ a = 1 p − 1 ∑ b = 1 p − 1 ϵ ˜ k f k ( a b − 1 ) − ϵ ˜ k f k ( 0 + g h A ) − f k ( 0 + A ) . (46)

Since ω i cannot represent the zero vector, the number of vectors such that v i , 0 = 0 and v i , 1 = 0 is one less than that of the other combinations like v i , 0 = 0 and v i , 1 = 1 . That is why, the last subtraction ϵ ˜ k f k ( 0 + g h A ) − f k ( 0 + A ) is required in Equation (46). According to the condition from Equation (18b), the first summation in Equation (46) becomes 0. Therefore, the following relation is obtained,

∑ v i , 0 + g h A ≠ 0 v i , 1 + A ≠ 0 ϵ ˜ k f k ( ( v i , 0 + g h A ) ( v i , 1 + A ) − 1 ) = − ϵ ˜ k f k ( g h ) . (47)

Therefore, the cross-correlation of the sequences S ^ and S becomes as follows for this case,

R S ^ , S ( x ) = p m − 2 m ′ − ϵ ˜ k f k ( g h ) . (48)

Finally, the cross-correlation of the sequences S ^ and S , that is in Equation (22), is proven.

If the value of h = 0 , then S ^ and S becomes the same sequence. In this case, the cross-correlation in Equation (22) becomes the autocorrelation after replacing the value h = 0 .

R S ( x ) = ( p m − 1, if x = h n ¯ , p m − m ′ ( ϵ ˜ k f k ( A ( 1 − g j ) ) + ϵ ˜ k − f k ( A ( 1 − g − j ) ) − ϵ ˜ k f k ( g j ) ) − 1, else if x = j n ¯ , p m − 2 m ′ − 1, otherwise . (49)

Corresponding to the above autocorrelation equation, the period of the proposed multi-value sequence explicitly given by p m − 1 .

This section experimentally observes the properties of the proposed sequence such as period, autocorrelation, and cross-correlation along with some examples. Throughout this section, | x | provides the absolute value of a complex number x. In addition, the notation S 3 denotes the proposed sequence with the parameter A = 3 .

Let f ( x ) = x 4 + 2 x 3 + 2 x 2 + 2 x + 2 be a primitive polynomial over F 5 . In this case, the period of this sequence becomes p m − 1 = 624 . Then the sequence S 3 is shown in Equation (50) and its autocorrelation becomes as follows and

S 3 = { 001000111010000000100000000110101001100011001001101110101011 010100001001001010000101001001101000110000100001110101101010 010000100000110111011110100111101100000010110001000001111001 100100100001100001001011110111011110001110111001010001110101 111100100111000110011000000011110000111110110000111110110110

000001101100011101000011100101010100111110001000100001110011 011110010110111010101000101110010000111001001101010100011111 010100001011101011010110111101101010001110000010010111101000

100101101101111010100000100001011001001001100001110000110000 111111110101010101100110110110111110100011010011111101100110 001001101100101001100110 } (50)

| R S 3 ( x ) | = ( 624, if x = 0 24, else if x = 26,78,104,130,156,182,234,286,312,338,390,442,468,494,520,546,598, 76, else if x = 52,208,260,364,416,572, 0, otherwise (51)

On the other hand, it should be noted that S 4 is different from S 3 and its autocorrelation is given as follows and

| R S 4 ( x ) | = ( 624, if x = 0 24, else if x = 26,78,104,130,56,182,234,286,312,338,390,442,468,494,520,546,598, 76, else if x = 52,208,260,364,416,572, 0, otherwise (52)

The cross-correlation of S 3 and S 4 becomes as follows and

| R S 3 , S 4 ( x ) | = ( 24, if x = 0,26,52,78,130,182,234,260,286,312,338,390,442,468,494,546,598, 76, else if x = 104,208,364,416,520,572, 624, else if x = 156, 0, otherwise (53)

Let f ( x ) = x 4 + 4 x 3 + 3 x 2 + 5 x + 3 be a primitive polynomial over F 7 . In this case, the period of the sequence becomes p m − 1 = 2400 .

By observing the experimental results, it is found that in every case, the cross-correlation graph has exactly q − 1 number of peaks. Among those, only one has a maximum value. For example, in

these q − 1 peaks the remaining part in the graph always holds a constant value of 0, which corresponds the case third case in Equation (22). It means that all this cross-correlation graph can be explained by Equation (22). It is also observed that by changing all the parameter values does not have any impact in the cross-correlation evaluation. On the other hand, as like the cross-correlation, the autocorrelation graph also has q − 1 number of peaks. Among them, only one holds the maximum value, the others have small values, the remaining part always holds a constant value of 1, and all these autocorrelation graphs can be explained by Equation (49).

Although nowadays multi-value sequence does not have enough application except the binary sequence (especially in security applications), therefore, in this section, the authors will emphasis on the binary case of their proposed sequence. Even though the authors proposed sequence is a multi-value sequence. but it can be easily mapped into binary sequence by setting the parameter value k = 2 . In this section the authors will introduce a comparison of their proposed sequence (binary case) with their previous work [

The autocorrelation of a sequence is a measure for how much the sequence differs from its each shift value. In addition, by evaluating this property some special characteristics about the sequence such as its period, some pattern of the sequence, and so on can be also found and the value of the autocorrelation always preferred to be as low as possible [

The unpredictability of a sequence can be measured by the length of the shortest Linear Feedback Shift Register (LFSR) which can generate the given sequence. This approach is particularly appealing since there exists an efficient procedure

(it is so called the Berlekamp-Massy algorithm [

The distribution of bit patterns is another important measure to check the randomness of a sequence. From the viewpoint of security, the distribution of bit patterns is as important as the linear complexity. If a sequence holds the uniform distribution of bit patterns, then it becomes difficult to guess the next bit after observing the previous bit patterns. After the experimental observation, it was found that the NTU sequence is not uniformly distributed. In other words, in case of binary NTU sequence, there is much difference in appearance between the 0 and 1. To improve this drawback, instead of prime field (which used in the NTU sequence generation procedure), the authors focused on the sub extension field during the sequence generation procedure in this research work. As a result, after utilizing the sub extension field, the distribution of bit patterns becomes close to uniform. This comparison is shown in the following

d | H w t ( b ( d ) ) | D S 15624 ( b ( d ) ) | % | D N T U 15624 ( b ( d ) ) | % |
---|---|---|---|---|---|

1 | 0 | 8124 | 51.99 | 9374 | 59.99 |

1 | 7500 | 48.01 | 6250 | 40.01 | |

2 | 0 | 4224 | 27.03 | 5624 | 35.99 |

1 | 3900 | 24.96 | 3750 | 24.00 | |

2 | 3600 | 23.04 | 2500 | 16.00 | |

3 | 0 | 2196 | 14.05 | 3374 | 21.59 |

1 | 2028 | 12.98 | 2250 | 14.40 | |

2 | 1872 | 11.98 | 1500 | 9.60 | |

3 | 1728 | 11.05 | 1000 | 6.40 | |

4 | 0 | 1140 | 7.29 | 2024 | 12.95 |

1 | 1056 | 6.75 | 1350 | 8.60 | |

2 | 972 | 6.22 | 900 | 5.76 | |

3 | 900 | 5.76 | 600 | 3.84 | |

4 | 828 | 5.29 | 400 | 2.56 |

b ( n ) , respectively. In terms of the distribution of bit patterns, the sequence defined over the sub extension field hold much better distribution (close to uniform) of 0 and 1 than the sequence defined over the prime field.

As mentioned previously, NTU sequence proposed in [

One of the most common applications of the pseudo-random binary sequence is in a stream cipher. Basically, stream cipher is divided into two classes: block cipher and stream cipher. Among these in case of block cipher, same key is used for both encryption and decryption of each block (≥64 bits) of data. On the other hand, in case of stream cipher, encryption and decryption are performed by the bit wise ⊕ (XOR) operation with a key stream. Here, the authors restrict the discussion of their proposed pseudo-random binary sequence in a stream cipher. An image of the stream cipher is shown in

The authors in this paper have proposed a multi-value sequence (including a binary sequence) by utilizing a primitive polynomial, trace function, k-th power residue symbol over the sub extension field. The notable outcomes of this

research work are as follows:

• This is an extension of our previous works [

• This work overcomes the shorter period shortcoming of our previous work [

• The period, autocorrelation, and cross-correlation properties regarding the proposed sequence are theoretically explained.

• The authors make a comparison in terms of autocorrelation, linear complexity and distribution of bit patterns properties with their previous work [

• According to the comparison results, the proposed sequence holds low correlation, high linear complexity, and much better distribution of bit patterns compared to our previous work [

• The proposed sequence can be a prominent candidate for stream cipher like cryptographic applications due to its exemplary properties.

As future works, the following points should be researched:

• Mathematically prove the linear complexity and distribution of bit patterns properties.

• To introduce more efficient calculation instead of the power residue calculation.

This work has been supported by JSPS KAKENHI Grant-in-Aid for Scientific Research (A) Number 16H01723.

The authors declare no conflicts of interest regarding the publication of this paper.

Ali, Md.A., Kodera, Y., Kusaka, T., Uehara, S., Nogami, Y. and Morelos-Zaragoza, R.H. (2019) Multi-Value Sequence Generated over Sub Extension Field and Its Properties. Journal of Information Security, 10, 130-154. https://doi.org/10.4236/jis.2019.103008