I was reading this paper, on page number 29, 2nd paragraph it is written that "take the coefficients of $ \gamma $ modulo q and applying an algorithm for taking square roots in the finite field Z[ $ \alpha $ ]/Q (see [19; 16, Section 4.6.2, Exercise 15]), we find an element $ \delta_{0} $ (mod Q) such that $ \delta_{0}^{2}\gamma $ = l mod Q". I cannot understand how we can find this $ \delta_{0} $.

  • $\begingroup$ Don't you think that the algorithm for doing that is in one (or both) of those references? Did you check them out? $\endgroup$ – Jyrki Lahtonen Jun 21 '16 at 18:40
  • $\begingroup$ I checked them out but couldn't understand the method the author is trying to direct. $\endgroup$ – Mayank Jun 21 '16 at 20:13
  • $\begingroup$ In that case it might be better that you link to that reference, and make a more specific question about its content. The way it is now, anyone willing to try to help you needs to first follow up your link, then see what references 16 and 19 are, then locate copies of them, and read the surrounding material. That may be asking too much. Calculating square roots in finite fields (which is what I suspect this is about) may or may not be easy, depending on how the field arithmetic is implemented. $\endgroup$ – Jyrki Lahtonen Jun 22 '16 at 6:20
  • $\begingroup$ I have added the reference links. $\endgroup$ – Mayank Jun 22 '16 at 9:13
  • $\begingroup$ I could just understand that one reference states something about rabin method and the other gives an idea about Berlekamp and Zassenhaous method. But, I could not properly understand how using these methods gives us the square root in finite field. The thing that I am struck at is how can we map our square root from Z[$\alpha$] to Fp. Because once we can do that, we can find the square root in Fp(using rabin method)and raise it by newton iteration. $\endgroup$ – Mayank Jun 22 '16 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.