All one polynomial

Last updated June 27, 2023

In mathematics, an all one polynomial (AOP) is a polynomial in which all coefficients are one. Over the finite field of order two, conditions for the AOP to be irreducible are known, which allow this polynomial to be used to define efficient algorithms and circuits for multiplication in finite fields of characteristic two.^[1] The AOP is a 1-equally spaced polynomial.^[2]

Definition

An AOP of degree m has all terms from x^m to x⁰ with coefficients of 1, and can be written as

AOP_{m}(x)=\sum _{i=0}^{m}x^{i}

or

AOP_{m}(x)=x^{m}+x^{m-1}+\cdots +x+1

or

AOP_{m}(x)={x^{m+1}-1 \over {x-1}}.

Thus the roots of the all one polynomial of degree m are all (m+1)th roots of unity other than unity itself.

Properties

Over GF(2) the AOP has many interesting properties, including:

The Hamming weight of the AOP is m + 1, the maximum possible for its degree^[3]
The AOP is irreducible if and only if m + 1 is prime and 2 is a primitive root modulo m + 1^[1] (over GF(p) with prime p, it is irreducible if and only if m + 1 is prime and p is a primitive root modulo m + 1)
The only AOP that is a primitive polynomial is x² + x + 1.

Despite the fact that the Hamming weight is large, because of the ease of representation and other improvements there are efficient implementations in areas such as coding theory and cryptography.^[1]

Over $\mathbb {Q}$ , the AOP is irreducible whenever m + 1 is a prime p, and therefore in these cases, the pth cyclotomic polynomial.^[4]

Related Research Articles

In mathematics, a field $F$ is algebraically closed if every non-constant polynomial in $F [x]$ has a root in $F$ .

In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod $p$ when $p$ is a prime number.

In mathematics, a polynomial is an expression consisting of indeterminates and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example of a polynomial of a single indeterminate $x$ is $x 2 - 4 x + 7$ . An example with three indeterminates is $x 3 + 2 xyz 2 - yz + 1$ .

<span class="mw-page-title-main">Factorization</span> (Mathematical) decomposition into a product

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, $3 \times 5$ is a factorization of the integer $15$ , and $(x - 2)(x + 2)$ is a factorization of the polynomial $x 2 - 4$ .

In algebraic number theory, an algebraic integer is a complex number which is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial whose coefficients are integers. The set of all algebraic integers $A$ is closed under addition, subtraction and multiplication and therefore is a commutative subring of the complex numbers.

<span class="mw-page-title-main">Root of unity</span> Number that has an integer power equal to 1

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power $n$ . Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform.

In mathematics, thenth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of $and is not a divisor of for any k < n . Its roots are all n th primitive roots of unity, where k runs over the positive integers not greater than n and coprime to n . In other words, the n th cyclotomic polynomial is equal to$

In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g$ ^$k$ ≡ $a$ . Such a value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ . So $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ .

In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted for the possible factors, that is, the field to which the coefficients of the polynomial and its possible factors are supposed to belong. For example, the polynomial $x 2 - 2$ is a polynomial with integer coefficients, but, as every integer is also a real number, it is also a polynomial with real coefficients. It is irreducible if it is considered as a polynomial with integer coefficients, but it factors as $if it is considered as a polynomial with real coefficients. One says that the polynomial x 2 - 2 is irreducible over the integers but not over the reals.$

In field theory, a branch of algebra, an algebraic field extension $is called a separable extension if for every, the minimal polynomial of over F is a separable polynomial. There is also a more general definition that applies when E is not necessarily algebraic over F . An extension that is not separable is said to be inseparable .$

In mathematics, Eisenstein's criterion gives a sufficient condition for a polynomial with integer coefficients to be irreducible over the rational numbers – that is, for it to not be factorizable into the product of non-constant polynomials with rational coefficients.

In mathematics, finite field arithmetic is arithmetic in a finite field contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.

