The Chinese Remainder Theorem is often used as a way to speed up modular exponentiation. In this problem we go through the procedure of using CRT. Suppose we want to compute yd mod N, where y = 680, d 1325, and N 1739. = To use the CRT technique we must know the factorization of N. In the case of this problem, N where p = 37 and q = 47. Step 1) We first compute Up = y mod p and Yqy mod q. Ур Yq dp dq Step 2) - We compute the exponents dp = d mod p - 1 and dq= = d mod q - 1. Notice that this step uses Fermat's Little Theorem. - Xp xq = = Step 3) In this stage we do the exponentiation in the smaller groups. dp = yp = da Yq mod p = = pq mod q=
The Chinese Remainder Theorem is often used as a way to speed up modular exponentiation. In this problem we go through the procedure of using CRT. Suppose we want to compute yd mod N, where y = 680, d 1325, and N 1739. = To use the CRT technique we must know the factorization of N. In the case of this problem, N where p = 37 and q = 47. Step 1) We first compute Up = y mod p and Yqy mod q. Ур Yq dp dq Step 2) - We compute the exponents dp = d mod p - 1 and dq= = d mod q - 1. Notice that this step uses Fermat's Little Theorem. - Xp xq = = Step 3) In this stage we do the exponentiation in the smaller groups. dp = yp = da Yq mod p = = pq mod q=
Related questions
Question
100%
Transcribed Image Text:Step 3)
In this stage we do the exponentiation in the smaller
groups.
Xp Ур
x q
=
Cp
Cq
da
= Yq
dp
Step 4)
We now return to the big group using the formula
x = qcp xp + pcqq mod N.
qx
In this formula, Cp
Cq = p¯¹
=
=
mod p =
And finally,
X =
mod q =
=
mod q.
q-¹ mod p and
Transcribed Image Text:The Chinese Remainder Theorem is often used
as a way to speed up modular exponentiation. In this
problem we go through the procedure of using CRT.
Suppose we want to compute yd mod N, where
Y 680, d
1325, and N = 1739.
=
=
To use the CRT technique we must know the
factorization of N. In the case of this problem, N = = pq
where p = 37 and q = 47.
Step 1)
We first compute yp = y mod p and
= y mod q.
Yq
Ур
Yq
Step 2)
We compute the exponents dp
da = d mod q- 1. Notice that this step uses
Fermat's Little Theorem.
dp
da
||
Xp
xq
=
Step 3)
In this stage we do the exponentiation in the smaller
groups.
dp
=Yp
da
Yq
mod p =
=
mod q=
d mod p 1 and
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 6 steps with 5 images
