This paper focuses on a pseudorandom number generator called an NTU sequence for use in cryptography. The generator is defined with an m-sequence and Legendre symbol over an odd characteristic field. Since the previous researches have shown that the generator has maximum complexity; however, its bit distribution property is not balanced. To address this drawback, the author introduces dynamic mapping for the generation process and evaluates the period and some distribution properties in this paper.

The authors have proposed a multi-value sequence called an NTU sequence which is generated by a trace function and the Legendre symbol over a finite field. Most of the properties for NTU sequence such as period, linear complexity, autocorrelation, and cross-correlation have been theoretically shown in our previous work. However, the distribution of digit patterns, which is one of the most important features for security applications, has not been shown yet. In this paper, the distribution has been formulated with a theoretic proof by focusing on the number of 0's contained in the digit pattern.

This paper proposes a new approach for generating pseudo random multi-valued (including binary-valued) sequences. The approach uses a primitive polynomial over an odd characteristic prime field ${p}$, where p is an odd prime number. Then, for the maximum length sequence of vectors generated by the primitive polynomial, the trace function is used for mapping these vectors to scalars as elements in the prime field. Power residue symbol (Legendre symbol in binary case) is applied to translate the scalars to k-value scalars, where k is a prime factor of p-1. Finally, a pseudo random k-value sequence is obtained. Some important properties of the resulting multi-valued sequences are shown, such as their period, autocorrelation, and linear complexity together with their proofs and small examples.

Let p be an odd characteristic and m be the degree of a primitive polynomial f(x) over the prime field Fp. Let ω be its zero, that is a primitive element in F*pm, the sequence S={si}, si=Tr(ωi) for i=0,1,2,… becomes a non-binary maximum length sequence, where Tr(·) is the trace function over Fp. On this fact, this paper proposes to binarize the sequence by using Legendre symbol. It will be a class of geometric sequences but its properties such as the period, autocorrelation, and linear complexity have not been discussed. Then, this paper shows that the generated binary sequence (geometric sequence by Legendre symbol) has the period n=2(pm-1)/(p-1) and a typical periodic autocorrelation. Moreover, it is experimentally observed that its linear complexity becomes the maximum, that is the period n. Among such experimental observations, especially in the case of m=2, it is shown that the maximum linear complexity is theoretically proven. After that, this paper also demonstrates these properties with a small example.