In: Computer Science
In this question we show that we can use φ(n)/2. Let n = pq. Let x be a number so that gcd(x, n) = 1.
1. show that xφ(n)/2 = 1 mod p and xφ(n)/2 = 1 mod q
2. Show that this implies that and xφ(n)/2 = 1 mod n
3. Show that if e · d = 1 mod φ(n)/2 then xe·d = 1 mod n.
4. How can we use φ(n)/2 in the RSA?
Please explain answers if you can! Thanks!!
Q:-
In this question we show that we can use φ(n)/2. Let n = pq. Let x
be a number so that gcd(x, n) = 1.
1. show that xφ(n)/2 = 1 mod p and
xφ(n)/2 = 1 mod q.
Answer:--------
φ(n) = (p-1)(q-1). As p and q are primes , both p-1 and q-1 will be
even.
By Fermat's little theorem, xp−1 ≅ 1 (mod
p).
Hence, x φ(n)/2 = (xp−1)(q−1)/2 ≅
(1)(q−1)/2 ≅ 1 (mod p ).
Similarly, xφ(n)/2 ≅ 1 (mod q).
2. Show that this implies that and xφ(n)/2 =
1 mod n.
Answer:--------
Given equations: y ≅ 1 (mod p) and y
≅ 1 (mod q), the Chinese Remainder Theorem says
there is a unique in y ∈ Zpq that satisfies these two
equations, and in this particular case y = 1 is the obvious unique
solution. Hence, (b) follows.
3. Show that if e·d = 1 mod φ(n)/2 then xe·d
= 1 mod n.
Answer:--------
Since e·d ≅ 1 (mod
ϕ(n)/2), ed = k·(ϕ(n)/2) + 1, for some integer
k.
So,
xe·d ≅ x
k·(ϕ(n)/2) + 1 ≅
(xϕ(n)/2)k · x
≅ (1)k·x
≅ x (mod pq).