ELI15: Explain why Lagrange basis is more natural to use.

[str4d]

Which section of the Halo 2 book were you reading?

4.2 Polynomials, subsection "Lagrange basis functions"

What was unclear?

Why the Lagrange basis is " a more natural expression" either in general, or specifically when working over a multiplicative subgroup of order n.

What would help to make it clearer to you?

An addition or rewrite that includes the following points:

• If we try to encode data as the coefficients of a polynomial in the monomial basis, then if you apply any operations to those polynomials you end up with meaningless coefficients. If instead you encode information in the evaluations of the polynomials, then operations on polynomials is equivalent to operations on their evaluations. The Lagrange basis represents a polynomial directly in terms of its evaluations - it's like having a vector of your data.
• The subgroup is isomorphic to the integers modulo n (it "wraps around"). This means that when you are doing things like permutation arguments, it's easier to create an efficient permutation.

[daira]

The latter point, about the group wrapping around, isn't actually very important. We may not end up relying on that at all.