My Math Forum Trivial quadratic residues for prime powers

 Number Theory Number Theory Math Forum

 March 30th, 2010, 03:14 PM #1 Newbie   Joined: Mar 2010 Posts: 2 Thanks: 0 Trivial quadratic residues for prime powers (For convenience, "=" means congruent and "!=" means not congruent when followed by (mod m). If anyone can tell me how to type the actual symbols, please do so as this is my first time posting on this forum.) Context: I am coding a solver (in Java) for generalized Pell equations of the form x^2 - Dy^2 = N using a paper of John Robertson as a reference. The Lagrange-Matthews-Mollin algorithm requires a complete solution set to the congruence z^2 = D (mod |m|) for various m. So, I've handled factoring |m| into prime powers p^k and am OK with Tonelli Shanks and Hensel lifting when D != 0 (mod p), but I'm stuck on the supposedly trivial case D = 0 (mod p). Say for example we want to find all solutions to x^2 = 98 (mod 7^3). It is easy to check that the solutions are x = 21, 28, 70, 77, 119, 126, 168, 175, 217, 224, 266, 273, 315, 322 (mod 7^3). I can see that the solution set is simply x = +-21 (mod 49). Likewise, I have determined that the solution set to x^2 = 98 (mod 7^4) is x = +-70 (mod 7^3). What would be an efficient algorithm for the general case? And will prime p = 2 need to be treated separately from primes p > 2? I have limited number theory background, so I'm probably missing something basic. The literature I've consulted seems to pass off such problems as trivial or easy or irrelevant, leaving them as exercises to the reader, either explicitly or by omission. After I've completed this step, straightforward application of the Chinese Remainder Theorem will allow me to complete the overall problem. Any help would be appreciated.
 March 31st, 2010, 08:20 AM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Trivial quadratic residues for prime powers So you want to solve $z^2\equiv np^a\pmod{p^b}$ with gcd(n, p) = 1. (You can of course solve mod each of the prime powers of m and CRT them together to get a solution for mod m rather than just mod p^b.) If a >= b, then of course $z^2\equiv0\pmod{p^b}$ and so the possibilities for z are just multiples of $p^{\lceil b/2\rceil}$. If a < b and a is odd, then there are no solutions. If a < b and a is even, then $z=kp^{a/2}$ with k and p coprime. You should be able to find solutions to $x^2\equiv n\pmod{p^{b-a}}$ and multiply them by $p^{a/2}$. In your example, $z^2\equiv2\pmod7^2\pmod{7^3}$, solve $x^2\equiv2\pmod7$ and multiply the solution by 7. I've not worked with this before, but this seems to work. Let me know if you get your program finished, I'd be curious to see the result.
 April 1st, 2010, 10:21 PM #3 Newbie   Joined: Mar 2010 Posts: 2 Thanks: 0 Re: Trivial quadratic residues for prime powers Thank you! I was looking for an analytic approach like the one you presented. After reading your post, it seems very natural to have broken the problem down the way you did, and only the last part struck me as being potentially tricky to come up with. As a novice, I experience many "Why didn't I think of that?" moments. I have not implemented your method yet, as I have some other more pressing projects, but when I find time to complete everything I will post my code.

 Tags powers, prime, quadratic, residues, trivial

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post smslca Number Theory 5 October 12th, 2012 09:48 AM smslca Number Theory 0 October 12th, 2012 01:34 AM slippy Number Theory 7 October 26th, 2009 02:40 PM soandos Number Theory 12 December 5th, 2007 09:26 PM MutenRo Number Theory 12 September 30th, 2007 12:13 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top