On Period of Fibonacci Sequence in Finite Rings with Identity of Order P^2

In this paper, we obtain the period of generalized Fibonacci sequence in finite rings with identity of order p2 by using equality recursively defined by Fn＋2 = A1Fn＋1 ＋ A0Fn, for n ≥ 0, where F0 = 0 （ the zero of the ring）, F1 = 1 （the identity of the ring） and A0 , A1 are generators elements of finite rings with identity of order p2. Also, we get some results between the period of generalized Fibonacci sequence in the finite rings oforderp2 and characteristic of these rings.

GMW sequences over Galois rings and their linear complexities

A new family of GMW sequences over an arbitrary Galois ring was defined by using the trace functions and permutations.This generalizes the concept of GMW sequences over finite fields.Utilizing the Fourier representation,we derived an estimate of the linear complexities of this family of GMW sequences.And the result shows that such sequences have large linear complexities.

INJECTIVE MAPS ON PRIMITIVE SEQUENCES OVER Z/(p^e)

Let Z/（p^e） be the integer residue ring modulo p^e with p an odd prime and integer e ≥ 3. For a sequence a over Z/（p^e）, there is a unique p-adic decomposition a- = a-0 ＋a-1 .p ＋… ＋ a-e-l .p^e-1 where each a-i can be regarded as a sequence over Z/（p）, 0 ≤ i ≤ e - 1. Let f（x） be a primitive polynomial over Z/（p^e） and G＇（f（x）,p^e） the set of all primitive sequences generated by f（x） over Z/（p^e）. For μ（x） ∈ Z/（p）[x] with deg（μ（x）） ≥ 2 and gad（1 ＋ deg（μ（x））,p- 1） = 1, setφe-1 （x0, x1,… , xe-1） = xe-1. [μ（xe-2） ＋ ηe-3（x0, X1,…, xe-3）] ＋ ηe-2（x0, X1,…, xe-2） which is a function of e variables over Z/（p）. Then the compressing mapφe-1 ： G＇（f（x）,p^e） → （Z/（p））^∞ ,a-→φe-1（a-0,a-1, … ,a-e-1） is injective. That is, for a-,b-∈ G＇（f（x）,p^e）, a- = b- if and only if φe-1 （a-0,a-1, … ,a-e-1） = φe-1（b-0, b-1,… ,b-e-1）. As for the case of e = 2, similar result is also given. Furthermore, if functions φe-1 and ψe-1 over Z/（p） are both of the above form and satisfy φe-1（a-0,a-1,…,a-e-1）=ψe-1（b-0, b-1,… ,b-e-1） for a-,b-∈G＇（f（x）,p^e）, the relations between a- and b-, φe-1 and ψe-1 are discussed

On the Judgement of Full-Period Sequences and a Novel Congruential Map with Double Modulus on Z(p^n)

This paper studies the judgement problem of full-period maps on Z(p^n) and proposes a novel congruential map with double modulus on Z(p^n). The full-period properties of the sequences generated by the novel map are studied completely. We prove some theorems including full-period judgement theorem on Z(p^n) and validate them by some numerical experiments. In the experiments, full-period sequences are generated by a full-period map on Z(p^n). By the binarization, full-period sequences are transformed into binary sequences. Then, we test the binary sequences with the NIST SP 800-22 software package and make the poker test. The passing rates of the statistical tests are high in NIST test and the sequences pass the poker test. So the randomness and statistic characteristics of the binary sequences are good. The analysis and experiments show that these full-period maps can be applied in the pseudo-random number generation(PRNG), cryptography, spread spectrum communications and so on.

The 0 ,1 - Distribution of the First CoordinateSequences Derived from ML- Sequences over Z/(2~e)

The 0,1 distribution of the first coordinate sequences derived from the maximal lenght sequences (ML sequences) over Z/(2~e) is exactly given.

Polynomial Splitting Ring and Root Representation of Linear Recurring Sequences Over Z|(p^e)

The concept of the splitting ring of the polynomial over ring Z(pe) is introduced and the factomation of polynomials and the properties df polynomial roots are discussed. By using these results and the structure of sequence families, it is shown that the terms of a linear recurring sequence over Z/(pe) may be represented by the roots of its characteristic polynomial and the representation is uniquely determined by the sequence.

Periods of polynomials over a Galois ring

The period of a monic polynomial over an arbitrary Galois ring GR(pe,d) is theoretically determined by using its classical factorization and Galois extensions of rings. For a polynomial f(x) the modulo p remainder of which is a power of an irreducible polynomial over the residue field of the Galois ring, the period of f(x) is characterized by the periods of the irreducible polynomial and an associated polynomial of the form (x-1)m+pg(x). Further results on the periods of such associated polynomials are obtained, in particular, their periods are proved to achieve an upper bound value in most cases. As a consequence, the period of a monic polynomial over GR(pe,d) is equal to pe-1 times the period of its modulo p remainder polynomial with a probability close to 1, and an expression of this probability is given.

Negacyclic codes over Galois rings of characteristic 2a

Abstract We investigate negacyclic codes over the Galois ring GR（2a,m） of length N = 2kn, where n is odd and k≥0. We first determine the structure of u-constacyclic codes of length n over the finite chain ring GR（2a, m）[u]/〈u2k ＋ 1〉. Then using a ring isomorphism we obtain the structure of negacyclic codes over GR（2a, m） of length N = 2kn （n odd） and explore the existence of self-dual negacyclic codes over GR（2a, m）. A bound for the homogeneous distance of such negacvclic codes is also given.

Constructions on Approximately Mutually Unbiased Bases by Galois Rings

Several new series of approximately mutually unbiased bases are constructed by using Gauss sums and Jacobi sums over Galois rings GR(p2, r), and the tensor method.

