I'm programming a solution to HackerRank's Project Euler 100, which is a much stronger variant than the original question, so I have to essentially make a quadratic solver, which involves a lot of quadratic modular equations. I'm trying to implement a full "modular square root" function which can take a number, a prime, and the power of that prime, i.e. find all x such that: $$ x^2 \equiv \text{num} \pmod{\text{prime}^{\text{power}}} $$ It currently works well enough for odd primes, but I have some edge cases that I'm still fleshing out:
I don't understand mod $2^n$ quite yet, but I feel like Hensel's stronger Lemma will help me? Likewise with num $= 0$. Also situations with num having prime as a factor. For example, $x^2 \equiv \text{num} \pmod{{2}^{{8}}}$ has many solutions for a variety of numbers, as does $x^2 \equiv \text{num} \pmod{\text{3}^{\text{power}}}$...
My guess is that Hensel's Stronger Lemma is what will let me lift, and even then, I'm not quite sure algorithmically what this implies. Hensel's Stronger Lemma says that you can lift lower roots to several higher powers, but not all of them, so does that mean I'd need to exhaustively search all qualifying lower roots of a prime to lift to all higher roots?
I am not a number theorist, just teaching myself coding, so a lot of this has been a huge crash course in number theory concepts!