Square root

Square roots over finite fields

Elements of finite fields that have square roots are known as quadratic residues.

Legendre symbols are computed by quadratic reciprocity using an extended Euclidean algorithm to determine whether or not an element of a finite field has a square root.

Several variations on the general method exist .

Extracting square roots by hand

The grade-school arithmetic lesson long forgotten by most adults!

1. Group the digits under the radical in pairs: ${\sqrt {6\quad 55\quad 36}}$. You will get one digit of result for each pair of digits under the radical. That is the original reason for the vinculum or bar commonly placed over the radical, to indicate that it is a problem to be worked out in the style of a long division.
2. Start with the largest digit whose square does not exceed the leftmost digit or pair of digits under the radical.
3. At each step, double the number you have written so far over the radical, append the next digit, the largest that will fit, multiplying by that same digit again and subtracting to calculate the remainder, and then bring down the next pair of digits, as for long division.

${\begin{array}{rrr|rrr}&&&2&5&6\\\hline &&{\sqrt {}}&6&55&36\\{\underline {2}}\times {\underline {2}}&=&4&-4&&\\\hline 2\times 2&=&4~~&2&55&\\4{\underline {5}}\times {\underline {5}}&=&225&-2&25&\\\hline 25\times 2&=&50~~&&30&36\\50{\underline {6}}\times {\underline {6}}&=&3036&&-30&36\\\hline &&&&&0\end{array}}$

${\sqrt {65536}}=256$

The method is based on the identity

$(10x+y)^{2}=100x^{2}+20xy+y^{2}$.