Search

Let k be an integer with k ≥ 2 . Let R be a finite commutative ring with zero element 0 R and identity element 1 R ≠ 0 R and let R ∗ be the multiplicative group of units of R . Let f (x) ∈ R [ x ] be a non-constant polynomial. An element u ∈ R is called an f -unit if f (u) ∈ R ∗ . An f -unit is called an exceptional unit when f (x) = x (1 R - x) . In this paper, we obtain an exact formula for the number of representations of any element of R as the sum of kf-units of R. Furthermore, by using the technique of exponential sums, we deduce a more explicit formula for the case when f(x) is linear or quadratic. Our results generalize Miguel's theorem from exceptional unit to general f-unit and the Zhao–Hong–Zhu theorem from the ring of residue classes to the general finite commutative ring. [ABSTRACT FROM AUTHOR]

Motivated by recent works on the butterfly structure, particularly by its generalization introduced by Canteaut et al. (IEEE Trans Inf Theory 63(11):7575–7591, 2017), we first push further the study of permutation polynomials over binary finite fields by completely characterizing those permutations f ϵ ̲ defined over the finite field F Q 2 (of order Q 2 ) having the following shape: f ϵ ̲ (X) : = ϵ 1 X ¯ q + 1 + ϵ 2 X ¯ q X + ϵ 3 X ¯ X q + ϵ 4 X q + 1 where q = 2 k , Q = 2 m , m is odd, gcd (m , k) = 1 , X ¯ = X Q and ϵ ̲ = (ϵ 1 , ϵ 2 , ϵ 3 , ϵ 4) ∈ F Q 4 . We shall provide an approach to handle the bijectivity of f ϵ ̲ for any k ≥ 1 . Notably, we show that the problem of finding conditions for bijectivity of the quadrinomial f ϵ ̲ is closely related to the study of the famous equation X q + 1 + X + a = 0 (*). We then reduce the initial problem into the problem of finding conditions for which an equation of the form (*) has a unique solution in F Q for every a ∈ F Q . In addition, as a crucial direct consequence our result, we prove the validity of the conjecture (Conjecture 19) proposed by Li et al. (Des Codes Cryptogr 89:737–761, 2021). We emphasize that our positive answer completely characterizes permutations with boomerang uniformity 4 from the butterfly structure, which leads to the view of the quadrinomial f ϵ ̲ as excellent candidates to design block ciphers in symmetric cryptography. Despite a lot of attention regarding the considered conjecture, it remains unsolved on its whole when the coefficients lie in F Q . However, this article is the first which propose an approach that solves the enter conjecture by handling both sides of it involving equivalence simultaneously. We believe that our novel approach and its strength could benefit from proving the bijectivity of other families of polynomials over finite fields. [ABSTRACT FROM AUTHOR]

We illustrate a general technique to construct towers of fields producing high order elements in F q 2 n , for odd q, and in F 2 2 · 3 n , for n ≥ 1 . These towers are obtained recursively by x n 2 + x n = v (x n - 1) , for odd q, or x n 3 + x n = v (x n - 1) , for q = 2 , where v(x) is a polynomial of small degree over the prime field F q and x n belongs to the finite field extension F q 2 n , for an odd q, or to F 2 2 · 3 n . Several examples are provided to show the numerical efficacy of our method. Using the techniques of Burkhart et al. (Des Codes Cryptogr 51(3):301–314, 2009) we prove similar lower bounds on the orders of the groups generated by x n , or by the discriminant δ n of the polynomial. We also provide a general framework which can be used to produce many different examples, with the numerical performance of our best examples being slightly better than in the cases analyzed in Burkhart et al. (2009). [ABSTRACT FROM AUTHOR]

