All one polynomial
Encyclopedia
An all one polynomial is a polynomial used in finite field
s, specifically GF(2) (binary
). The AOP is a 1-equally spaced polynomial.
An AOP of degree m has all terms from xm to x0 with coefficients of 1, and can be written as
or
or
thus the roots of the all one polynomial of degree m are all (m+1)th roots of unity other than unity itself.
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
.
Over
, the AOP is irreducible whenever m + 1 is prime p, and therefore in these cases, the pth cyclotomic polynomial
.
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
s, specifically GF(2) (binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
). The AOP is a 1-equally spaced polynomial.
An AOP of degree m has all terms from xm to x0 with coefficients of 1, and can be written as
or
or
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 weightHamming weightThe Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1's in the string...
of the AOP is m + 1 - The AOP is irreducibleIrreducible polynomialIn mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....
if and only if m + 1 is prime and 2 is a primitive rootPrimitive root modulo nIn modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g modulo n. In other words, g is a generator of the multiplicative group of integers modulo n...
modulo m + 1 - The only AOP that is a primitive polynomialPrimitive polynomialIn field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field GF...
is x2 + 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
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
and cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
.
Over
, the AOP is irreducible whenever m + 1 is prime p, and therefore in these cases, the pth cyclotomic polynomialCyclotomic polynomial
In algebra, the nth cyclotomic polynomial, for any positive integer n, is the monic polynomial:\Phi_n = \prod_\omega \,where the product is over all nth primitive roots of unity ω in a field, i.e...
.