Siguiente: Trace Arriba: Algorithms for field arithmetic Anterior: Squaring

Square root

Since $\mathbb{F}_{2^n}^*$ is a cyclic group of order $2^n-1$ we have that for all $A(X)\in\mathbb{F}_{2^n}$: $A(X) = A(X)^{2^n} = \left(A(X)^{2^{n-1}}\right)^2,$ thus $\sqrt{A(X)} = A(X)^{2^{n-1}}$, and being squaring a linear map:

$$A(X)=\sum_{i=0}^{n-1}a_iX^i\ \Longrightarrow\ \sqrt{A(X)} = ... ...{n-1}}\right)^i = \sum_{i=0}^{n-1}a_i\left(\sqrt{X}\right)^i.$$ (8)

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

$$\sqrt{A(X)} = \sum_{i=0}^{k-1}a_{2i}\left(\sqrt{X}\right)^{2i} + \sum_{i=0}^{k-1}a_{2i+1}\left(\sqrt{X}\right)^{2i+1}$$

$$= \sum_{i=0}^{k-1}a_{2i}X^i + \sqrt{X}\sum_{i=0}^{k-1}a_{2i+1}X^i%\\$$ (9)

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

$$\sqrt{A(X)} = \sum_{i=0}^{k-1}a_{2i}\left(\sqrt{X}\right)^{2i} + \sum_{i=0}^{k-2}a_{2i+1}\left(\sqrt{X}\right)^{2i+1}$$

$$= \sum_{i=0}^{k-1}a_{2i}X^i + \sqrt{X}\sum_{i=0}^{k-2}a_{2i+1}X^i%\\$$ (10)

and clearly, $\sqrt{X} = X^{2^{n-1}} \bmod p_n(X)$.