We consider the problem of interpolating a sparse multivariate polynomial over a finite field, represented with a black box. Building on the algorithm of Ben-Or and Tiwari (1988) for interpolating polynomials over fields with characteristic zero, we develop a new Monte Carlo algorithm over finite fields by doing additional probes. To interpolate a polynomial f ∈ F q [ x 1 , ... , x n ] with a partial degree bound D and a term bound T, our new algorithm costs O ∼ (n T log 2 q + n T D log q) bit operations and uses 2(n + 1)T probes to the black box. If q ⩾ O(nT2D), it has constant success rate to return the correct polynomial. Compared with the previous algorithms over general finite field, our algorithm has better complexity in the parameters n, T and D, and is the first one to achieve the complexity of fractional power about D, while keeping linear in n and T. A key technique is a randomization which makes all the coefficients of the unknown polynomial distinguishable, producing a diverse polynomial. This approach, called diversification, was proposed by Giesbrecht and Roche (2011). Our algorithm interpolates each variable independently by using O(T) probes, and then uses the diversification to correlate terms in different images. At last, we get the exponents by solving the discrete logarithms and obtain the coefficients by solving a linear system. We have implemented our algorithm in Maple. Experimental results show that our algorithm can be applied to the sparse polynomials with large degree within a few minutes. We also analyze the success rate of the algorithm. [ABSTRACT FROM AUTHOR]

Each irreducible representation of the affine group of a finite field has a unique maximal inductive algebra, and it is self-adjoint. [ABSTRACT FROM AUTHOR]

In this paper, by transforming the permutation problem into the root distribution problem in the unit circle of certain quadratic and cubic equations, we investigate the permutation behavior of the type f(x) = x + ... over 픽... and f(x) = x + ... + ... over 픽..., respectively. [ABSTRACT FROM AUTHOR]

Let F be a finite field, μ be a fixed additive character and s be an integer coprime to | F × |. For any a ∈ F , the corresponding Weil sum is defined to be W F , s (a) = ∑ x ∈ F μ (x s − a x). The Weil spectrum counts distinct values of the Weil sum as a runs through the invertible elements in the finite field. The value of these sums and the size of the Weil spectrum are of particular interest, as they link problems in coding and information theory to other areas of math such as number theory and arithmetic geometry. In the setting of Niho exponents, we examine the Weil sum, its bounds and its spectrum. As a consequence, we give a new proof to the Vanishing Conjecture of Helleseth (1971) on the presence of zero in the Weil spectrum in the case of Niho exponents. We also state a conjecture for when the Weil spectrum contains at least five elements, and prove it for a certain class of Weil sums. [ABSTRACT FROM AUTHOR]

For a finite field F of characteristic 2, an integer n ≥ 3 , and for a function f : F → F , if there is a function h : F → F such that the divided difference f [ x 1 , ⋯ , x n ] on any n distinct elements of F satisfies f [ x 1 , ... , x n ] = h (x 1 + ⋯ + x n) , then f is a polynomial of degree at most n over F . This makes earlier work of Davies and Rousseau complete. [ABSTRACT FROM AUTHOR]

One of the most important functions used in a quantum key distribution (QKD) network is universal hash functions, specially, (almost) strongly universal hash functions which are used in at least three steps of QKD, in particular, in error correction, privacy amplification, and authentication. Also, they have been recently used in several other quantum communication protocols like quantum secret sharing (QSS). These hash functions have also many other important applications from information security to data structures and parallel computing. Recently, Bibak et al. [Quantum Inf. Comput., 2021] introduced quadratic hash which gives much better collision bound than the well-known polynomial hash. In this paper, we define three new universal hash function families which strongly generalize all the previous families and have several advantages over them. Then, using highly influential and pioneering results of Schmidt and of Weil, we show that these new families are (almost) Δ -universal which can then be easily converted to (almost) strongly universal families. This makes them useful for applications in QKD and many other areas. [ABSTRACT FROM AUTHOR]

For q = 3 r (r ∈ ℕ), denote by q the finite field of order q and for a positive integer m ≥ 2 , let q m be its extension field of degree m. We establish a sufficient condition for existence of a primitive normal element α such that f (α) is a primitive element, where f (x) = a x 2 + b x + c , with a , b , c ∈ q m satisfying b 2 ≠ a c in q m . [ABSTRACT FROM AUTHOR]

