I am stuck with these questions. how to solv these
x^2 = 120 mode 953 using quadratic residue
6x^17 = 31 mod 13 using the properties of logarithms
x^2 = 120 mode 953 using quadratic residue
6x^17 = 31 mod 13 using the properties of logarithms
-
1) 953 is prime; so we can use Legendre symbols.
(120/953) = (2^2/953) * (2/953) (3/953) (5/953), by factoring 120
................= 1 * (2/953) (3/953) (5/953)
................= (-1)^((953^2 - 1)/8) (3/953) (5/953), using (2/p) formula
................= (3/953) (5/953)
................= [(953/3) * (-1)^(952 * 2/4)] * [(953/5) * (-1)^(952 * 4/4)], by Quadratic Reciprocity
................= (953/3) * (953/5)
................= (2/3) * (3/5)
................= -1 * -1, since 2 is not a square mod 3, and 3 is not a square mod 5
................= 1.
Hence, this is solvable.
Using index tables, or trial and error, we find that x = ± 88 (mod 953) are solutions.
------------------
2) Note that 2 is a primitive root mod 13; so I'll use discrete logs base 13.
Note that 31 = 5 (mod 13).
Take logs of both sides:
log 6 + 17 log x = log 5 (mod 13 - 1)
==> 5 + 17 log x = 9 (mod 12), since 2^5 = 6 (mod 13) and 2^9 = 5 (mod 13).
Solve for log x:
5 log x = 4 = -20 (mod 12)
==> log x = -4 (mod 12)
==> log x = 8 (mod 12)
==> x = 2^8 = 9 (mod 13).
I hope this helps!
(120/953) = (2^2/953) * (2/953) (3/953) (5/953), by factoring 120
................= 1 * (2/953) (3/953) (5/953)
................= (-1)^((953^2 - 1)/8) (3/953) (5/953), using (2/p) formula
................= (3/953) (5/953)
................= [(953/3) * (-1)^(952 * 2/4)] * [(953/5) * (-1)^(952 * 4/4)], by Quadratic Reciprocity
................= (953/3) * (953/5)
................= (2/3) * (3/5)
................= -1 * -1, since 2 is not a square mod 3, and 3 is not a square mod 5
................= 1.
Hence, this is solvable.
Using index tables, or trial and error, we find that x = ± 88 (mod 953) are solutions.
------------------
2) Note that 2 is a primitive root mod 13; so I'll use discrete logs base 13.
Note that 31 = 5 (mod 13).
Take logs of both sides:
log 6 + 17 log x = log 5 (mod 13 - 1)
==> 5 + 17 log x = 9 (mod 12), since 2^5 = 6 (mod 13) and 2^9 = 5 (mod 13).
Solve for log x:
5 log x = 4 = -20 (mod 12)
==> log x = -4 (mod 12)
==> log x = 8 (mod 12)
==> x = 2^8 = 9 (mod 13).
I hope this helps!