mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, an all one polynomial (AOP) is a

polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...

in which all

coefficient In mathematics, a coefficient is a Factor (arithmetic), multiplicative factor involved in some Summand, term of a polynomial, a series (mathematics), series, or any other type of expression (mathematics), expression. It may be a Dimensionless qu ...

s 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 Multiplication is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division (mathematics), division. The result of a multiplication operation is called a ''Product (mathem ...

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...

s of characteristic two.. The AOP is a 1-

equally spaced polynomial An equally spaced polynomial (ESP) is a polynomial used in finite fields, specifically GF(2) (binary). An ''s''-ESP of degree ''sm'' can be written as: :ESP(x) = \sum_^ x^ for i = 0, 1, \ldots, m or :ESP(x) = x^ + x^ + \cdots + x^s + 1. Prope ...

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_^ x^i

or :

AOP_m(x) = x^m + x^ + \cdots + x + 1

or :

AOP_m(x) = .

Thus the

roots A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusin ...

of the all one polynomial of degree ''m'' are all (''m''+1)th

roots of unity In mathematics, a root of unity is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group char ...

other than unity itself.

Properties

Over

GF(2) (also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field with two elements. is the Field (mathematics), field with the smallest possible number of elements, and is unique if the additive identity and the multiplicative identity ...

the AOP has many interesting properties, including: *The

Hamming weight The Hamming weight of a string (computer science), 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 mo ...

of the AOP is ''m'' + 1, the maximum possible for its degree *The AOP is irreducible

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

''m'' + 1 is

prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

and 2 is a primitive root modulo ''m'' + 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 Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and computer data storage, data sto ...

and

cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...

. Over

\mathbb

, the AOP is irreducible whenever ''m'' + 1 is a prime ''p'', and therefore in these cases, the ''p''th

cyclotomic polynomial In mathematics, the ''n''th cyclotomic polynomial, for any positive integer ''n'', is the unique irreducible polynomial with integer coefficients that is a divisor of x^n-1 and is not a divisor of x^k-1 for any Its roots are all ''n''th prim ...

References

External links

*{{PlanetMath, urlname=AllOnePolynomial, title=all one polynomial Field (mathematics) Polynomials