Let $ F $ be a finite field of characteristic $ p $ having $ q = p^n $ elements and $ G $ be an abelian group. In this paper, we determine the structure of the group of units of the group algebra $ FG $, where $ G $ is an abelian group of order $ 17\leq |G|\leq 20 $.

Linear complementary dual (LCD) codes and linear complementary pairs (LCP) of codes have been proposed for new applications as countermeasures against side-channel attacks (SCA) and fault injection attacks (FIA) in the context of direct sum masking (DSM). The countermeasure against FIA may lead to a vulnerability for SCA when the whole algorithm needs to be masked (in environments like smart cards). This led to a variant of the LCD and LCP problems, where several results were obtained intensively for LCD codes, but only partial results were derived for LCP codes. Given the gap between the thin results and their particular importance, this paper aims to reduce this by further studying the LCP of codes in special code families and, precisely, the characterization and construction mechanism of LCP codes of algebraic geometry codes over finite fields. Notably, we propose constructing explicit LCP of codes from elliptic curves. Besides, we also study the security parameters of the derived LCP of codes (C , D) (notably for cyclic codes), which are given by the minimum distances d (C) and d (D ⊥). Further, we show that for LCP algebraic geometry codes (C , D) , the dual code C ⊥ is equivalent to D under some specific conditions we exhibit. Finally, we investigate whether MDS LCP of algebraic geometry codes exist (MDS codes are among the most important in coding theory due to their theoretical significance and practical interests). Construction schemes for obtaining LCD codes from any algebraic curve were given in 2018 by Mesnager, Tang and Qi in [11]. To our knowledge, it is the first time LCP of algebraic geometry codes has been studied. [ABSTRACT FROM AUTHOR]

It is known that a Bruen chain of the three-dimensional projective space PG (3 , q) exists for every odd prime power q at most 37, except for q = 29. It was shown by Cardinali et al. (2005) that Bruen chains do not exist for 41 ⩽ q ⩽ 49. We develop a model, based on finite fields, which allows us to extend this result to 41 ⩽ q ⩽ 97 , thereby adding more evidence to the conjecture that Bruen chains do not exist for q > 37. Furthermore, we show that Bruen chains can be realised precisely as the (q + 1) / 2 -cliques of a two related, yet distinct, undirected simple graphs. [ABSTRACT FROM AUTHOR]

Let q be a power of a prime such that q ≡ 1 (mod r). Let c be an r -th power residue over F q. In this paper, we present a new r -th root formula which generalizes G.H. Cho et al.'s cube root algorithm, and which provides a refinement of Williams' Cipolla-Lehmer based procedure. Our algorithm which is based on the recurrence relations arising from irreducible polynomial h (x) = x r + (− 1) r + 1 (b + (− 1) r r) (x − 1) with b = c + (− 1) r + 1 r requires only O (r 2 log ⁡ q + r 4) multiplications for r > 1. The multiplications for computation of the main exponentiation of our algorithm are half of that of the Williams' Cipolla-Lehmer type algorithms. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is using analytic methods to give a recurrence formula of the number of solutions of an equation over finite field. We use analytic methods to give a recurrence formula for the number of solutions of the above equation. And our method is based on the properties of the Gauss sum. It is worth noting that we used a novel method to simplify the steps and avoid complicated calculations.

Similarities between biological and digital communication systems have been investigated since biology also uses a discrete alphabet to represent and transmit information. The genetic information of an organism is encoded in DNA molecules by units called bases. However, there is no a definitive model and the question as what error-correcting code underlies DNA sequences remains an open problem. Recent works show that DNA sequences can be identified as codewords in a class of cyclic error-correcting codes known as BCH codes. We propose improvements regarding the code construction process that resulted in a novel algorithm for searching BCH codes whose codeword differ from a given DNA sequence (mapped to finite field $\mathbb {F}_{4}$ ) in up to only one symbol. The most important improvement is to replace brute force decoding with syndrome decoding. In this sense, based on a statistical analysis, we verify whether in a collection of sequences with the same taxonomic rank there is a code that identifies most of these sequences, called dominant code. Furthermore, we check whether the dominant code can provides a biological information to DNA classification being an alignment-free method. Finally, we show that the probability of a DNA sequences with odd-length $n$ be identified by a BCH code tends to analytical probability of the same code identifying a random vector.

