Building Blocks
|
In cryptographic applications, we often need to raise numbers to massively large powers, mod some base k. To do this, we need to be smart about keeping intermediate results small during the calculation, so we won't blow out the precision of our calculator/programming language. The big idea is to divide the calculation into small steps and remove copies of k at each intermediate step.
(a) In \(\mathbb{Z}_{y}\), find the value of compute the following values of $[5]^m$ where $m$ is a power of 2.
Compute each one of these values by squaring the previous value. Each time, normalize the result to use a small representative value. That is, write the value as [p] where p is in the range 0 through 6. This will give you a fairly small integer to square when computing the next value in the sequence.
(b) Write 55 as the sum of powers of two. Then use this decomposition of 55 to rewrite \([5]^{55}\) as the product of smaller powers of [5]. Each of these smaller powers should have an exponent that is a power of 2, e.g. like \([5]^16\.
Remember that addition in the exponent can be converted to multiplication at the base level like this:
\(a^{b+c} = a^b \times a^c\)
(c) Use your table to compute the value of \([5]^{55}\) in \(\mathbb{Z}_{y}\).
To do this, use your expression from part (b), look up the values for these smaller powers in the table from part (a), and then simplify the result.
In \(\mathbb{Z}_{11}\), find the value of \([8]^{21}\). You must show your work, keeping all numbers in your calculations small. You may not use a calculator. You must express your final answer as [n], where \(0 \le n \le 10\).