An AOP of
degreem 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 weight of the AOP is m + 1, the maximum possible for its degree[3]
The AOP is
irreducibleif and only ifm + 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)
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 , the AOP is irreducible whenever m + 1 is a prime p, and therefore in these cases, the pth
cyclotomic polynomial.[4]
^Itoh, Toshiya; Tsujii, Shigeo (1989), "Structure of parallel multipliers for a class of fields GF(2m)", 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,
MR1136200.