mersenneforum.org > Math square root modulo prime
 Register FAQ Search Today's Posts Mark Forums Read

 2010-02-16, 13:32 #1 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 23518 Posts square root modulo prime In the book of Crandall and Pomerance, it is given that For solving the equation x2=a (mod p) to find out x when a, p are being given, and then where p is a prime number. If p is of the prime 3 (mod 4) since a(p-1)/2 = 1 (mod p) a is always a quadratic residue mod p a(p+1)/2 = a (mod p) x = $\sqrt a$ mod p = a(p+1)/4 x will always take two values, that sum up to p, but either result is OK, the other value can be quite easily calculated by using (p-x). If p is of form 5 (mod 8) a(p-1)/2 = 1 (mod p) a(p+3)/2 = a2 (mod p) a(p+3)/8 = either $\sqrt a$ (mod p) or $\sqrt {-a}$ (mod p) since p is of form 1 (mod 4), if a is quadratic residue (mod p), so is (p-a) which is not the case at all if p is of form 3 (mod 4) Here that we don't want $\sqrt {-a}$ (mod p), if that case occurs, we multiply by $\sqrt {-1}$ (mod p) Since Legendre symbol (2/p) = (-1)(m[sup]2-1)/8[/sup], which is equal to -1 if p is of form 5 (mod 8), 2 is a quadratic non residue (mod p) in this case. 2(p-1)/2 = -1 (mod p) 2(p-1)/4 = $\sqrt {-1}$ (mod p) Thus is x2 = -a (mod p), then x := 2(p-1)/4x My clarification lies when p is of form 1 (mod 8) In the book it is given that to solve up the congruence x2 = a (mod p) such that a(p-1)/2 = 1 (mod p) Let (p-1) = 2st, where t is odd. The group order of a (mod p) is a divisor of 2st. Let d be a quadratic non-residue (mod p) with d(p-1)/2 = -1 (mod p) Let A = at (mod p), and then D = dt (mod p) Now that the group order of A (mod p) is a divisor of 2s-1, and then group order of D (mod p) is exactly equal to 2s only. With the powers of D in reverse, the group order of D-1 (mod p) is exactly 2s as well. In the book, it is given that solving for $\mu$ is a special case of the discrete logarithm problem, that we have within our hands is relatively simple. Thus, for some value $\mu$, we have that (D-1)2 $$\mu$$ = A (mod p) = at (mod p) atD2 $$\mu$$ = 1 (mod p) at+1D2 $$\mu$$ = a (mod p) x = $\sqrt a$ (mod p) = a(t+1)/2D$$\mu$$ (mod p) My questions (1) Since the group order of A (mod p) is a divisor of 2s-1 and then that group order of D-1 (mod p) is a exactly equal to 2s does it not imply that $(D^{-1})^{2^{\mu}} \equiv A\ (mod\ p)$ i.e. the power of D-1 which is equal to A is a power of 2? Why is it given within the book that for some value of $\mu$ we have that $(D^{-1})^{2 \mu} \equiv A\ (mod\ p)$ (2) Since the group order of A (mod p) is a divisor of 2s-1 The group order of D-1 (mod p) is a exactly equal to 2s The group order of D (mod p) is a exactly equal to 2s Shouldn't it be always true that $(D)^{2 \mu} \equiv A\ (mod\ p)$ and then also that $(D^{-1})^{2 \mu} \equiv A\ (mod\ p)$? Let me demonstrate this case with an example: For x2 = 491 (mod 1009) The group order of 491 (mod 1009) is 252. t = 63. Let d = 499. d need not be a primitive root at all, a quadratic non-residue is enough, right? The group order of d (mod 1009) is equal to 1008, only if d is a primitive root of (mod 1009). A = at (mod p) = 49163 (mod 1009) D = dt (mod p) = 49963 (mod 1009) D-1 = (4991007)63 (mod 1009) since we always have that D-1 (mod n) = D[TEX]\phi(n)[/TEX]-1 (mod n), and then that $\phi(n)$ = n-1, when the case that n is prime. Now that the value of $2 \mu$ is equal to 4 (I doubt that it should be always a power of 2 only) A = 49163 (mod 1009) = 469 (mod 1009) D = 49963 (mod 1009) = 183 (mod 1009) D4 = 540 (mod 1009) D-1 = 49963441 (mod 1009) = 805 (mod 1009) (D-1)4 = 469 (mod 1009) Luckily enough, it is somehow true that $(D^{-1})^{2 \mu} \equiv A\ (mod\ p)$ Shouldn't it be always true that $(D)^{2 \mu} \equiv A\ (mod\ p)$ as well as that $(D^{-1})^{2 \mu} \equiv A\ (mod\ p)$? if the group order of both are same always? Is the latter being always true? I am becoming unsure of that case as well...
 2010-02-16, 21:25 #2 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts 3) Also since we have that p-1 = 2st, where t is odd. if p = 3 (mod 4), then s = 1 if p = 5 (mod 8), then s = 2 if p = 9 (mod 16), then s = 3 if p = 17 (mod 32), then s = 4, etc. Since a(p-1)/2 = 1 (mod p), since a is quadratic residue (mod p) a2[SUP]s-1t[/SUP] = 1 (mod p) Thus, either at = 1 (mod p) or a2[SUP]it[/SUP] = -1 (mod p) for some value of i between 0 & s-2. d2[SUP]s-1t[/SUP] = -1 (mod p) Group order of A = at (mod p) is a divisor of 2s-1 Group order of D = dt (mod p) is exactly equal to 2s Group order of A = at (mod p) = 2i+1 Thus, is it always true that if p = 3 (mod 4), then i = 1 if p = 5 (mod 8), then i = 2 if p = 9 (mod 16), then i = 3 if p = 17 (mod 32), then i = 4, etc. for solving up the equation $(D^{-1})^{2 \mu} \equiv A\ (mod\ p)$ such that if p = 2n-1+1 (mod 2n), then the value of $\mu$ is always equal to ...

 Similar Threads Thread Thread Starter Forum Replies Last Post davar55 Lounge 0 2016-03-16 20:19 paul0 Factoring 10 2015-01-19 12:25 Damian Math 3 2010-01-01 01:56 Yamato Math 6 2008-02-25 15:08 davar55 Puzzles 3 2007-09-05 15:59

All times are UTC. The time now is 19:39.

Wed Dec 1 19:39:19 UTC 2021 up 131 days, 14:08, 1 user, load averages: 1.49, 1.52, 1.50

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.