Re: numerical methods (was: banning calculators)

["John S. Denker" <jsd@MONMOUTH.COM>]

Jack Uretsky wrote:
>         I started courses with 739 to the 597'th power just to show how
> useless calculators are.

1) Calculators are NOT useless.

2) We need to answer the pedagogical / motivational question:
Why would anybody CARE about the value of 739 to the 597th power?

Here's a story you can tell to motivate bignum arithmetic:  crypto.

Suppose you want to send me a private message.  I tell you to encrypt
it by multiplying by 500 modulo 667.  I can then decrypt it by
multiplying by the multiplicative inverse of 500 (modulo 667).
The question is, how can I find a number i (the inverse) such
that 500*i = 1 (mod 667)?

 -- I could try all possibilities and see what works.  There are
    only 666 choices.  Call this the brute-force search method.
 -- I could calculate 500^617 (mod 667) and notice that it gives
    me a big hint as to what i must be.  Call this the number-
    theory method.

Therefore:  Homework:
  Warmup:  What's 2^4 mod 5?  What's 3^4 mod 5?  What's 4^4 mod 5?
     What's 2^6 mod 7?
  a) Write a spreadsheet that will calculate take any 3-digit base
     and raise it to any 3-digit power modulo any 3-digit modulus.
     The spreadsheet must fit on one page;  600-line spreadsheets
     are not acceptable.  Hint:  Convert the power to binary
     representation.  (Note:  You could even carry out this
     algorithm on a hand calculator;  it's slightly laborious
     but not too bad.)
  b) Use it to calculate 500^617 (mod 667).
  c) Think about the result of step (b).  Find an expression for i,
     the multiplicative inverse of 500 (mod 667).  Compute i.
  d) Extra credit:  Where am I getting these numbers?  What's special
     about them?  Choose a number other than 500, and calculate its
     multiplicative inverse (mod 667).


===========

Remark:  In real-world applications, we would use thousand-digit
numbers, not 3-digit numbers.  The brute-force search method
becomes compleeeeeetely infeasible, but the number-theory method
remains reasonably efficient (although not quite so easy to implement
on a simple spreadsheet).

Also:  The objective of cryptology is that it should be easy
for me (the good guy) to decode the number, and disproportionately
hard for the bad guys to decode it.  I can find inverses modulo m
easily, because I constructed m.  I just have to remember how it
was constructed.  It is the product of two primes, and I remember
which ones.  The bad guys would need to factor m, which is not so
easy if m is a thousand-digit number.  This sort of crypto is based
on the idea that it is relatively easy to find big primes, and
easy to multiply them together, but not so easy to factor big
numbers.

=============

Pedagogical / philosophical remarks:

1) There is a cute number-theory lesson hiding in here.
Some guy named Euler had something to say on the topic.

2) This drives home the point that for many problems of
interest, you need a brain and a calculator.  You could
do this problem without a calculator, but it would be
rather laborious.  With a calculator or a spreadsheet,
it goes much quicker.  OTOH you can't do it without
using your brain.  You have to organize the calculation
just-so or the machine won't be able to handle it.

Brain + calculator = good combination.