Search

Permutation polynomials over finite fields constitute an active research area and have important applications in many areas of science and engineering. In this paper, several classes of permutation polynomials with trace functions are presented over F p n (p = 2 , 3) by investigating the number of solutions to special equations. [ABSTRACT FROM AUTHOR]

The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with d 1.5 + o (1) for input polynomials of degree d, and with the square of the bit size of the ground field. It relies on a variant of the Cantor–Zassenhaus algorithm which exploits fast modular composition. Using techniques by Kaltofen and Shoup, we prove a refinement of this bound when the finite field has a large extension degree over its prime field. We also present fast practical algorithms for the case when the extension degree is smooth. [ABSTRACT FROM AUTHOR]

For a prime p and positive integers m, n, let F q be a finite field with q = p m elements and F q n be an extension of F q. Let h(x) be a polynomial over F q n satisfying the following conditions: (i) Tr m nm (x) ∘ h (x) = τ (x) ∘ Tr m nm (x) ; (ii) For any s ∈ F q , h(x) is injective on Tr m nm (x) - 1 (s) , where τ (x) is a polynomial over F q. For b , c ∈ F q , δ ∈ F q n , and positive integers i, j, d with q ≡ ± 1 (mod d) , we propose a class of permutation polynomials of the form b (Tr m nm (x) + δ) 1 + i (q n - 1) d + c (Tr m nm (x) + δ) 1 + j (q n - 1) d + h (x) over F q n by employing the Akbary–Ghioca–Wang (AGW) criterion in this paper. Accordingly, we also present the permutation polynomials of the form b (Tr m nm (x) + δ) 1 + i (q n - 1) d + h (x) by letting c = 0 and choosing some special i, which covered some known results of this form. [ABSTRACT FROM AUTHOR]

Permutation polynomials with sparse forms over finite fields attract researchers’ great interest and have important applications in many areas of mathematics and engineering. In this paper, by investigating the exponents (s, i) and the coefficients a,b∈Fq∗\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$a,b\in \mathbb {F}_{q}^{*}$$\end{document}, we present some new results of permutation polynomials of the form f(x)=axqi(q2-q+1)+bxs+Trqn/q(x)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$f(x)= ax^{q^i(q^{2}-q+1)} + bx^{s} + \textrm{Tr}_{q^n/q}(x)$$\end{document} over Fqn\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mathbb {F}_{q^n}$$\end{document} (n=2\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n=2$$\end{document} or 3). The permutation property of the new results is given by studying the number of solutions of special equations over Fqn\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mathbb {F}_{q^n}$$\end{document}. [ABSTRACT FROM AUTHOR]

Consider a multivariate polynomial f∈K[x1,…,xn]\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$f \in K [x_1, \ldots , x_n]$$\end{document} over a field K, which is given through a black box capable of evaluating f at points in Kn\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$K^n$$\end{document}, or possibly at points in An\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$A^n$$\end{document} for any K-algebra A. The problem of sparse interpolation is to express f in its usual form with respect to the monomial basis. We analyze the complexity of various old and new algorithms for this task in terms of bounds D and T for the total degree of f and its number of terms. We mainly focus on the case when K is a finite field and explore possible speed-ups. [ABSTRACT FROM AUTHOR]

Let q be a prime power and F q be a finite field with q elements. In this paper, we employ the AGW criterion to investigate the permutation behavior of some polynomials of the form b (x q + a x + δ) 1 + i (q 2 - 1) d + c (x q + a x + δ) 1 + j (q 2 - 1) d + L (x) over F q 2 with a 1 + q = 1 , q ≡ ± 1 (mod d) and L (x) = - a x or x q - a x. Accordingly, we also present the permutation polynomials of the form b (x q + a x + δ) s - a x by letting c = 0 and choosing some special exponent s, which generalize some known results on permutation polynomials of this form. [ABSTRACT FROM AUTHOR]

It is well-known that each left ideal in a matrix rings over a finite field is generated by an idempotent matrix. In this work we compute the number of left ideals in these rings, the number of different idempotents generating each left ideal, and give explicitly a set of idempotent generators of all left ideals of a given rank. We then apply these results to give examples of left group codes that have best possible minimum weight. [ABSTRACT FROM AUTHOR]

Differential uniformity of permutation polynomials has been studied intensively in recent years due to the differential cryptanalysis of S-boxes. The boomerang attack is a variant of differential cryptanalysis which combines two differentials for the upper part and the lower part of the block cipher. The boomerang uniformity measures the resistance of block ciphers to the boomerang attack. In this paper, by using the resultant elimination method, we study the boomerang uniformity of normalized permutation polynomials of the low degree over finite fields. As a result, we determine the boomerang uniformity of all normalized permutation polynomials of degree up to six over the finite field F q . [ABSTRACT FROM AUTHOR]

