1
$\begingroup$

I am trying to implement an algorithm that can compute the square root of a quadratic residue mod a prime power. For integers $a$ such that

  1. $p\not\mid a$
  2. $p\neq 2$

it's relatively straightforward using Hensel's Lemma to lift the roots from $\mathbb{Z}/p\mathbb{Z}$ to $\mathbb{Z}/p^k\mathbb{Z}$. However, in the cases where either (or both) of the two conditions fail, I'm not certain what to do. I think the more general version of Hensel's lemma may be applicable, but I'm not sure how to use it. Wikipedia mentions "an algorithm of Gauss", but doesn't provide any links or details.

  • 0
    Maybe this will help? http://mathforum.org/library/drmath/view/70474.html . Additionally, see: [**Cipolla's Algothim**](http://mathoverflow.net/questions/52081/is-there-an-efficient-algorithm-for-finding-a-square-root-modulo-a-prime-power). Also see: **Tonnelli-Shanks Algorithm**.2012-12-16
  • 0
    Ok, the last post on the mathforum page describes the procedure for $p=2$, so that should work fine. On the other link you gave me, the accepted answer says, "if $j$ is odd, give up". I assume that means there are no roots?2012-12-16
  • 0
    Do you have access to the book **A Course in Number Theory and Cryptography** by Neil Koblitz? Look at p. 48, **Square roots modulo $p$**.2012-12-16
  • 0
    That section doesn't mention anything about prime powers though.2012-12-16
  • 0
    Nick, sorry for the bogus reference: Does this help [**see section called Square roots mod p prime**](https://www.cs.rochester.edu/u/www/u/nelson/courses/cryptology/notes/lecture_10.txt)2012-12-16
  • 0
    This also doesn't mention prime powers.2012-12-16
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6753/discussion-between-amzoti-and-nick)2012-12-16

0 Answers 0