All one polynomial

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

YouTube Encyclopedic

1/3
Views:
109 831
16 931
1 329

Transcription

. . . In this segment, we're going to talk about Lagrangian interpolation, and I'm just going to show you the theory of Lagrangian interpolation in this segment.|We're not going to derive the Lagrangian interpolation in this particular segment just to show you the formulas of it. So, as we know that if somebody gives us a certain number of data points, so let's suppose somebody gives us four data points, then I know that if I'm going to draw some kind of a polynomial through it, it'll be a third-order polynomial.|So if somebody's giving you one, two, three, four data points and wants to say that, hey, go ahead and find out the polynomial which goes through those four points, it will be a third-order polynomial.|So it will be a third-order polynomial. Now, we have already talked about in the previous segments how to find this third- order polynomial by using something called the direct method, and something called the Newton's divided difference method. . So those are the two methods we have already talked about how to find this polynomial.|So it is the same polynomial whether you are using direct method or Newton's divided difference method, because it has been shown in another segment, that if somebody gives you a certain number of specified points, where all the xs are different, then the polynomial which goes through those particular points is unique.|So many times people say that one should not call it Lagrangian interpolation, or Newton's divided difference method interpolation, we should call it as the form, Lagrangian form of polynomial interpolation, but doesn't really matter until the time you realize that the polynomial, no matter which number you're going to use, through a certain number of specified points, if you're doing polynomial interpolation through n points, the polynomial which will go through those number of points is unique. So what does Lagrangian interpolation look like?|It looks like as follows, that given, let's suppose, n plus 1 data points, so if somebody's giving you n plus 1 data points, like x0, y0, x1, y1, all the way up to xn, yn.|So somebody's giving you n plus 1 data points, of course we are already saying that all these x0, x1, x2, all the way up to xn, they are different from each other.|In that case, the nth-order polynomial, so the Lagrangian form of interpolation, or Lagrangian polynomial interpolant, looks like of this form, this n stands for that it's the nth-order polynomial, looks like this summation here, i equal to 0 to n Li . . . let me not write my L like that, let me just write my L as it is in the notes, Li of x times the value of the function at the x points. So basically what you have is that you have Li of x, which is a function of x.|So these are the weighting functions basically, which you are giving to the values of the function at different values of x, because i is going from 0 to n, so it's basically the values of the function at x0, x1, xn.|So keep in mind that f of xi is nothing but yi, okay?|So there's no difference between the point at yi, which is given to you, like y0, y1, yn, that's the same as the value of the function at xi. So let's go ahead and see that what this weighting function is, so you have this weighting function . . . weighting function Li . . . Li of x.|So we want to see what that weighting function Li of x looks like. So I'm going to write it on the board here so that, because I will show it in expansion, that's why I'm writing it here.|Li of x is written as a product, so the Pi . . . the Pi symbol stands for the product for j equal to 0 to n, where n is the number of . . . order of the polynomial, j not equal to i, you're going to find the product of this quantity, x minus xj, divided by xi minus xj, that's what you're going to find the product of. So again, keep in mind that it is a function of x, but the other . . . the other things which are in this product are the values of x themselves at different points.|Now, if you were going to expand it, because sometimes people get intimidated by this particular symbol of product, then also we're saying j is not equal to i, so I'm going to show you an expanded view, that way you will have a little bit better understanding of it.|Now, first you've got to understand this is your Li x here, so this i is going to be same once your i is fixed. So you'll find out that as I start writing the expanded version of this, this number, or this xi, is not going to change, because the product is going . . . the product lower limit and upper limit on j, j equal to 0 to n, of course, j is not equal to i.|So you'll have x minus x0, because that's the first value of j it's going to take, divided by xi, is going to stay the same for all of these cases, minus x0.|So this and this number is exactly the same, then what's going to happen is next time you're going to get x minus x1, you're going to get x1, divided by xi minus x1, and this is going to continue to take place all the way up to x minus x-sub-i-minus-1, divided by xi minus x-sub-i-minus-1.|The reason why I went all the way up to that particular term is because j is not equal to i, so I'm just writing the term which is before j equal to i, and the next term, since it says j is not equal to i, I will have not x minus xi, but x-sub-i-plus-1, that's what I will have, divided by xi minus x-sub-i-plus-1, all the way up to the last term, which will be x minus xn, divided by xi minus xn. So this is the term which you'll have to calculate as the weighting function for each i, where i is going from 0 to n, so that's how this is going to work out for your . . . for the . . . for the Lagrangian interpolation.|And that is the end of this segment.|We'll take some examples in the next . . . we'll take examples in the next three segments.|And this is the end of this segment. . . .

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 _{i=0}^{m}x^{i}

AOP_{m}(x)=x^{m}+x^{m-1}+\cdots +x+1

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:

The Hamming weight of the AOP is m + 1, the maximum possible for its degree^[3]
The AOP is irreducible if and only if m + 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)
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 and cryptography.^[1]

Over $\mathbb {Q}$ , the AOP is irreducible whenever m + 1 is a prime p, and therefore in these cases, the pth cyclotomic polynomial.^[4]

References

^ ^a ^b ^c 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.
^ Itoh, Toshiya; Tsujii, Shigeo (1989), "Structure of parallel multipliers for a class of fields GF(2^m)", 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, MR 1136200.

External links

all one polynomial at PlanetMath.

This page was last edited on 26 June 2023, at 11:17

From Wikipedia, the free encyclopedia