Let F q denote the finite field of order q. In this paper, we determine certain permutation binomials and permutation trinomials of the form x r h (x q + 1) over F q 2 . Some of them are generalizations of known ones. [ABSTRACT FROM AUTHOR]

In this paper, we present a refinement of the Cipolla-Lehmer type algorithm given by H. C. Williams in 1972, and later improved by K. S. Williams and K. Hardy in 1993. For a given r-th power residue c∈Fq where r is an odd prime, the algorithm of H. C. Williams determines a solution of Xr=c in O(r3logq) multiplications in Fq, and the algorithm of K. S. Williams and K. Hardy finds a solution in O(r4+r2logq) multiplications in Fq. Our refinement finds a solution in O(r3+r2logq) multiplications in Fq. Therefore our new method is better than the previously proposed algorithms independent of the size of r, and the implementation result via SageMath shows a substantial speed-up compared with the existing algorithms. It should be mentioned that our method also works for a composite r. [ABSTRACT FROM AUTHOR]

Permutation trinomials over finite fields are of great interest for their simple algebraic forms and important applications in many areas of mathematics and engineering. In this paper, six new classes of permutation trinomials over F33k are presented based on the multivariate method. Their permutation properties are proved by using the resultant elimination method. [ABSTRACT FROM AUTHOR]

This note presents two classes of permutation polynomials of the form $$(x^{p^m}-x+\delta )^s+L(x)$$ over the finite fields $${{\mathbb {F}}}_{p^{2m}}$$ as a supplement of the recent works of Zha, Hu and Li, Helleseth and Tang. [ABSTRACT FROM AUTHOR]

In 2016, Y. Kumar et al. in the paper ‘Affine equivalence and non-linearity of permutations overZn\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}_n$$\end{document}’ conjectured that: Forn≥3\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n\ge 3$$\end{document}, the nonlinearity of any permutation onZn\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}_n$$\end{document}, the ring of integers modulon, cannot exceedn-2\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n-2$$\end{document}. For an odd prime p, we settle the above conjecture when n=2p\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n=2p$$\end{document} and for p≡3(mod4)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$p\equiv 3 \pmod {4}$$\end{document} we prove the above conjecture with an improved upper bound. Further, we derive a lower bound on maxNLn\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\max {\mathcal {N}}{\mathcal {L}}_n$$\end{document} when n is an odd prime or twice of an odd prime where maxNLn\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\max {\mathcal {N}}{\mathcal {L}}_n$$\end{document} denotes the maximum possible nonlinearity of any permutation on Zn\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}_n$$\end{document}. [ABSTRACT FROM AUTHOR]

We provide trisection (division by 3) algorithms for Jacobians of genus 2 curves over finite fields $$\mathbb {F}_q$$ of odd characteristic which rely on the factorization of a polynomial whose roots correspond (bijectively) to the set of trisections of the given divisor. We also construct a polynomial whose roots allow us to calculate the 3-torsion divisors. We show the relation between the rank of the 3-torsion subgroup and the factorization of this 3-torsion polynomial, and describe the factorization of the trisection polynomials in terms of the Galois structure of the 3-torsion subgroup. We also generalize these ideas for $$\ell \in \{5,7\}$$ . [ABSTRACT FROM AUTHOR]

Let r be a divisor of q-1.\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$q-1.$$\end{document} An element α∈Fq\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\alpha \in {\mathbb {F}}_{q}$$\end{document} is said to be r-primitive if ord(α)=q-1r\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\alpha )=\frac{q-1}{r}$$\end{document}. In this paper, we discuss the existence of r-primitive pairs (α,f(α))\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\alpha , f(\alpha ))$$\end{document} where α∈Fq\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\alpha \in {\mathbb {F}}_q$$\end{document}, f(x) is a general rational function of degree sum m (degree sum is the sum of the degrees of numerator and denominator of f(x)) and the denominator of f(x) is square-free. Then we show that for any integer m>0\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$m>0$$\end{document}, there exists a positive constant Br,m\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$B_{r,m}$$\end{document} such that if q>Br,m\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$q>B_{r,m}$$\end{document}, then such r-primitive pairs exist. In particular, we present a bound for Br,m\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$B_{r,m}$$\end{document} with r=2\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$r=2$$\end{document} and m∈{2,3,4,5,6}\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$m\in \{2,3,4,5,6\}$$\end{document}, and provide some conditions on the existence of 2-primitive pairs. [ABSTRACT FROM AUTHOR]

We design new deterministic algorithms, based on Graeffe transforms, to compute all the roots of a polynomial which splits over a finite field $$\mathbb {F}_q$$ . Our algorithms were designed to be particularly efficient in the case when the cardinality $$q - 1$$ of the multiplicative group of $$\mathbb {F}_q$$ is smooth. Such fields are often used in practice because they support fast discrete Fourier transforms. We also present a new nearly optimal algorithm for computing characteristic polynomials of multiplication endomorphisms in finite field extensions. This algorithm allows for the efficient computation of Graeffe transforms of arbitrary orders. [ABSTRACT FROM AUTHOR]