In recent years, there have been a lot of research towards finding conditions under which the trinomial x r (x α (q − 1) + x β (q − 1) + 1) permutes F 2 2 m with α > β and r being positive integers. The authors of [6,10,24] have determined these conditions when α ≤ 5 for certain values of β and r. In this paper, we work for α = 6 and determine four new classes of such permutation trinomials. Our contribution encompasses the investigation of these unexplored classes. Additionally, we analyze their quasi-multiplicative equivalence with already known permutation trinomials for m ≥ 1. Through our research, we demonstrate that two of these determined classes are new, and for others, we explicitly compute the exponent for which they become equivalent. [ABSTRACT FROM AUTHOR]

We introduce a class of permutation polynomial over F q n that can be written in the form L (x) x q + 1 or L (x q + 1) x for some q -linear polynomial L over F q n . Specifically, we present those permutation polynomials explicitly as well as their inverses. In addition, more permutation polynomials can be derived in a more general form. [ABSTRACT FROM AUTHOR]

A plane curve C ⊂ P 2 of degree d is called blocking if every F q -line in the plane meets C at some F q -point. We prove that the proportion of blocking curves among those of degree d is o (1) when d ≥ 2 q − 1 and q → ∞. We also show that the same conclusion holds for smooth curves under the somewhat weaker condition d ≥ 3 p and d , q → ∞. Moreover, the two events in which a random plane curve is smooth and respectively blocking are shown to be asymptotically independent. Extending a classical result on the number of F q -roots of random polynomials, we find that the limiting distribution of the number of F q -points in the intersection of a random plane curve and a fixed F q -line is Poisson with mean 1. We also present an explicit formula for the proportion of blocking curves involving statistics on the number of F q -points contained in a union of k lines for k = 1 , 2 , ... , q 2 + q + 1. [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]

Let q be an even prime power and m ≥ 2 an integer. By q , we denote the finite field of order q and by q m its extension of degree m. In this paper, we investigate the existence of a primitive normal pair (α , f (α)) , with f (x) = a x 2 + b x + c d x + e ∈ q m (x) where the rank of the matrix F = a b c 0 d e ∈ M 2 × 3 ( q m ) is 2. Namely, we establish sufficient conditions to show that nearly all fields of even characteristic possess such elements, except for 1 1 0 0 1 0 if q = 2 and m is odd, and then we provide an explicit small list of possible and genuine exceptional pairs (q , m). [ABSTRACT FROM AUTHOR]

Encryption schemes like AES require finite field modular multiplication. The encryption speed is highly dependent on the performance of the finite field multiplier. Several high-speed systolic bit parallel multipliers with low area complexity have been proposed in the literature. In this paper, a modular multiplication algorithm is used to propose a bit parallel polynomial basis systolic multiplier which has achieved 89% less and 17% less area-delay product than the best existing multipliers. It has been observed that the area complexity of the proposed systolic multiplier for irreducible polynomials matches with the best-reported multiplier with 17% less time complexity. The results are further verified with the help of the FPGA implementation of the proposed multiplier for m = 8,163. Being generic, the proposed multiplier can be optimized further for trinomials and pentanomials. [ABSTRACT FROM AUTHOR]

In this paper, we give the characterization of the unit groups of semisimple group algebras of some non-metabelian groups of order 1 2 0. This study completes the study of unit groups of semisimple group algebras of all groups up to order 1 2 0 , except that of the symmetric group S 5 and groups of order 9 6. [ABSTRACT FROM AUTHOR]

Let q be a prime power, q ≠ 2 , 3 , and let A be an n × n matrix over q 2 . We prove that the numerical range of A B and B A is the same for every rank 1 matrix B if and only if A is a multiple of a unitary matrix. The corresponding result for complex matrices was proved by Chien, Gau, Li, Tsai and Wang [Products of operators and numerical range, Linear Multilinear Algebra 64(1) (2016) 58–67]. [ABSTRACT FROM AUTHOR]

