This paper presents a new method to derive the phase difference between n-tuples of an m-sequence over GF(p) of period pn-1. For the binary m-sequence of the characteristic polynomial f(x)=xn+xd+1 with d=1,2c or n-2c, the explicit formulas of the phase difference from the initial n-tuple are efficiently derived by our method for specific n-tuples such as that consisting of all 1's and that cosisting of one 1 and n-1 0's, although the previously known formula exists only for that consisting of all 1's.

The value distribution of the partial autocorrelation of periodic sequences is important for the evaluation of the sequence performances when sequences of long period are used. But it is difficult to find the exact value distribution of the autocorrelation in general. Therefore we derived some properties of the partial autocorrelation for binary m-sequences which may be used to find the exact value distribution.

Recently, the small set of nonbinary Kasami sequences was presented and their correlation properties were clarified by Liu and Komo. The family of nonbinary Kasami sequences has the same periodic maximum nontrivial correlation as the family of Kumar-Moreno sequences, but smaller family size. In this paper, first it is shown that each of the nonbinary Kasami sequences is unbalanced. Secondly, a new family of nonbinary sequences obtained from modified Kasami sequences is proposed, and it is shown that the new family has the same maximum nontrivial correlation as the family of nonbinary Kasami sequences and consists of the balanced nonbinary sequences.

It is known that a family of p-ary bent sequences, whose elements take values of GF (p) with a prime p, possesses low periodic correlation properties and high linear span. Firstly such a family is shown to consist of balanced sequences in the sense that the frequency of appearances in one period is the same for each nonzero element and once less for zero element. Secondly the exact distribution of the periodic correlation values is given for the family.

A self-complementary basis of a finite field corresponds to the orthonormal basis of a vector metric space. This paper presents a theorem that GF (24m) has no self-complementary normal bases over GF (2) if m is odd, which was recently conjectured by one of the present authors.

An approximate equation of the odd periodic correlation distribution for the family of binary sequences is derived from the exact even periodic correlation distribution. The distribution means the probabilities of correlation values which appear among all the phase-shifted sequences in the family. It is shown that the approximate distribution is almost the same as the computational result of some family such as the Gold sequences with low even periodic correlation magnitudes, or the Kasami sequences, the bent sequences with optimal even periodic correlation properties in the sense of the Welch's lower bound. It is also shown that the odd periodic correlation distribution of the family with optimal periodic correlation properties is not the Gaussian distribution, but that of the family of the Gold sequences with short period seems to be similar to the Gaussian distribution.

Recently two interesting conjectures on the linear complexity of binary complementary sequences of length 2nN0 were given by Karkkainen and Leppanen when those sequences are considered as periodic sequences with period 2nN0, where those sequences are constructed by successive concatenations or successive interleavings from a pair of kernel complementary sequences of length N0. Their conjectures were derived from numerical examples and suggest that those sequences have very large linear complexities. In this paper we give the exact formula of characteristic polynomials for those complementary sequences and show that their conjectures are true.

It is shown that we can simultaneously make both of Zech's logarithm table and trace table in a finite field by using a feedback shift register which generates a pseudo-random sequence. Convenient method for the initial loading of the feedback shift register is given.

In ordinary digital signature schemes, anyone can verify signatures with signer's public key. However it is not necessary for anyone to be convinced a justification of signer's dishonorable message such as a bill. It is enough for a receiver only to convince outsiders of signature's justification if the signer does not execute a contract. On the other hand there exist messages such as official documents which will be first treated as limited verifier signatures but after a few years as ordinary digital signatures. We will propose a limited verifier signature scheme based on Horster-Michels-Petersen's authenticated encryption schemes, and show that our limited verifier signature scheme is more efficient than Chaum-Antwerpen undeniable signature schemes in a certain situation. And we will propose a convertible limited verifier signature scheme based on our limited verifier signature scheme, and show that our convertible limited verifier signature scheme is more efficient than Boyar-Chaum-Damg rd-Pedersen convertible undeniable signature schemes in a certain situation.