This paper shows new permutation polynomials over finite fields. Some of them are of the form $$\left( x^{p^k}\pm x+\delta \right) ^s +hx$$ . Some others are complete mappings. [ABSTRACT FROM AUTHOR]

An extension of the primitive normal basis theorem and its strong version is proved. Namely, we show that for nearly all $$A = {\small \left( \begin{array}{cc} a&{}b \\ c&{}d \end{array} \right) } \in \mathrm{GL}_2(\mathbb {F}_{q})$$ , there exists some $$x\in \mathbb {F}_{q^m}$$ such that both $$x$$ and $$(-dx+b)/(cx-a)$$ are simultaneously primitive elements of $$\mathbb {F}_{q^m}$$ and produce a normal basis of $$\mathbb {F}_{q^m}$$ over $$\mathbb {F}_q$$ , granted that $$q$$ and $$m$$ are large enough. [ABSTRACT FROM AUTHOR]

A general construction of APN polynomial functions of the form $$c_{30}x^3+c_{03}x^{3q}+\sum \nolimits _{i=0}^2\sum \nolimits _{j=0}^2c_{ij}x^{i+qj}$$ over a finite field $$\mathbb {F}_{q^2}$$ of odd characteristic is proposed, and some variants of this construction are also presented. As a consequence, new APN polynomial functions such as ones over $$\mathbb {F}_{3^{2m}}$$ and $$\mathbb {F}_{11^2}$$ which are CCZ-inequivalent to known APN functions are obtained. [ABSTRACT FROM AUTHOR]

This note presents two new permutation polynomials with the formp(x) = (x2k +x+δ)s+x over the finite field F2n as a supplement of the recentwork of Yuan, Ding, Wang and Pieprzyk. [ABSTRACT FROM AUTHOR]

Let E be a finite degree extension over a finite field F = GF( q), G the Galois group of E over F and let a∈ F be nonzero. We prove the existence of an element w in E satisfying the following conditions: - w is primitive in E, i.e., w generates the multiplicative group of E (as a module over the ring of integers). - the set { w g∣ g∈ G} of conjugates of w under G forms a normal basis of E over F. - the (E, F)-trace of w is equal to a. This result is a strengthening of the primitive normal basis theorem of Lenstra and Schoof [10] and the theorem of Cohen on primitive elements with prescribed trace [3]. It establishes a recent conjecture of Morgan and Mullen [14], who, by means of a computer search, have verified the existence of such elements for the cases in which q≤ 97 and n≤ 6, n being the degree of E over F. Apart from two pairs ( F, E) (or ( q, n)) we are able to settle the conjecture purely theoretically. [ABSTRACT FROM AUTHOR]

We characterize almost weakly self-dual polynomial bases for the finite field over , where denotes the finite field of order q a prime power. We also extend a formula for the excess of certain polynomial bases from the case q = 2 to general q. [ABSTRACT FROM AUTHOR]

Over finite field GF( q) with q a power of an odd prime p, we characterize inversive maximal period polynomials in terms of polynomials of order q + 1, and then we study some properties of polynomials of order q + 1. [ABSTRACT FROM AUTHOR]

In this note we give a complete explicit factorization of $$x^{2^k }$$ + 1 into irreducible polynomials over F for a prime p≡3 mod 4. As a result we can construct an irreducible polynomial over F of degree of any power of 2. Some interesting properties of the coefficients of the irreducibles are noted. We also mention that our results may be useful in applying the Fast Fourier Transform over finite fields. [ABSTRACT FROM AUTHOR]

In this paper the m-dimensional extension $$\mathbb{F}_{q^m } $$ of the finite field $$\mathbb{F}_q $$ of order q is investigated from an algebraic point of view. Looking upon the additive group $$(\mathbb{F}_{q^m } , + )$$ as a cyclic module over the principal ideal domain $$\mathbb{F}_q [x]$$ , we introduce a new family of polynomials over $$\mathbb{F}_q $$ which are the additive analogues of the cyclotomic polynomials. Two methods to calculate these polynomials are proposed. In combination with algorithms to compute cyclotomic polynomials, we obtain, at least theoretically, a method to determine all elements in $$\mathbb{F}_{q^m } $$ of a given additive and multiplicative order; especially the generators of both cyclic structures, namely the generators of primitive normal bases in $$\mathbb{F}_{q^m } $$ over $$\mathbb{F}_q $$ , are characterized as the set of roots of a certain polynomial over $$\mathbb{F}_q $$ . [ABSTRACT FROM AUTHOR]