Applications of permutation polynomials in cryptography are closely related to their cycle structures. For example, many block ciphers use permutation polynomials defined over F 2 n with few fixed points and nontrivial cycles of length 2 as their S-boxes. In addition, permutation polynomials with long cycles have been widely used to generate keystream sequences. Complete permutation polynomials over F 2 n have a single fixed point and good bit independence, which can provide good choices for S-boxes in block ciphers. However, there are only a limited number of known infinite families of complete permutation polynomials with explicit cycle structures. In this paper, we construct two classes of r-regular complete permutation polynomials g(x) over F 2 n , i.e., g(x) is a complete permutation polynomial over F 2 n with a single fixed point and all the other cycles of the same length r. The first class of regular complete permutation polynomials over F 2 km is based on some permutation polynomials over F 2 m for positive integers k, m, and the second class of regular complete permutation polynomials over F 2 n for a positive integer n is obtained from piecewise functions. In addition, when g(x) is a r-regular complete permutation polynomial, we also consider the r-regular complete permutation property of g (x) + x . [ABSTRACT FROM AUTHOR]

Let s be a positive integer, p be an odd prime, q = ps, and let Fq be a finite field of q elements. Let Nq be the number of solutions of the following equations: (x1m1 + x2m2 + ... + xnmn)k = x1x2...xnxn+1kn+1 over the finite field Fq, with n≥2, t>n,k, and kj(n+1 ≤ j≤), mi(1 ≤ i ≤n) are positive integers. In this paper, we find formulas for Nq when there is a positive integer l such that dD|(pl+1), where D = lcm[d1,...dn], d = gcd(Σi=1n M/mi -kM, (q-1)/D), M=lcm [m1, ... mn], dj = gcd(mj,q-1), 1≤j≤n. .And we determine Nq explicitly under certain cases. This extends Markoff-Hurwitz-type equations over finite field. [ABSTRACT FROM AUTHOR]

Let p be a prime number and let k be an algebraically closed field of characteristic p. A BT_1 group scheme over k is a finite commutative group scheme which arises as the kernel of p on a p-divisible (Barsotti–Tate) group. Our main result is that every BT_1 group scheme over k occurs as a direct factor of the p-torsion group scheme of the Jacobian of an explicit curve defined over {\mathbb F}_p. We also treat a variant with polarizations. Our main tools are the Kraft classification of BT_1 group schemes, a theorem of Oda, and a combinatorial description of the de Rham cohomology of Fermat curves. [ABSTRACT FROM AUTHOR]

We consider polynomials over a prime field of elements. With each polynomial under consideration, we associate the -valued function defined by the polynomial. A period of the -valued function is a tuple of elements in such that . In the paper, we propose an algorithm that, for an arbitrary prime and an arbitrary -valued function given by a polynomial over the field , finds a basis of the linear space of all periods of . Moreover, the complexity of the algorithm is , where is the degree of the polynomial defining . As a consequence, we show that for prime and each fixed number the problem of search for a basis of the linear space of all periods of a function given by a polynomial of degree at most can be solved by a polynomial-time algorithm with respect to the number of function variables. [ABSTRACT FROM AUTHOR]

In this article, we present a new strategy to reduce rational polynomials based on the kernel of a linear map defined by Sylvester's matrix. The strategy does not carry out the computation of the greatest common divisor between two polynomials, as other algorithms do, but produces the reduced fractional polynomial directly. This strategy was inspired while we were considering Padé approximant as tensor elements in the proper generalised decomposition for solving partial differential equations. The proposed algorithm can use the Singular Value Decomposition (SVD) technique when dealing with a polynomial with floating-point arithmetic. We compare it with Brown's algorithm and another one, that is based on SVD technique, which is proposed by Corless, in two wedges: multiplication for finite and integral field. Comparison are made in term of time of computation and robustness. The proposed algorithm yields the reduced fractional polynomail with less time complexity than the Brown algorithm and Corless' one, and that for multiplication in finite, fractional and integral fields. Robustness of the algorithm has been tested too and compared with those algorithms. Tests have shown the ability of removing Froissart doublets and producing reduced fractional polynomials having errors close to the machinery's precision. This work ends with the integration of the reducing algorithm in the process of PGD methods to reduce rational polynomials considered as tensor elements. Results show the essential utility of the proposed algorithm: producing parametric solutions, with rational polynomials to solve parametric nonlinear equations. [ABSTRACT FROM AUTHOR]