In finite field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite field $GF(p m)$ . This means that a polynomial $F (X)$ of degree $m$ with coefficients in $GF(p) = Z / p Z$ is a primitive polynomial if it is monic and has a root $α$ in $GF(p m)$ such that $is the entire field GF(p m) . This implies that α is a primitive (p m - 1)-root of unity in GF(p m) .$

In algebra, Gauss's lemma, named after Carl Friedrich Gauss, is a statement about polynomials over the integers, or, more generally, over a unique factorization domain. Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials.

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.

In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detection and correction.

In field theory, a simple extension is a field extension which is generated by the adjunction of a single element, called a primitive element. Simple extensions are well understood and can be completely classified.

In cryptography, SWIFFT is a collection of provably secure hash functions. It is based on the concept of the fast Fourier transform (FFT). SWIFFT is not the first hash function based on FFT, but it sets itself apart by providing a mathematical proof of its security. It also uses the LLL basis reduction algorithm. It can be shown that finding collisions in SWIFFT is at least as difficult as finding short vectors in cyclic/ideal lattices in the worst case. By giving a security reduction to the worst-case scenario of a difficult mathematical problem, SWIFFT gives a much stronger security guarantee than most other cryptographic hash functions.

In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them.

In number theory, a cyclotomic field is a number field obtained by adjoining a complex root of unity to $Q$ , the field of rational numbers.

References

1 2 3 Cohen, Henri; Frey, Gerhard; Avanzi, Roberto; Doche, Christophe; Lange, Tanja; Nguyen, Kim; Vercauteren, Frederik (2005), Handbook of Elliptic and Hyperelliptic Curve Cryptography, Discrete Mathematics and Its Applications, CRC Press, p. 215, ISBN 9781420034981 .
↑ Itoh, Toshiya; Tsujii, Shigeo (1989), "Structure of parallel multipliers for a class of fields GF(2^m)", Information and Computation, 83 (1): 21–40, doi: 10.1016/0890-5401(89)90045-X .
↑ Reyhani-Masoleh, Arash; Hasan, M. Anwar (2003), "On low complexity bit parallel polynomial basis multipliers", Cryptographic Hardware and Embedded Systems - CHES 2003, Lecture Notes in Computer Science, vol. 2779, Springer, pp. 189–202, doi: 10.1007/978-3-540-45238-6_16 .
↑ Sugimura, Tatsuo; Suetugu, Yasunori (1991), "Considerations on irreducible cyclotomic polynomials", Electronics and Communications in Japan, 74 (4): 106–113, doi:10.1002/ecjc.4430740412, MR 1136200 .

External links

all one polynomial at PlanetMath .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[hehcc-1] 1 2 3 Cohen, Henri; Frey, Gerhard; Avanzi, Roberto; Doche, Christophe; Lange, Tanja; Nguyen, Kim; Vercauteren, Frederik (2005), Handbook of Elliptic and Hyperelliptic Curve Cryptography, Discrete Mathematics and Its Applications, CRC Press, p. 215, ISBN 9781420034981 .

[2] Itoh, Toshiya; Tsujii, Shigeo (1989), "Structure of parallel multipliers for a class of fields GF(2^m)", Information and Computation, 83 (1): 21–40, doi: 10.1016/0890-5401(89)90045-X .

[3] Reyhani-Masoleh, Arash; Hasan, M. Anwar (2003), "On low complexity bit parallel polynomial basis multipliers", Cryptographic Hardware and Embedded Systems - CHES 2003, Lecture Notes in Computer Science, vol. 2779, Springer, pp. 189–202, doi: 10.1007/978-3-540-45238-6_16 .

[4] Sugimura, Tatsuo; Suetugu, Yasunori (1991), "Considerations on irreducible cyclotomic polynomials", Electronics and Communications in Japan, 74 (4): 106–113, doi:10.1002/ecjc.4430740412, MR 1136200 .

[1]

[2]

[3]

[4]