Monomial and quadratic bent functions over the finite fields of odd characteristic

Considered are p-ary bent functions having the form f(x)=Tr/sub n/(/spl sigma//sub i=0//sup s/a/sub i/x/sup di/). A new class of ternary monomial regular bent function with the Dillon exponent is discovered. The existence of Dillon bent functions in the general case is an open problem of deciding whether a certain Kloosterman sum can take on the value -1. Also described is the general Gold-like form of a bent function that covers all the previously known monomial quadratic cases. The (weak) regularity of the new as well as of known monomial bent functions is discussed and the first example of a not weakly regular bent function is given. Finally, some criteria for an arbitrary quadratic function to be bent are proven.     

Hartley transforms over finite fields

A general framework is presented for constructing transforms in the field of the input which have a convolution-like property. The construction is carried out over finite fields, but is shown to be valid over the real and complex fields as well. It is shown that these basefield transforms can be viewed as “projections” of the discrete Fourier transform (DFT) and that they exist for all lengths N for which the DFT is defined. The convolution property of the basefield transforms is derived and a condition for such transforms to have the self-inverse property is given. Also, fast algorithms for these basefield transforms are developed, showing gains when compared to computations using the FFT. Application of the methodology to Hartley transforms over R leads to a simple derivation of fast algorithms for computing real Hartley transforms     

Digital oscillators over finite fields

This paper shows how the error-free computational property of finite fields can be used to eliminate aperiodicity and SNR degradation problems in digital oscillators. Galois fields are used to eliminate representation and truncation errors in the computation of sinusoid samples. Theorems are presented that characterize those fields that admit all operands necessary for sample generation at a given phase resolution. Two finite field oscillator architectures, exponential feedback, and direct forms are presented, and various design issues associated with operand representation and arithmetic are discussed. It is also shown how field arithmetic can be replaced by arithmetic in the direct product ring associated with a set of specially chosen small fields. This is important in high-speed applications where the loop delay must be minimized. We also present analytical estimates of clocking frequency, latency, and phase and frequency resolution for both architectures. Finally, we present an example ASIC design of a finite ring digital oscillator in 2μ CMOS technology     

Paraunitary filter banks over finite fields

In real and complex fields, unitary and paraunitary (PU) matrices have found many applications in signal processing. There has been interest in extending these ideas to the case of finite fields. We study the theory of PU filter banks (FBs) in GF(q) with q prime. Various properties of unitary and PU matrices in finite fields are studied. In particular, a number of factorization theorems are given. We show that (i) all unitary matrices in GF(q) are factorizable in terms of Householder-like matrices and permutation matrices, and (ii) the class of first-order PU matrices (the lapped orthogonal transform in finite fields) can always be expressed as a product of degree-one or degree-two building blocks. If q>2, we do not need degree-two building blocks. While many properties of PU matrices in finite fields are similar to those of PU matrices in complex field, there are a number of differences. For example, unlike the conventional PU systems, in finite fields, there are PU systems that are unfactorizable in terms of smaller building blocks. In fact, in the special case of 2×2 systems, all PU matrices that are factorizable in terms of degree-one building blocks are diagonal matrices. We derive results for both the cases of GF(2) and GF(Q) with q>2. Even though they share some similarities, there are many differences between these two cases     

Finding roots of polynomials over finite fields

We propose an improved algorithm for finding roots of polynomials over finite fields. This makes possible significant speedup of the decoding process of Bose-Chaudhuri-Hocquenghem, Reed-Solomon, and some other error-correcting codes.     

The fractional Fourier transform over finite fields

The central contribution of this paper is the definition of the fractional Fourier transform over finite fields (GFrFT). In order to introduce the GFrFT, concepts related to trigonometry in finite fields are reviewed and some new ideas put forward. In particular, graphic representations of elements in a finite field are suggested and analogies with real and complex numbers are discussed. A modified version of the finite field Fourier transform is given and its eigenstructure is analyzed. This allows us to develop GFrFT theory and investigate its main characteristics. Some illustrative examples are also given throughout the paper.     

Solving sparse linear equations over finite fields

A "coordinate recurrence" method for solving sparse systems of linear equations over finite fields is described. The algorithms discussed all requireO(n_{1}(omega + n_{1})log^{k}n_{1})field operations, wheren_{1}is the maximum dimension of the coefficient matrix,omegais approximately the number of field operations required to apply the matrix to a test vector, and the value ofkdepends on the algorithm. A probabilistic algorithm is shown to exist for finding the determinant of a square matrix. Also, probabilistic algorithms are shown to exist for finding the minimum polynomial and rank with some arbitrarily small possibility of error.     

Cyclic block codes definable over multiple finite fields

It is shown that there exists a class of error correcting codes which can be viewed both as binary cyclic codes and as multilevel cyclic codes. This class contains not only the Burton codes but also some Reed Solomon codes. The conditions which codes of this class must satisfy are explained and some simple examples are given     

Efficient probabilistic algorithm for solving quadratic equations over finite fields

An efficient probabilistic algorithm for solving quadratic equations over GF(p) (p is odd prime) and GF(2m) is proposed. This algorithm solves the given quadratic equations probabilistically with probability 0-5 in each trial and is more efficient than Rabin's method for quadratic equations over GF(p) and GF(2m).     

Efficient bit-serial multiplication and the discrete-timeWiener-Hopf equation over finite fields

Discrete-time Wiener-Hopf equations (DTWHEs) over finite fields are considered. It is shown that solving the DTWHE is equivalent to performing division over finite fields. The proof provides a new interpretation of the relationship between bit-serial multiplication and DTWHEs. The interpretation enables bit-serial multiplication over GF(2 ^m) to be understood more easily. As an example, bit-serial multiplication methods for multiplying any two elements that can be done without performing any transformation, or with only a simple transformation of the bases, are presented     

Multiplicative complexity of bilinear algorithms for cyclic convolution over finite fields

The multiplicative complexity of bilinear algorithms for cyclic convolution over finite fields is investigated. It is shown that mutually prime factor algorithms are inferior to directly designed algorithms for all lengths except those whose factors have relatively prime exponents. A previously described approach is proposed for directly designing algorithms which are highly structured and computationally efficient. Several complexity results are provided for factor lengths of specific form, and the manner in which cyclic convolution algorithms lead to linear algebraic error-correcting codes is discussed.Research supported by Natural Sciences and Engineering Research Council Canada Grant A0912.     

特征3有限域上椭圆曲线的Montgomery算法

研究了Montgomery算法在特征3有限域上椭圆曲线的应用.根据Montgomery算法的结构,省去y坐标的计算,提出新的点加和倍点计算公式,加快点乘计算速度.经过理论分析和实验验证,提出的点加和倍点计算公式可节省约15%的运算时间.     

有限域上的Resilient函数

文献[1]讨论了二元域上的Resilient函数,本文将Resilient函数的概念推广到一般有限域上,并对它进行了讨论,得到了它的一些性质．     

有限域上多项式形式的ElGamal体制及数字签名方案

提出了有限域上多项式形式的ElGamal公钥体制,并基于新体制,提出了一个多项式形式的ElGamal数字签名方案。新的公钥体制一次可以加密多个明文,新的签名方案一次可对多个文件进行签名。两个体制的安全性都主要基于离散对数问题的难解性。     

Construction of compressed sensing matrices based on affine symplectic space over finite fields

The compressed sensing matrices based on affine symplectic space are constructed. Meanwhile, a comparison is made with the compressed sensing matrices constructed by DeVore based on polynomials over finite fields. Moreover, we merge our binary matrices with other low coherence matrices such as Hadamard matrices and discrete fourier transform (DFT) matrices using the embedding operation. In the numerical simulations, our matrices and modified matrices are superior to Gaussian matrices and DeVore's matrices in the performance of recovering original signals.     

A new structured design method for convolutions over finite fields, Part I

The structure of bilinear cyclic convolution algorithms is explored over finite fields. The algorithms derived are valid for any length not divisible by the field characteristic and are based upon the small length polynomial multiplication algorithms. The multiplicative complexity of these algorithms is small and depends on the field of constants. The linear transformation matricesA, B(premultiplication), andC(postmultiplication) defining the algorithm have block structures which are related to one another. The rows ofAandBand the columns ofCare maximal length recurrent sequences. Because of the highly regular structure ofA, B, andC, the algorithms can be very easily designed even for large lengths. The application of these algorithms to the decoding of Reed-Solomon codes is also examined.     

有限域和剩余类环上非奇异反馈多项式的谱刻划

本文给出了有限域和剩余类环上非线性反馈移存器的非奇异反馈多项式及局部置换多项式的谱刻划，简化了素域上的现有结果，并对有限域上和剩余类环上相关免疫函数的谱特征给出了一个新的证明方法。     

Two-band wavelets and filterbanks over finite fields with connections to error control coding

Recently, we have developed a new framework to study error-control coding using finite-field wavelets and filterbanks (FBs). This framework reveals a rich set of signal processing techniques that can be exploited to investigate new error correcting codes and to simplify encoding and decoding techniques for some existing ones. The paper introduces the theory of wavelet decompositions of signals in vector spaces defined over Galois fields. To avoid the limitations of the number theoretic Fourier transform, our wavelet transform relies on a basis decomposition in the time rather than the frequency domain. First, by employing a symmetric, nondegenerate canonical bilinear form, we obtain a necessary and sufficient condition that the basis functions defined over finite fields must satisfy in order to construct an orthogonal wavelet transform. Then, we present a design methodology to generate the mother wavelet and scaling function over finite fields by relating the wavelet transform to two-channel paraunitary (PU) FBs. Finally, we describe the application of this transform to the construction of error correcting codes. In particular, we give examples of double circulant codes that are generated by wavelets.     

A fast algorithm for the Fourier transform over finite fields andits VLSI implementation

The Fourier transform over finite fields is mainly required in the encoding and decoding of Reed-Solomon and BCH codes. An algorithm for computing the Fourier transform over any finite field GF(p^m) is introduced. It requires only O(n(log n)²/4) additions and the same number of multiplications for an n-point transform and allows in some fields a further reduction of the number of multiplications to O(n log n). Because of its highly regular structure, this algorithm can be easily implementation by VLSI technology     

New key pre-distribution scheme using symplectic geometry over finite fields for wireless sensor networks

To achieve secure communication in wireless sensor networks (WSNs), where sensor nodes with limited computation capability are randomly scattered over a hostile territory, various key pre-distribution schemes (KPSs) have been proposed. In this paper, a new KPS is proposed based on symplectic geometry over finite fields. A fixed dimensional subspace in a symplectic space represents a node, all 1-dimensional subspaces represent keys and every pair of nodes has shared keys. But this naive mapping does not guarantee a good network resiliency. Therefore, it is proposed an enhanced KPS where two nodes have to compute a pairwise key, only if they share at least q common keys. This approach enhances the resilience against nodes capture attacks. Compared with the existence of solution, the results show that new approach enhances the network scalability considerably, and achieves good connectivity and good overall performance.