We study the finite field extension estimates for Hamming varieties Hj, j ∈ Fq*, defined by Hj = {x ∈ Fqd: ∏k=1d xk = j}, where Fq^d denotes the d-dimensional vector space over a finite field Fq with q elements. We show that although the maximal Fourier decay bound on Hj away from the origin is not good, the Stein-Tomas L2 → Lr extension estimate for Hjholds. [ABSTRACT FROM AUTHOR]

For a prime p and a positive integer k , let q = p k and F q n be the extension field of F q. We derive a sufficient condition for the existence of a primitive element α in F q n such that α 3 − α + 1 is also a primitive element of F q n , a sufficient condition for the existence of a primitive normal element α in F q n over F q such that α 3 − α + 1 is a primitive element of F q n , and a sufficient condition for the existence of a primitive normal element α in F q n over F q such that α 3 − α + 1 is also a primitive normal element of F q n over F q. [ABSTRACT FROM AUTHOR]

In this paper, we cryptanalyzed a recently proposed encryption scheme that uses elliptic curves over a finite field. The security of the proposed scheme depends upon the elliptic curve discrete logarithm problem. Two secret keys are used to increase the security strength of the scheme as compared to traditionally used schemes that are based on one secret key. In this scheme, if an adversary gets one secret key then he is unable to get the contents of the original message without the second secret key. Our analysis shows that the proposed scheme is not secure and unable to provide the basic security requirements of the encryption scheme. Due to our successful cryptanalysis, an adversary can get the contents of the original message without the knowledge of the secret keys of the receiver. To mount the attack, Mallory first gets the transmitted ciphertext and then uses public keys of the receiver and global parameters of the scheme to recover the associated plaintext message. To overcome the security flaws, we introduced an improved version of the scheme. [ABSTRACT FROM AUTHOR]

Let F q denote the finite field with q elements. In this paper, we study the permutation property of the class of quadrinomials x 3 + a x q + 2 + b x 2 q + 1 + c x 3 q ∈ F q 2 [ x ] , where char (F q) ∈ { 3 , 5 }. With some additional assumption on the coefficients, we propose several new necessary and sufficient conditions on the coefficients that yield permutation quadrinomials. [ABSTRACT FROM AUTHOR]

Let Sn be the symmetric group and An be the alternating group on n symbols. In this article, we have proved that if F is a finite field of characteristic p > n, then there does not exist a normal complement of Sn (n is even) and An (n ≥ 4) in their corresponding unit groups U (F S n) and U (F A n). Moreover, if F is a finite field of characteristic 3, then A4 does not have normal complement in the unit group U (F A 4). [ABSTRACT FROM AUTHOR]

Let p be a prime and let q = p n , with n ≥ 1 an odd integer. We describe a method for the construction of characteristic polynomials of simple non-ordinary abelian varieties of dimension g and p-rank g − 1 or g − 2 over the finite field F q , when 2 g = ρ b − 1 (ρ − 1) for some prime ρ ≥ 3 and integer b ≥ 1. [ABSTRACT FROM AUTHOR]

We give the characterization of the unit group of FqSL(2, Z5), where Fq is a finite field with q = pk elements for prime p > 5, and SL(2, Z5) denotes the special linear group of 2 × 2 matrices having determinant 1 over the cyclic group Z5. [ABSTRACT FROM AUTHOR]

We consider the problem of bounding the dimension of Hilbert cubes in a finite field F p that does not contain any primitive roots. We show that the dimension of such Hilbert cubes is O ε (p 1 / 8 + ε) for any ε > 0 , matching what can be deduced from the classical Burgess estimate in the special case when the Hilbert cube is an arithmetic progression. We also consider the dual problem of bounding the dimension of multiplicative Hilbert cubes avoiding an interval. [ABSTRACT FROM AUTHOR]

