Chapter 7 Exercises
Exercises Set 1
1.
Write a python function that computes \(\gcd(a,b)\) for \(a, b \in \Z\text{.}\)
2.
An efficient algorithm for computing a solution to \(au + bv = \gcd(a,b)\) is given below:
- Set \(u = 1, g = a, x = 0\) and \(y = b\text{.}\)
- If \(y = 0\text{,}\) set \(v = (g - au)/b\) and return values \((g, u, v)\text{.}\)
- Divide \(g\) by \(y\) to get \(g = qy + t\) with \(0 \leq t \lt y\text{,}\) store \(q\) and \(t\text{.}\)
- Set \(s = u - qx\text{.}\)
- Set \(u = x\) and \(g = y\text{.}\)
- Set \(x = s\) and \(y = t\text{.}\)
- Go to Step (b).
Implement this algorithm in a python function.
3.
Implement the fast powering algorithm in python as a function that takes as input a base \(g\text{,}\) a power \(x\text{,}\) and a mod \(n\) and produces as output \(g^x \bmod n\text{.}\) You may wish to use the python function bin(n) which returns the binary representation as a string of 1s and 0s. (You can view this string as the values of the coefficients \(k_i\) in the description of the algorithm above. )