All one polynomial

All one polynomial

An all one polynomial (AOP) is a polynomial used in finite fields, specifically GF(2) (binary). The AOP is a 1-equally spaced polynomial.

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

:AOP(x) = sum_{i=0}^{m} x^i

or

:AOP(x) = x^m + x^{m-1} + cdots + x + 1

or

:(x-1)AOP(x) = x^{m+1} - 1

thus the roots of the all one polynomial are all roots of unity.

Properties

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

*The Hamming weight of the AOP is "m" + 1
*The AOP is irreducible if and only if "m" + 1 is prime and 2 is a primitive root modulo "m" + 1
*The only AOP that is a primitive polynomial is "x"2 + 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.

Over mathbb{Q}, the AOP is irreducible whenever "m + 1" is prime p, and therefore in these cases, the "p"th cyclotomic polynomial.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Polynomial — In mathematics, a polynomial (from Greek poly, many and medieval Latin binomium, binomial [1] [2] [3], the word has been introduced, in Latin, by Franciscus Vieta[4]) is an expression of finite length constructed from variables (also known as… …   Wikipedia

  • Polynomial hierarchy — In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co NP to oracle machines.DefinitionsThere are multiple equivalent definitions of the classes of the polynomial …   Wikipedia

  • Polynomial conjoint measurement — is an extension of the theory of conjoint measurement to three or more attributes. It was initially developed by the mathematical psychologists David Krantz (1968) and Amos Tversky (1967). The theory was given a comprehensive mathematical… …   Wikipedia

  • 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 {i=0}^{m} x^{si} for i = 0, 1, ldots, mor:ESP(x) = x^{sm} + x^{s(m 1)} + cdots + x^s +… …   Wikipedia

  • Polynomial ring — In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the …   Wikipedia

  • Polynomial interpolation — In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. In other words, given some data points (such as obtained by sampling), the aim is to find a polynomial which… …   Wikipedia

  • Polynomial long division — In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalised version of the familiar arithmetic technique called long division. It can be done easily by hand,… …   Wikipedia

  • Polynomial factorization — In mathematics and computer algebra, polynomial factorization typically refers to factoring a polynomial into irreducible polynomials over a given field. Formulation of the questionOther factorizations, such as square free factorization exist,… …   Wikipedia

  • Polynomial-time approximation scheme — In computer science, a polynomial time approximation scheme (abbreviated PTAS) is a type of approximation algorithm for optimization problems (most often, NP hard optimization problems).A PTAS is an algorithm which takes an instance of an… …   Wikipedia

  • Newton polynomial — In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is the interpolation polynomial for a given set of data points in the Newton form. The Newton polynomial is sometimes called Newton s… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”