The Gauss sums and Jacobi sums over Galois ring GR(p^2 , r)

Galois rings and exponential sums over Galois rings have many applications in algebraic combinatorics, coding theory and cryptography. In this paper, we present explicit description on the Gauss sums and Jacobi sums over Galois ring GR(p2 , r), and show that the values of these sums can be reduced to the Gauss sums and Jacobi sums over finite field Fpr for all non-trivial cases.

0,1 distribution in the highest level sequences of primitive sequences over Z2e

In this paper, we discuss the 0, 1 distribution in the highest level sequence ae-1 of primitive sequence over Z2e generated by a primitive polynomial of degree n. First we get an estimate of the 0, 1 distribution by using the estimates of exponential sums over Galois rings, which is tight for e relatively small to n. We also get an estimate which is suitable for e relatively large to n. Combining the two bounds, we obtain an estimate depending only on n, which shows that the larger n is, the closer to 1/2 the proportion of 1 will be.

A criterion for primitive polynomials over Galois rings

The theory of primitive polynomials over Galois rings is analogue to the same one over finite fields. It also provides useful tools for one to study the maximal period sequences over Galois rings. In the case of Fq, we have more complete results. In the case of Zpn, n≥2, there are also some results. In particular, according to refs. [3, 4] and using the technique of trace representation of maximal period sequences over Fq, we have found a discriminant which can judge whether a given polynomial f（x） over Zpn is a primitive polynomial if f（x） mod p is a primitive polynomial over Fp. Furthermore, it is easy to calculate the discriminant using the coefficients of f（x）.

Improved Information Set Decoding Algorithms over Galois Ring in the Lee Metric

The security of most code-based cryptosystems relies on the hardness of the syndrome decoding(SD) problem.The best solvers of the SD problem are known as information set,decoding(ISD) algorithms.Recently,Weger,et al.(2020) described Stern’s ISD algorithm,s-blocks algorithm and partial Gaussian elimination algorithms in the Lee metric over an integer residue ring Z_(pm),where p is a prime number and m is a positive integer,and analyzed the time complexity.In this paper,the authors apply a binary ISD algorithm in the Hamming metric proposed by May,et al.(2011)to solve the SD problem over the Galois ring GR(p^(m),k) endowed with the Lee metric and provide a detailed complexity analysis.Compared with Stern’s algorithm over Zpmin the Lee metric,the proposed algorithm has a significant improvement in the time complexity.

Distribution of Elements in Primitive Sequences over Z_(p^e)

Using the estimates of character sums over Galoi8 rings and the trace de-scription of primitive sequences over Z_(p^e), we obtain an estimate for the frequency of theoccurrences of any element in Z_(p^e) in one period of a primitive sequence, which is betterthan Kuzmin's results if n >4e, where n is the degree of the generating polynomial ofthe primitive sequence.

Galois环上的一类GMW序列及其线性复杂度

将有限域上GMW序列的概念推广到了一般的Galois环上。利用环上的置换,定义了一类新的一般Galois环上的GMW序列,并对其线性复杂度进行了估计。结果表明,这类GMW序列具有非常大的线性复杂度。

Pseudo-Randomness of Certain Sequences of k Symbols with Length pq

The theory of finite pseudo-random binary sequences was built by C. Mauduit and A. Sarkozy and later extended to sequences of k symbols （or k-ary sequences）. Certain constructions of pseudo-random sequences of k symbols were presented over finite fields in the literature. In this paper, two families of sequences of k symbols are constructed by using the integers modulo pq for distinct odd primes p and q. The upper bounds on the well-distribution measure and the correlation measure of the families sequences are presented in terms of certain character sums over modulo pq residue class rings. And low bounds on the linear complexity profile are also estimated.

环的Galois、分离和Frobenius扩张

设∧是其中心Ｃ＿∧上的有限维单代数，Ｆ是满足Ｃ＿∧的∧的子环，Ｇ是保持Γ的元素不变的∧的自同构的有限群．本文证明：若∧／Γ是Ｇ－Ｇａｌｏｉｓ扩张，则在∧中的中心化子△是Ｃ＿Γ一分离代数且∧／Γ是Ｆｒｏｂｅｎｉｕｓ扩张，这里Ｃ＿Γ是Γ的中心．

Galois环导出p元序列中元素组的分布及其渐近均匀性

r-样式的分布是有限域上序列伪随机性的一个重要方面。就此问题本文对域R/pR上一类序列作了考察,这类序列得自于Galois环R=GR(ptn, pn)上其特征多项式f (x)在模p下本原的线性递归序列(包括极大长序列)的p-adic展开,即所谓Galois环导出p元序列。我们得到了这种序列上独立r-样式分布的一个估计,作为推论,r-样式的分布关于f (x)的次数是渐近均匀的。

Galois环上的不完全指数和及其在Z_p^2导出Kerdock序列上的应用

给出了Galois环上不完全指数和的上界,并在此基础上对Zp2导出的p元Kerdock序列的非周期自相关性进行了研究,给出了序列非周期自相关性的上界,其中p为任意奇素数。结果表明,该类序列具有极低的非周期自相关性,在密码学和通信领域具有潜在的应用价值。最后,还对序列元素的部分周期分布进行了估计。

Galois环上的一类具有极大线性复杂度和最佳相关性的GMW序列

构造了一类在特征为素数平方的Galois环上的GMW序列族,推广了Udaya和Siddiqi的工作。证明了该序列族具有大的序列周期和最佳相关性,其最佳相关性用Welch下界来衡量。同时利用离散傅里叶变换对序列的线性复杂度进行了估计,结果表明这类序列具有非常大的线性复杂度。