Due Monday, August 29th

For Monday:

  • A note about daily posts!  Sometimes the tasks may take more than an hour, or be frustrating.  Sometimes I give you tasks BEFORE I’ve taught you how to do them.  (My philosophy is that that’s part of the exploratory, messy nature of effective mathematics learning.)  In these circumstances, you should feel you have done your due diligence after one hour and hand in what you have (maybe skip over the frustrating task, at least at first).  Then you can come back to them later sometime, as needed.  For example, after Friday’s class, the Wednesday tasks should seem doable if they were not before, and you can go back to them to solidify understanding.
  • Quick review question:  What is the inverse of 7 mod 11?  What is the inverse of 7 mod 14?  (Watch for trick questions!)
  • I’m assuming you know about binary, and how to write things in binary.  If not, this PBS YouTube video gives a good review in the first four minutes.  (The rest of the video is also relevant and interesting (about ASCII and unicode etc.) if you are curious.)
  • I’ve warned you several times that you cannot reduce an exponent modulo $n$ even when you are working in $\mathbb{Z}/n\mathbb{Z}$.  So we might sometimes need to compute large exponents.  Let’s suppose we need to compute $2^5$.  We could start with $2$, and then:
      1. multiply by $2$ to get $2^2=2 \times 2 =4$
      2. multiply by $2$ to get $2^3=4 \times 2=8$
      3. multiply by $2$ to get $2^4=8 \times 2=16$
      4. multiply by $2$ to get $2^5=16 \times 2=32$
  • That’s four multiplications.  Instead, we could do this:
      1. multiply by $2$ to get $2^2=4$
      2. now that we have $2^2=4$, we could multiply it by itself to get $2^4 = 4 \times 4 = 16$
      3. multiply by $2$ to get $2^5 = 32$
  • That was only three multiplications!  That’s more efficient.  So, the challenge is to compute a high power by doing as few multiplications as possible.
  • Your challenge is to compute $2^{148}$ modulo $1000$.  Imagine you have a calculator that will multiply two numbers modulo $1000$ for you (for example, you can use google, wolfram alpha or Sage on the course website), but WON’T just do big exponents.  (Remember, it’s always efficient to reduce mod n between each multiplication, so you never get more than 3 digit numbers to work with.)  How can you do this with the fewest multiplications possible?  Try to do the best you can, and count the multiplications you use.
  • Then, watch this video (6:09) which gives a general algorithm.
  • Use the double-and-add algorithm of the video (by writing 148 in binary) to demonstrate an efficient way to compute $2^{148}$.
  • What you just learned is what computers do, when implementing cryptosystems in modular arithmetic.
  • Now read Section 3.5 “Modular Exponentiation” of your textbook for another, different approach.  Now work out this method for $2^{148}$?  Better or worse?  This is an easier algorithm to internalize and remember for use on a test.
  • Time left?  I wouldn’t want you to get bored.  If you still have some time left, you can optionally try to create a nice implementation of the double-and-add algorithm in your favourite language.  I’d be happy to see that in the canvas inbox if you do.  If you are new to programming, implementing the simpler algorithm of just multiplying by 2 repeatedly using a for-loop is a good first challenge.  There are tons of “learn python” resources online; here’s a YouTube playlist that seems popular.  Reach out to me!