Misplaced Pages

All one polynomial

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Polynomial in which all coefficients are one

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. The AOP is a 1-equally spaced polynomial.

Definition

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

A O P m ( x ) = ∑ i = 0 m x i {\displaystyle AOP_{m}(x)=\sum _{i=0}^{m}x^{i}}

or

A O P m ( x ) = x m + x m − 1 + ⋯ + x + 1 {\displaystyle AOP_{m}(x)=x^{m}+x^{m-1}+\cdots +x+1}

or

A O P m ( x ) = x m + 1 − 1 x − 1 . {\displaystyle 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:

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 Q {\displaystyle \mathbb {Q} } , the AOP is irreducible whenever m + 1 is a prime p, and therefore in these cases, the pth cyclotomic polynomial.

References

  1. ^ 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)", 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.

External links

Categories: