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
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6753/discussion-between-amzoti-and-nick)2012-12-16

0 Answers 0