Compute the following greatest common divisors by factoring the integers as products of primes.
Both
We try to factor both of
Again, we aim to factor both
Use the Euclidean algorithm to calculate the following gcds:
We start by dividing
As above, we repeatedly perform divisions with remainder,
starting with
Using the Extended Euclidean algorithm, find integers
Earlier in the lesson, we checked that
Here, we must first calculate
Try this for yourself! Choose primes
Answers will vary.
Which of the following numbers are prime? For the ones that aren’t prime, factor them as a product of primes.
101
119
127
Solution:
The number
The number
The number
For any positive integer
Calculate
Calculate
Solution:
For any positive integer
We perform divisions with remainder, starting with dividing
Again, we perform divisions with remainder, starting with
dividing
Find integers
Solution:
Starting from the Euclidean algorithm work from question 2(b), we
have
Here, we first have to run the Euclidean algorithm on
Given our work in part (b), there is just one more thing to do.
We already know that
Compute the following values of the Euler phi function.
Solution:
Since
Since
Since
Since
Notice that
Here, we can use the same approach that worked for calculating
There are
Modular arithmetic is good for much more than RSA. If an equation
is true in the integers, we can “reduce it mod
Prove that each of the following equations has no integer solution by
showing each one has no solutions mod
Solution:
Here, we take the equation and reduce it modulo
For this one, we take the equation and reduce it modulo
For this equation, reducing modulo
Since
In RSA, Nick is not supposed to reveal
Suppose you have a magic machine that takes
Once you know both
What this means is that an efficient way for calculating
Solution:
If we have the values of
So, if we know
As suggested in the hint, let’s see what the quadratic formula
says about the roots of the polynomial
Like any cryptosystem, the security of RSA can be compromised if
used incorrectly. Suppose Nick and Bahaa have the same value of
Explain how Nick and Bahaa can work out each other’s private keys, and therefore read each other’s encrypted messages.
Suppose Shefaza comes along and sends the same message
Explain how Diana can use this information to recover Shefaza’s
plaintext
Hint: Running the Extended Euclidean algorithm on
Solution:
Because Nick and Bahaa have both chosen the same value of
As mentioned in the hint for the question, since
At this point, Diana should take the ciphertexts
So, if Diana calculates the unique integer
Remark: There’s a minor point to mention here: we
only talked about what it means to raise numbers to positive exponents
mod