mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-02-16, 13:32   #1
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default 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 [tex]\mu[/tex] = A (mod p) = at (mod p)
atD2 [tex]\mu[/tex] = 1 (mod p)
at+1D2 [tex]\mu[/tex] = a (mod p)
x = \sqrt a (mod p) = a(t+1)/2D[tex]\mu[/tex] (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...
Raman is offline   Reply With Quote
Old 2010-02-16, 21:25   #2
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

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 ...
Raman is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 20:21.

Mon Sep 21 20:21:31 UTC 2020 up 11 days, 17:32, 1 user, load averages: 2.47, 2.61, 2.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.