2010-02-16, 13:32 | #1 |
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts |
square root modulo prime
In the book of Crandall and Pomerance, it is given that
For solving the equation x^{2}=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 = 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} = a^{2} (mod p) a^{(p+3)/8} = either (mod p) or (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 (mod p), if that case occurs, we multiply by (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} = (mod p) Thus is x^{2} = -a (mod p), then x := 2^{(p-1)/4}x My clarification lies when p is of form 1 (mod 8) In the book it is given that to solve up the congruence x^{2} = a (mod p) such that a^{(p-1)/2} = 1 (mod p) Let (p-1) = 2^{s}t, where t is odd. The group order of a (mod p) is a divisor of 2^{s}t. Let d be a quadratic non-residue (mod p) with d^{(p-1)/2} = -1 (mod p) Let A = a^{t} (mod p), and then D = d^{t} (mod p) Now that the group order of A (mod p) is a divisor of 2^{s-1}, and then group order of D (mod p) is exactly equal to 2^{s} only. With the powers of D in reverse, the group order of D^{-1} (mod p) is exactly 2^{s} as well. In the book, it is given that solving for is a special case of the discrete logarithm problem, that we have within our hands is relatively simple. Thus, for some value , we have that (D^{-1})^{2 [tex]\mu[/tex]} = A (mod p) = a^{t} (mod p) a^{t}D^{2 [tex]\mu[/tex]} = 1 (mod p) a^{t+1}D^{2 [tex]\mu[/tex]} = a (mod p) x = (mod p) = a^{(t+1)/2}D^{[tex]\mu[/tex]} (mod p) My questions (1) Since the group order of A (mod p) is a divisor of 2^{s-1} and then that group order of D^{-1} (mod p) is a exactly equal to 2^{s} does it not imply that 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 we have that (2) Since the group order of A (mod p) is a divisor of 2^{s-1} The group order of D^{-1} (mod p) is a exactly equal to 2^{s} The group order of D (mod p) is a exactly equal to 2^{s} Shouldn't it be always true that and then also that ? Let me demonstrate this case with an example: For x^{2} = 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 = a^{t} (mod p) = 491^{63} (mod 1009) D = d^{t} (mod p) = 499^{63} (mod 1009) D^{-1} = (499^{1007})^{63} (mod 1009) since we always have that D^{-1} (mod n) = D^{[TEX]\phi(n)[/TEX]-1} (mod n), and then that = n-1, when the case that n is prime. Now that the value of is equal to 4 (I doubt that it should be always a power of 2 only) A = 491^{63} (mod 1009) = 469 (mod 1009) D = 499^{63} (mod 1009) = 183 (mod 1009) D^{4} = 540 (mod 1009) D^{-1} = 499^{63441} (mod 1009) = 805 (mod 1009) (D^{-1})^{4} = 469 (mod 1009) Luckily enough, it is somehow true that Shouldn't it be always true that as well as that ? 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 |
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts |
3) Also since we have that
p-1 = 2^{s}t, 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) a^{2[SUP]s-1}t[/SUP] = 1 (mod p) Thus, either a^{t} = 1 (mod p) or a^{2[SUP]i}t[/SUP] = -1 (mod p) for some value of i between 0 & s-2. d^{2[SUP]s-1}t[/SUP] = -1 (mod p) Group order of A = a^{t} (mod p) is a divisor of 2^{s-1} Group order of D = d^{t} (mod p) is exactly equal to 2^{s} Group order of A = a^{t} (mod p) = 2^{i+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 such that if p = 2^{n-1}+1 (mod 2^{n}), then the value of is always equal to ... |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Square Root Days | davar55 | Lounge | 0 | 2016-03-16 20:19 |
NFS Square root problems | paul0 | Factoring | 10 | 2015-01-19 12:25 |
Square root of 3 | Damian | Math | 3 | 2010-01-01 01:56 |
Computing the cube root modulo p | Yamato | Math | 6 | 2008-02-25 15:08 |
Divisible up to Square Root | davar55 | Puzzles | 3 | 2007-09-05 15:59 |