Siguiente: Square root Arriba: Algorithms for field arithmetic Anterior: Multiplication

Squaring

Since $\mathbb{F}_{2^n}$ is a field of characteristic 2, squaring is a linear map, thus

$$A(X)=\sum_{i=0}^{n-1}a_iX^i\ \Longrightarrow\ A(X)^2=\sum_{i=0}^{n-1}a_iX^{2i},$$ (5)

thus only monomials of even exponent appear in $A(X)^2$.

If $n=2k$ is an even number,

$$A(X)^2 = \sum_{i=0}^{k-1}a_iX^{2i} + \sum_{i=k}^{n-1}a_iX^{2i}$$

$$= \sum_{i=0}^{k-1}a_iX^{2i} + X^n\sum_{i=0}^{k-1}a_{k+i}X^{2i}$$

$$= \sum_{i=0}^{k-1}a_iX^{2i} + \left(\sum_{j=0}^{n-1}q_jX^j\right)\left(\sum_{i=0}^{k-1}a_{k+i}X^{2i}\right)%\\$$ (6)

If $n=2k-1$ is an odd number,

$$A(X)^2 = \sum_{i=0}^{k-1}a_iX^{2i} + \sum_{i=k}^{n-1}a_iX^{2i}$$

$$= \sum_{i=0}^{k-1}a_iX^{2i} + X^{n+1}\sum_{i=0}^{k-2}a_{k+i}X^{2i}$$

$$= \sum_{i=0}^{k-1}a_iX^{2i} + \left(\sum_{j=0}^{n-1}q_jX^j\right)\left(\sum_{i=0}^{k-2}a_{k+i}X^{2i+1}\right)%\\$$ (7)

Eq's (6)-(7) determine an algorithm for squaring, which can still be simplified, according to the special form of the irreducible polynomial $p_n(X)$.