In 2006, Hubert, Mauduit and Sárközy extended the notion of binary sequences to n-dimensional binary lattices and introduced the measures of pseudorandomness of binary lattices. In 2011, Gyarmati, Mauduit and Sárközy extended the notions of family complexity, collision and avalanche effect from binary sequences to binary lattices. In this paper, we construct pseudorandom binary lattices by using cyclotomic classes in finite fields and study the pseudorandom measure of order k, family complexity, collision and avalanche effect. Results indicate that such binary lattices are “good,” and their families possess a nice structure in terms of family complexity, collision and avalanche effect.

n-to-1 mappings have many applications in combinatorial design, coding theory and cryptography. In this paper, by using piecewise method and monomials on subsets of q + 1-th roots of unity, we show a class of n-to-1 binomials having the form xr (a + xs(q - 1)) over Fq². [ABSTRACT FROM AUTHOR]

Semi-regular sequences over F 2 are sequences of homogeneous elements of the algebra B (n) = F 2 [ X 1 ,... , X n ] / (X 1 2 ,... , X n 2) , which have as few relations between them as possible. It is believed that most such systems are F 2 -semi-regular and this property has important consequences for understanding the complexity of Gröbner basis algorithms such as F4 and F5 for solving such systems. In fact even in one of the simplest and most important cases, that of quadratic sequences of length n in n variables, the question of the existence of semi-regular sequences for all n remains open. In this paper we present a new framework for the concept of F 2 -semi-regularity which we hope will allow the use of ideas and machinery from homological algebra to be applied to this interesting and important open question. First we introduce an analog of the Koszul complex and show that F 2 -semi-regularity can be characterized by the exactness of this complex. We show how the well known formula for the Hilbert series of a F 2 -semi-regular sequence can be deduced from the Koszul complex. Finally we show that the concept of first fall degree also has a natural description in terms of the Koszul complex. [ABSTRACT FROM AUTHOR]

We provide an easy method for the construction of characteristic polynomials of simple ordinary abelian varieties ${{\mathcal A}}$ of dimension g over a finite field ${{\mathbb F}}_q$ , when $q\ge 4$ and $2g=\rho ^{b-1}(\rho -1)$ , for some prime $\rho \ge 5$ with $b\ge 1$. Moreover, we show that ${{\mathcal A}}$ is absolutely simple if $b=1$ and g is prime, but ${{\mathcal A}}$ is not absolutely simple for any prime $\rho \ge 5$ with $b>1$. [ABSTRACT FROM AUTHOR]

Reed–Solomon codes are widely used to establish a reliable channel to transmit information in digital communication which has a strong error correction capability and a variety of efficient decoding algorithm. Usually we use the maximum likelihood decoding (MLD) algorithm in the decoding process of Reed–Solomon codes. MLD algorithm relies on determining the error distance of received word. Dür, Guruswami, Wan, Li, Hong, Wu, Yue and Zhu et al. got some results on the error distance. For the Reed–Solomon code C , the received word u is called an ordinary word of C if the error distance d (u , C) = n − deg ⁡ u (x) with u (x) being the Lagrange interpolation polynomial of u. We introduce a new method of studying the ordinary words. In fact, we make use of the result obtained by Y.C. Xu and S.F. Hong on the decomposition of certain polynomials over the finite field to determine all the ordinary words of the standard Reed–Solomon codes over the finite field of q elements. This completely answers an open problem raised by Li and Wan in [On the subset sum problem over finite fields, Finite Fields Appl.14 (2008) 911–929]. [ABSTRACT FROM AUTHOR]

We consider polynomials f(x1, ..., xn) over a finite field that possess the following property: for some element b of the field the set of solutions of the equation f(x1, ..., xn) = b coincides with the set of solutions of some system of linear equations over this field. Such polynomials are said to be multiaffine with respect to the right-hand side b. We obtain the properties of multiaffine polynomials over a finite field. Then we show that checking the multiaffinity with respect to a given right-hand side may be done by an algorithm with polynomial (in terms of the number of variables and summands of the input polynomial) complexity. Besides that, we prove that in case of the positive decision a corresponding system of linear equations may be recovered with complexity which is also polynomial in terms of the same parameters. [ABSTRACT FROM AUTHOR]

