HSME |

Content |
---|

Further Modular Arithmetic |

Multiplicative Group and Discrete Log |

Problems & Projects |

Problem Set |

Project |

Solutions |

Exercises Solutions |

Problem Set Solutions |

Misc. |

Definition Sheet |

Full Version |

PDF Version |

## *Finding the square root*Edit

## Legendre SymbolEdit

*.. to be expanded* There is actually a simple way to determine whether *a* is square

Let *g* be a generator of *G* where *G* is the multiplicative group mod *p*. Since all the squares form a group therefore, if *a* is a square, then

and if *a* is not a square then

we shall use these facts in the next section. *.. to be expanded*

## *Finding the square root*Edit

We aim to describe a way to find a square root in mod *m*. Let's start with the simplest case, where *p* is prime. In fact, for square root finding, the simplest case also happens to be the hardest.

If *p* ≡ 3 (mod *4*) then it is easy to find a square root. Just note that if *a* has a square root then

So let us consider primes equivalent to 1 mod 4. Suppose we can find the square root of *a* mod *p*, and let

With the above information, we can find the square of *a* mod *p*^{2}. We let

we want *x*^{2} ≡ a (mod *p*^{2}), so

for some *k* as so , we see that

so if we need to find such that , we simply need to make the subject

- .

*..generalisation* *..example*

*..method for finding a sqr root mod p*