In this paper, we will show that some families of periodic sequences over Z4 and Z8 with period multiple of 2r-1 generated by r-th degree basic primitive polynomials assorted by the root of each polynomial, and give the exact distribution of sequences for each family. We also point out such an instability as an extreme increase of their linear complexities for the periodic sequences by one-symbol substitution, i.e., from the minimum value to the maximum value, for all the substitutions except one.

A self-complementary basis of a finite field corresponds to the orthonormal basis of a vector metric space. Seroussi and Lempel showed that a finite field GF (qn) has a self-complementary basis over GF (q) if and only if either q is even or both q and n are odd. In this paper, firstly we show that by using the complementary basis of a polynomial basis we can write a self-complementary basis explicitly. Since a polynomial basis and a normal basis are the most popular bases in finite fields, in this paper we consider whether a polynomial basis or a normal basis can be self-complementary. Secondly we show that any polynomial basis can not be self-complementary. Thirdly we tabulate the numbers of all the different self-complementary normal bases of GF (qn) over GF (q) for various q and n. From this table we present a conjecture concerning the existence of nonexistence of self-complementary normal bases.

Firstly we show a usuful property of the fast algorithm for computing linear complexities of p-ary periodic sequences with period pn (p: a prime). Secondly the property is successfully applied to obtain the value distribution of the linear complexity for p-ary periodic sequences with period pn.

Relations between well-known bounds for the minimum distance of binary cyclic codes such as BCH bound (dBCH), HT bound (dHT) and new bounds dA, dB proposed recently by Shen et al. are investigated. We prove firstly dBCH dA and secondly dHT dB. We also give binary cyclic codes which satisfy dA dHT.

From a sequence {ai}i0 over GF(p) with period pn-1 we can obtain another periodic sequence {i}i0 with period pn-2 by deleting one symbol at the end of each period. We will give the bounds (upper bound and lower bound) of linear complexity of {i}i0 as a typical example of instability of linear complexity. Derivation of the bounds are performed by using the relation of characteristic polynomials between {ai}i0 and {ai(j)}i0={ai+j}i0, jGF(p){0}. For a binary m-sequence {ai}i0 with period 2n-1, n-1 a prime, we will give the explicit formula for the characteristic polynomial of {i}i0.

The maximum order complexity (MOC) of a sequence is a very natural generalization of the well-known linear complexity (LC) by allowing nonlinear feedback functions for the feedback shift register which generates a given sequence. It is expected that MOC is effective to reduce such an instability of LC as an extreme increase caused by the minimum changes of a periodic sequence, i. e. , one-symbol substitution, one-symbol insertion or one-symbol deletion per each period. In this paper we will give the bounds (lower and upper bounds) of MOC for the minimum changes of an m-sequence over GF(q) with period qn-1, which shows that MOC is much more natural than LC as a measure for the randomness of sequences in this case.

A simple and practical method for arithmetic computations in a finite field GF (pn) is presented. Since number of elements of GF (pn) is pn, the method uses representation of a field element as an integer modulo pn. The method also uses log and antilog tables. Only one n-th of memories are required to store the log and antilog tables of this paper in comparison with ordinary log and antilog tables. It is not necessary to compute by using vectors. It is also shown that Zech's logarithm defined by Conway can be easily computed by using the log and antilog tables of this paper. The results of this paper are useful for decoding error-correcting cyclic codes.

From a GF(q) sequence {ai}i0 with period qn - 1 we can obtain new periodic sequences {ai}i0 with period qn by inserting one symbol b GF(q) at the end of each period. Let b0 = Σqn-2 i=0 ai. It Is first shown that the linear complexity of {ai}i0, denoted as LC({ai}) satisfies LC({ai}) = qn if b -b0 and LC({ai}) qn - 1 if b = -b0 Most of known sequences are shown to satisfy the zero sum property, i.e., b0 = 0. For such sequences satisfying b0 = 0 it is shown that qn - LC({ai}) LC({ai}) qn - 1 if b = 0.