A generalization of the method of C. Carlet for constructing differentially 4-uniform permutations of binary vector spaces in even dimension 2k is suggested. It consists in restricting APN-functions in 2k+1 variables to a linear manifold of dimension 2k. The general construction of the method is proposed and a criterion for its applicability is established. Power permutations to which this construction is applicable are completely described and a class of suitable not one-to-one functions is presented. [ABSTRACT FROM AUTHOR]

In this paper, we study binomials having the form x r (a + x 3 (q - 1)) over the finite field F q 2 with q = 2 m , and determine all the r's and coefficients a's making them permutations. For even m or odd m with 3 ∤ m , we prove that the characterization is necessary and sufficient. For the case of odd m and 3 ∣ m , we prove that the corresponding sufficient condition is also necessary for almost all r's. Finally we obtain that the proportion of r's we cannot prove the necessity is only about 1 40 . [ABSTRACT FROM AUTHOR]

Chebotarëv proved that every minor of a discrete Fourier matrix of prime order is nonzero. We prove a generalization of this result that includes analogues for discrete cosine and discrete sine matrices as special cases. We establish these results via a generalization of the Biró–Meshulam–Tao uncertainty principle to functions with symmetries that arise from certain group actions, with some of the simplest examples being even and odd functions. We show that our result is best possible and in some cases is stronger than that of Biró–Meshulam–Tao. Some of these results hold in certain circumstances for non-prime fields; Gauss sums play a central role in such investigations. [ABSTRACT FROM AUTHOR]

Let 𝔽q[ɛ] := 𝔽q [X]/(X4 − X3) be a finite quotient ring where ɛ4 = ɛ3, with 𝔽q is a finite field of order q such that q is a power of a prime number p greater than or equal to 5. In this work, we will study the elliptic curve over 𝔽q[ɛ], ɛ4 = ɛ3 of characteristic p ≠ 2, 3 given by homogeneous Weierstrass equation of the form Y2Z = X3 + aXZ2 + bZ3 where a and b are parameters taken in 𝔽q[ɛ]. Firstly, we study the arithmetic operation of this ring. In addition, we define the elliptic curve Ea,b(𝔽q[ɛ]) and we will show that Eπ0(a),π0(b)(𝔽q) and Eπ1(a),π1(b)(𝔽q) are two elliptic curves over the finite field 𝔽q, such that π0 is a canonical projection and π1 is a sum projection of coordinate of element in 𝔽q[ɛ]. Precisely, we give a classification of elements in elliptic curve over the finite ring 𝔽q[ɛ]. [ABSTRACT FROM AUTHOR]

We perform an opportunistic search for cubic surfaces over small fields of characteristic two. The starting point of our work is a list of surfaces complied by Dickson over the field with two elements. We consider the nonsingular ones arising in Dickson’ s work for the fields of larger orders of characteristic two. We investigate the properties such as the number of lines, singularities and automorphism groups. The problem of determining the possible numbers of lines of a nonsingular cubic surface over the fields of C,R,Q, Fq where q odd, F2 was considered by Cayley and Salmon, Schläfli, Segre, Rosati and Dickson, respectively. Our work contributes this problem over the larger fields of even characteristic. Besides that we investigate the structure of nonsingular surfaces with 15 and 9 lines. This work is a contribution to the study of nonsingular cubic surfaces with less than 27 lines. [ABSTRACT FROM AUTHOR]

We investigate the lattice of clones that are generated by a set of functions that are induced on a finite field F by monomials. We study the atoms and coatoms of this lattice and investigate whether this lattice contains infinite ascending chains, or infinite descending chains, or infinite antichains.We give a connection between the lattice of these clones and semi-affine algebras. Furthermore, we show that the sublattice of idempotent clones of this lattice is finite and every idempotent monomial clone is principal. [ABSTRACT FROM AUTHOR]