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 . As well as it should have many desirable characteristics such as a long period, low correlation, uniformly distributed bit patterns, high linear complexity, and statistical randomness  to become a prominent candidate for information security and cryptographic related applications  . The randomness regarding a sequence is considered as the key strength of the cryptographic systems . Considering this crucial point, it’s better to use some non-linear mathematical calculation during sequence generation. Additionally, the sequence must have randomness property. The major substance for randomness is independency of values (or lack of correlation), unpredictability (or lack of predictability), and uniform distribution (or lack of bias) . Along with these, there are some statistical tests available to judge the randomness of a sequence such as NIST, Diehard, ENT test . It is mandatory to evaluate the randomness of a sequence before utilizing them in any cryptosystems.
Other geometric sequences having prominent pseudo-random properties are the Mersenne Twister (MT)  , Blum-Blum-Shub (BBS)  , Legendre sequence  , maximum length sequence (M-sequence)  , and Sidelnikov sequence . Among those, the former two pseudo-random number generators (MT and BBS) are well known considering their applications in cryptography rather than the theoretical aspect. On the other hand, the latter sequences (Legendre sequence, M-sequence, and Sidelnikov sequence) are prominent geometric sequences regarding the theoretical aspect. Generally, the typical features of a pseudo-random sequence such as its period, correlation, linear complexity, and distribution of bit patterns cannot be theoretically proven. However, if a sequence is defined over the finite field, then those features are often proven. All these above-mentioned sequences generated based on some mathematics more specifically they are defined over the finite field. Therefore, most of their important properties are already theoretically proven. The authors are basically more interested in the theoretical aspects of a pseudo-random sequence rather than their applications in the cryptographic area. Therefore, the authors motivated in this research work by observing the theoretical features of the well-known Legendre sequence, M-sequence, and Sidelnikov sequence. Moreover, many researchers are also attracted by these theoretic aspects of these sequences. Our proposed sequence generated by the idea of the Legendre sequence and M-sequences, thus the authors thought that its properties can be theoretically proven and fortunately it proven.
Our previous work on binary sequence  uses a primitive polynomial, trace function, and Legendre symbol to generate a new variety of pseudo-random binary sequence. In brief, the previous sequence generation procedure is as follows: firstly, it utilizes a primitive polynomial over an odd characteristic field to generate a maximum length vector sequence as elements in , then applies the trace function to map the vectors to prime field elements, and finally uses the Legendre symbol to binarize the scalars to binary sequence. Our previous binary sequence  generated by combining the features of M-sequence and L-sequence. Some important properties such as period, autocorrelation, and linear complexity have been theoretically proven in our previous work. Our previous works on multi-value sequence   utilizes a primitive polynomial, trace function, and power residue symbol over odd characteristic field. Some important features of the sequence such as period, autocorrelation, and cross-correlation are theoretically proven in our previous work. The authors previous works on the binary sequence  , signed binary sequence  , and multi-value sequence  are considered in the prime field more specifically, the trace function maps an element of the extension field to an element of the prime field . Our previous work on multi-value sequence  considered on the sub extension field characterized by four parameters however it has a shorter sequence period of
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 . 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 over the extension field . It is well known that using the primitive polynomial makes it possible to generate a maximum length vector sequence over . Let be a zero of the primitive polynomial and it’s a primitive element in . Then the sequence
becomes a maximum length sequence of having a period of , where, is the trace function over the sub extension field . It maps an element of the extension field to an element of the sub extension field . 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 such as . Then, the k-th power residue symbol is utilized for mapping the trace sequence to a k-value sequence more specifically a multi-value sequence.
The authors recently started to consider the sub extension field during the sequence generation procedure, whereas, almost all our previous works on pseudo-random sequence    are considered in the prime field . The trace calculation is an important step during our proposed sequence generation procedure. It should be noted that in case of prime field , the trace maps extension field elements to prime field elements and the possible range of trace outputs are . On the other hand, in case of sub extension field , the trace maps extension field elements to sub extension field elements and possible range of trace outputs are . Therefore, the sub extension field allows more variations in the trace values and from the theoretical perspective, this flexibility contributes to the betterment of a sequence properties. Thus, from this point of view it’s a new dimension in this research area. Some of the notable contributions of the authors in this paper are: this work is an extension of our previous works    ; if the parameter k satisfies the condition , then it also includes our previous work  ; this work overcomes the shorter period shortcoming of our previous work  by adding one more additional parameter A; the period, autocorrelation, and cross-correlation properties regarding the proposed sequence are explained both theoretically and experimentally; this work also makes a comparison in terms of autocorrelation, linear complexity, and distribution of bit patterns, according to the comparison results, it was found that the proposed sequence holds low correlation, high linear complexity, and much better distribution of bit patterns compared to our previous work . There are a lot of symbols used in this paper, thus a brief introduction about those symbols are introduced in Table 1.
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.
2.1. Primitive Polynomial
Consider a polynomial of degree m over prime field . If it is not factorized into smaller degree polynomials over the prime field , it is called an irreducible polynomial. Consider the smallest number e such that is divisible by over , it is known that e becomes a factor of . Then is especially called a primitive polynomial, when e is equal to . Its zero belongs to the extension field and it becomes a primitive element in that generates every non-zero element in as its power (for ). According to Fermat’s little theorem, the following property between and its base field holds .
Property 1. Let be a generator of , becomes a non-zero element in prime field and is also a generator of . □
2.2. Trace Function
This work utilizes the trace function to map an element of the extension field to an element of the sub extension field as,
Table 1. List of symbols used in this paper.
A crucial point, the above trace becomes an arbitrary element in and the trace function has a linearity property over the sub extension field as follows,
where and . In this paper, the following property is important .
Property 2. For each arbitrary element , the number of elements in whose trace with respect to becomes is given by and the number of non-zero elements in whose trace is zero is given by . □
2.3. k-th Power Residue Symbol
As an extension of the Legendre symbol, this paper considers the k-th power residue symbol for an arbitrary element a in and a prime factor k of as follows:
where PR and PNR stand for Power Residue and Power Non-Residue respectively. The is a primitive k-th root of unity that exists in and . It becomes a Legendre symbol when  and if , it becomes our previous work . Note that, for a non-zero element a and a fixed , the exponent i in Equation (3) is uniquely determined in the range of . Moreover, since and k is a prime number in this paper, the exponents can be dealt with as elements in . This symbol is basically used for checking whether or not a is a k-th PR over as shown above. The output of the k-th power residue symbol can be represented as an exponent of , where is a k-th primitive root. This paper uses k-th power residue symbol to translate a trace sequence over to a k values multi-value sequence such as , where .
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 .
This paper utilizes the power residue symbol to map an element in to an element in . Regarding the power residue symbol , the following property holds.
Property 3. For each i from 0 to , the number of non-zero elements in such that
is given by . □
2.4. Dual Bases
Dual basis that is used for some proofs shown in this paper is defined as follows:
Definition 1. Let be a finite field and be a finite extension of . Then the two bases and of over are said to be the dual (or complementary) bases if
where . □
The dual basis of an arbitrary basis is uniquely determined in . In this paper, the following property is important.
Property 4. Let and be a basis and its dual basis of over , respectively. Based on the definition of dual basis and the linearity of the trace function, if be a basis of in is a non-zero sub extension field element, then,
where . Thus, when , . □
2.5. Multi-Value Sequence and Its Properties
This paper introduces a k-value sequence, more specifically a multi-value sequence as follows.
2.5.1. Notation and Period
Let multi-value sequence is denoted as
where and n be the period of the sequence such as .
2.5.2. Autocorrelation and Cross-Correlation
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 . The autocorrelation of sequence shifted by x is generally defined as follows:
where is a primitive k-th root of unity over the complex number . It follows that,
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 . Let be a different sequence of having a period of n. Then, the cross-correlation at x shifted is generally defined by the following equation as,
where is a primitive k-th root of unity over the complex number .
2.5.3. Linear Complexity
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 , the linear complexity of sequence having a period of n is defined as follows.
where of is defined over as,
It should be noted that in Equation (12) needs to be calculated over , where k is a prime number and . It is said that linear complexity of pseudo-random sequence for security applications is preferred to be high.
2.5.4. Distribution of Bit Patterns
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 . 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 , 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.
3. Proposed Multi-Value Sequence
Let be a primitive element in the extension field , 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 be one of the factors of m. This paper proposes the following sequence by utilizing the trace function and k-th power residue symbol as follows:
Here k is a prime number as well as a factor of such as . To make the above equation more simpler, from here on will be represented as . Therefore, the above equation becomes,
Finally, a mapping function is used to translate the vector sequence generated by the k-th power residue symbol to a multi-value sequence. The mapping function is defined as follows:
As mentioned in Section 2.3, with a fixed maps an arbitrary element to an element in . For example, by utilizing the parameter and , the sequence values will be in the range of , all of these values are the elements of . In addition, let us fixed [1 4 3] be as a 3-rd primitive root of unity in . Then, all of the sequence values can be represented as a exponent of this primitive root . More details of this example are shown in Table 2. This mapping function holds the following property.
Property 5. Consider . If and ,
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 .
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 and can be defined as,
Here, A and B are non-zero elements in . They can be represented with a generator g that exists in the sub extension field and they hold the following relation.
where the index term h satisfies relation. In addition, here g needs
Table 2. Mapping procedure of for 24 different trace values1.
to be given by , which used in the following proofs2. The cross-correlation of these two sequences and is calculated as,
1In this example, we fixed [1 4 3] as a 3rd primitive root of unity that exists in . Therefore, every element can be represented as a power of this 3rd primitive root .
2Since is a generator of , therefore becomes a generator of .
where n is the period of these two sequences and according to the following section, it is given by . Furthermore, when , then the value of A and B becomes exactly equal to each other, therefore, the cross-correlation becomes the autocorrelation of .
Theorem 1. The cross-correlation between the sequence and given by Equation (21) is as follows.
where and h satisfies the relation in Equation (20) as well as . □
The proof for each case of Equation (22) is explained below. It should be noted that i holds the relation and it is mainly appeared at summations. Furthermore, in the following section is denoted as r.
3.1.1. The Case of
In this case, the cross-correlation between the sequences and becomes as follows:
According to Property 5 and depending on the condition of whether or not , the above equation can be rewritten as follows:
Thus, the above equation becomes as,
It should be noted that . Therefore, according to Property 2, the cross-correlation between the sequence and for the case of holds the following relation.
3.1.2. The Case of ,
In this case, the cross-correlation between the sequences and becomes as follows:
According to Property 5, depending on the condition whether or not and following relation is obtained.
For example, if and , then,
Depending on Property 2, first and second summations in Equation (28) respectively becomes as follows:
where the following facts and conditions should be noted for the above two summations:
• In this paper, the parameter A is not 0 and .
• The case of , .
• While , .
Assume, . Then the third summation in Equation (28) becomes as follows:
Now all of the possible values of 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,
here and for each . The cases of Equation (33a) and Equation (33b) respectively comply the first and second summations in Equation (28).
Furthermore, assume this is the input of mapping function as defined in Equation (32). Hence, considering the cases of and , the value of in Equation (32) cannot be 0 and , 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 part (B) is added in Equation (34). Furthermore, part (C) in Equation (34) is for adjusting the number of cases of , which mentioned in Equation (33c). Therefore, (18b) holds at part A in Equation (34).
Hence, the cross-correlation of the sequence and becomes as follows for the case of ,
In this case, the cross-correlation between the sequences and becomes as follows:
Here, x is not divisible by and does not belongs to . We assume the following basis in , by using this as,
Again let be the dual basis of .
Assume that can be represented with as follows:
Then, is given by
Based on Property 4, initial value of is as,
As previously mentioned that, and are the dual bases to each other, therefore can be expressed as follows:
After substituting these trace values, Equation (36) becomes as follows.
Based on Equation (18), the above equation is rewritten as,
According to Equation (18b) and holds the relation , which actually represents every non-zero element in , therefore, the second and third summations holds the following relations.
In addition, by considering the sub extension field and fixing the values of and the first summation holds the following relation as,
Considering the same calculation procedure of Equation (34), the fourth summation in Equation (44) becomes as follows:
Since cannot represent the zero vector, the number of vectors such that and is one less than that of the other combinations like and . That is why, the last subtraction 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,
Therefore, the cross-correlation of the sequences and becomes as follows for this case,
Finally, the cross-correlation of the sequences and , that is in Equation (22), is proven.
3.2. Autocorrelation and Period
If the value of , then and becomes the same sequence. In this case, the cross-correlation in Equation (22) becomes the autocorrelation after replacing the value .
Corresponding to the above autocorrelation equation, the period of the proposed multi-value sequence explicitly given by .
4. Examples and Discussions
This section experimentally observes the properties of the proposed sequence such as period, autocorrelation, and cross-correlation along with some examples. Throughout this section, provides the absolute value of a complex number x. In addition, the notation denotes the proposed sequence with the parameter .
Let be a primitive polynomial over . In this case, the period of this sequence becomes . Then the sequence is shown in Equation (50) and its autocorrelation becomes as follows and Figure 1 shows its autocorrelation graph.
Figure 1. with , and .
On the other hand, it should be noted that is different from and its autocorrelation is given as follows and Figure 2 shows its autocorrelation graph.
The cross-correlation of and becomes as follows and Figure 6 shows its cross-correlation graph.
Let be a primitive polynomial over . In this case, the period of the sequence becomes . Figure 3, Figure 4, and Figure 5 show the autocorrelation graphs of , , and the cross-correlation between the and , respectively.
By observing the experimental results, it is found that in every case, the cross-correlation graph has exactly number of peaks. Among those, only one has a maximum value. For example, in Figure 6, the maximum cross-correlation value is 624, which corresponds to the first case of , the remaining smaller peaks conform the second case of , and except
Figure 2. with , and .
Figure 3. with , and .
Figure 4. with , and .
Figure 5. with , and .
Figure 6. with , and .
these 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 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).
5. Comparison with Previous Work
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 . In this section the authors will introduce a comparison of their proposed sequence (binary case) with their previous work  in terms of autocorrelation, linear complexity, and distribution of bit patterns properties. In this section, the authors previous sequence proposed in  will be called as NTU (Nogami-Tada-Uehara) sequence.
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 autocorrelation of the proposed sequence (defined over sub extension field) and our previous sequence (NTU) (defined over prime field) is shown in Figure 7 and Figure 8, respectively. By observing their autocorrelation graph, it was found that on one hand, the number of peak values is increases in the sub field sequence, on the other hand, the difference between the maximum peak value with the smaller peak values are much smaller in the proposed sequence compared to our previous sequence. Moreover, in the proposed sequence except the peaks remaining autocorrelation value always remains at 0. It should be noted that in case of correlation evaluation, the less difference between the peak values are more crucial rather than the number of peaks .
5.2. Linear Complexity
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
Figure 7. Autocorrelation of proposed sequence.
Figure 8. Autocorrelation of NTU sequence.
(it is so called the Berlekamp-Massy algorithm  ) for finding the shortest LFSR. This length is referred as the linear complexity associated with the sequence. The linear complexity property regarding a sequence is an important parameter which tells how difficult it is to predict the next bit pattern by observing the previous bit pattern of a sequence. Thus, the linear complexity of a sequence is always preferred to be high. The linear complexity of the proposed sequence (defined over sub extension field) and our previous sequence (NTU) (defined over prime field) is shown in Figure 9 and Figure 10, respectively. By observing their linear complexity graph, it was found that the proposed sequence (which defined over the sub extension field) always hold high linear complexity compared to the NTU sequence. In other words, in terms of linear complexity the sequence defined over the sub extension field hold higher linear complexity than the sequence defined over the prime field.
5.3. Distribution of Bit Patterns
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 Table 3. In the following table, , , and denotes a bit pattern b of length d, the hamming weight of the bit pattern b, and the number of appearances of
Figure 9. LC of the proposed sequence.
Figure 10. LC of the NTU sequence.
Table 3. Comparison in bit distribution between the sub field binary sequence and NTU sequence.
, 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  is defined over the prime field and proposed sequence in this paper is defined over the sub extension field. After the comparison results it is concluded that in terms of correlation the proposed sequence holds low correlation compared to NTU sequence; about linear complexity proposed sequence possesses high linear complexity than NTU sequence; regarding the distribution of bit patterns proposed sequence hold much better distribution of bit patterns (close to uniform) than NTU sequence.
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 Figure 11. Few important considerations during the design of a stream cipher are the key (which used for both encryption and decryption) should have large period, good randomness, and unpredictability properties due to the usage of same key in both encryption and decryption. Here, the encryption is carried out by applying a bit-wise (XOR) operation between the plain-text of byte stream M and encryption key K. Then, the cipher-text C transmitted through a network. On the other hand, during the decryption, after the bit-wise operation between the cipher-text C and the same key K we will get the original plain-text M. In a stream cipher, a lot of sequences are assigned to several users, respectively. If these sequences have some correlation, then it will make some security vulnerabilities. Under this circumstance, it is important to observe the cross-correlation property between several sequences. Additionally, its linear complexity and distribution of bit patterns needs to be high and uniform, respectively to confirm its randomness. The authors proposed method can generate a long period pseudo-random sequence with typical auto and cross-correlation, high linear complexity, and almost uniformly distributed bit patterns features. After observing the experimental and comparison results, it can be concluded that the authors proposed sequence which defined over the sub extension field can be a prominent candidate for a stream cipher like applications.
6. Conclusions and Future Works
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
Figure 11. Application of the proposed sequence in stream cipher.
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.