Abstract:
Four recursive constructions of permutation polynomials over $\gf(q^2)$ with those over $\gf(q)$ are developed and applied to a few famous classes of permutation polynomials. They produce infinitely many new permutation polynomials over $\gf(q^{2^\ell})$ for any positive integer $\ell$ with any given permutation polynomial over $\gf(q)$. A generic construction of permutation polynomials over $\gf(2^{2m})$ with o-polynomials over $\gf(2^m)$ is also presented, and a number of new classes of permutation polynomials over $\gf(2^{2m})$ are obtained.

Abstract:
We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function $f: \{0,1\}^n \to \{0,1\}$ is an $s$-sparse GF(2) polynomial versus $\eps$-far from every such polynomial. Our algorithm makes $\poly(s,1/\eps)$ black-box queries to $f$ and runs in time $n \cdot \poly(s,1/\eps)$. The only previous algorithm for this testing problem \cite{DLM+:07} used poly$(s,1/\eps)$ queries, but had running time exponential in $s$ and super-polynomial in $1/\eps$. Our approach significantly extends the ``testing by implicit learning'' methodology of \cite{DLM+:07}. The learning component of that earlier work was a brute-force exhaustive search over a concept class to find a hypothesis consistent with a sample of random examples. In this work, the learning component is a sophisticated exact learning algorithm for sparse GF(2) polynomials due to Schapire and Sellie \cite{SchapireSellie:96}. A crucial element of this work, which enables us to simulate the membership queries required by \cite{SchapireSellie:96}, is an analysis establishing new properties of how sparse GF(2) polynomials simplify under certain restrictions of ``low-influence'' sets of variables.

Abstract:
A method for generating irreducible polynomials of degree n over the finite field GF(2) is proposed. The irreducible polynomials are found by solving a system of equations that brings the information on the internal properties of the splitting field GF(2^n) . Also, the choice of a primitive normal basis allows us to build up a natural representation of GF(2^n) in the space of n-binary sequences. Illustrative examples are given for the lowest orders.

Abstract:
In this paper we describe an improved version of HF-hash [7] viz. R-hash: Hash Function Using RandomQuadratic Polynomials Over GF(2). The compression function of HF-hash consists of 32 polynomials with64 variables over GF(2), which were taken from the first 32 polynomials of HFE challenge-1 by forcinglast 16 variables as 0. The mode operation used in computing HF-hash was Merkle-Damgard. We haverandomly selected 32 quadratic non-homogeneous polynomials having 64 variables over GF(2) in case ofR-hash to improve the security of the compression function used in HF-hash. In designing R-hash, we havealso changed the mode operation used in HF-hash, because of the theoretical weakness found in theMerkle-Damgard construction.In this paper we will prove that R-hash is more secure than HF-hash and SHA-256 as well as we will showthat it is also faster than HF-hash.

Abstract:
The discrete Fourier analysis on the 30°-60°-90° triangle is deduced from the corresponding results on the regular hexagon by considering functions invariant under the group G2, which leads to the definition of four families generalized Chebyshev polynomials. The study of these polynomials leads to a Sturm-Liouville eigenvalue problem that contains two parameters, whose solutions are analogues of the Jacobi polynomials. Under a concept of m-degree and by introducing a new ordering among monomials, these polynomials are shown to share properties of the ordinary orthogonal polynomials. In particular, their common zeros generate cubature rules of Gauss type.

Abstract:
The discrete Fourier analysis on the $30^{\degree}$-$60^{\degree}$-$90^{\degree}$ triangle is deduced from the corresponding results on the regular hexagon by considering functions invariant under the group $G_2$, which leads to the definition of four families generalized Chebyshev polynomials. The study of these polynomials leads to a Sturm-Liouville eigenvalue problem that contains two parameters, whose solutions are analogues of the Jacobi polynomials. Under a concept of $m$-degree and by introducing a new ordering among monomials, these polynomials are shown to share properties of the ordinary orthogonal polynomials. In particular, their common zeros generate cubature rules of Gauss type.

Abstract:
Spin-tomographic symbols of qudit states and spin observables are studied. Spin observables are associated with the functions on a manifold whose points are labelled by spin projections and 2-sphere coordinates. The star-product kernel for such functions is obtained in explicit form and connected with Fourier transform of characters of SU(2) irreducible representation. The kernels are shown to be in close relation to the Chebyshev polynomials. Using specific properties of these polynomials, we establish the recurrence relation between kernels for different spins. Employing the explicit form of the star-product kernel, a sum rule for Clebsch-Gordan and Racah coefficients is derived. Explicit formulas are obtained for the dual tomographic star-product kernel as well as for intertwining kernels which relate spin-tomographic symbols and dual tomographic symbols.

Abstract:
We prove that the Fourier dimension of any Boolean function with Fourier sparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof method yields an improved bound of $\widetilde{O}(\sqrt{s})$ assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every Boolean function of sparsity $s$ there is an affine subspace of $\mathbb{F}_2^n$ of co-dimension $O(\poly\log s)$ restricted to which the function is constant. This conjectured bound is tight upto poly-logarithmic factors as the Fourier dimension and sparsity of the address function are quadratically separated. We obtain these bounds by observing that the Fourier dimension of a Boolean function is equivalent to its non-adaptive parity decision tree complexity, and then bounding the latter.

Abstract:
A fast algorithm is derived for determining the linear complexity and the minimal polynomials of sequences over GF(p^m) with period kn, where p is a prime number, gcd(n,p^m-1)=1 and p^m-1=ku, n,k and u are integers. The algorithm presented here covers the algorithm proposed by Chen for determining the minimal polynomials of sequences over GF(p^m) with period 2^tn, where p is a prime, gcd(n,p^m-1)=1 and p^m-1=2^tu, n and u are integers. Combining our result with some known algorithms, it is possible to determine the linear complexity of sequences over GF(p^m) with period kn more efficiently. Finally an example applying this algorithm is presented.

Abstract:
A compressive sensing (CS) reconstruction method for polynomial phase signals is proposed in this paper. It relies on the Polynomial Fourier transform, which is used to establish a relationship between the observation and sparsity domain. Polynomial phase signals are not sparse in commonly used domains such as Fourier or wavelet domain. Therefore, for polynomial phase signals standard CS algorithms applied in these transformation domains cannot provide satisfactory results. In that sense, the Polynomial Fourier transform is used to ensure sparsity. The proposed approach is generalized using time-frequency representations obtained by the Local Polynomial Fourier transform (LPFT). In particular, the first-order LPFT can produce linear time-frequency representation for chirps. It provides revealing signal local behavior, which leads to sparse representation. The theory is illustrated on examples.