[Edu-sig] Pythonic Math must include...

[kirby urner]

On Sat, Jan 17, 2009 at 11:59 PM, michel paul <mpaul213 at gmail.com> wrote:
> I definitely believe that a good way to improve our current math curriculum
> would be to weave in computational number theory.  This would be the 21st
> century answer to 'back to basics'.
>

Yes.  OSCON avatar R0ml has puts a strong liberal arts spin, says
these language games with computers are the new rhetoric, the basis
for responsible civic participation.

If they deny you access to these skills, that's a clear conspiracy to
disempower you, or feel free to treat it that way:  blend in, act like
nothing is wrong, then network with your friends like crazy after
school, do peer to peer teaching.  Bone up on what they're
withholding, your right as a citizen.

Fortunately, Portland makes that easy, what with OS Bridge, Saturday
Academy and so on.  Plus some of our public schools have already
turned the corner.  LEP High is all open source Ubuntu on wireless,
had me in peer teaching Python years ago by now (realized they could
do it).

> I think a huge problem in student math illiteracy has to do with not
> understanding division, remainders, and ratios.  When dealing with division,
> our curriculum tends to focus on quotients, but understanding the nature of
> the remainder has a lot to do with what math and technology are about these
> days.
>

Per our Shuttleworth meetup in London that time (some years ago), in
South Africa at least they're just bored out of their skulls if you
didn't share the cool toys with them (the students).  "When do we get
to learn about computers?  That's what we're here for.  We know this
knowledge is necessary to run companies, governments, any large scale
service.  If that's not what we're learning, why are we here?"
Tuxlabs, Freedom Toasters, OLPC... all pieces of the puzzle.

Many (not all) North Americans are more docile and controllable,
weren't oppressed by years of apartheid, and so take it sitting down
when you say you're "teaching math" but teach nothing about the
executable math notations except on a TI (very anemic and
underpowered, a joke if you're trying to run a railroad).

> Exploring how to find primes is definitely a 'must include' in a
> computational math curriculum.  I think students should explore this in a
> variety of ways, including both sieves and generators, discussing why one
> might choose one approach or another in various situations.  This would do a
> whole lot of good for both math and tech literacy simultaneously.

Yes, and the literature is already well developed.  The Fermat Test
works pretty well actually.  If 2**(p-1) % p is 1, you're likely
dealing with a prime.  Let's test it:

>>> sequence = fermat_test()
>>> next(sequence)
5
>>> next(sequence)
7
>>> next(sequence)
11
>>> next(sequence)
13
>>> next(sequence)
17
>>> next(sequence)
19
>>> next(sequence)
23
>>> next(sequence)
29
>>> next(sequence)
31

Pretty good huh.  If you hard code the exceptions (as a list) you can
get a long way with this.  It's also a good lesson in simple logic:
"IF you're a prime THEN you will pass the Fermat Test" is true, but
"IF you pass the Fermat Test THEN you are prime" is false.  Talk about
Carmichael Numbers.

The Fermat Test is based on Euler's Theorem that a base to a totient
power of N, mod N, nets you unity.

RSA encrypts your message m by raising it to a 3rd power (say) mod
public key i.e. c = pow(m, 3, N), but then we know the inverse of 3,
call it d, mod totient(N) such that pow(c, d, N) will be the base
itself, i.e. m (we've gone "around the clock" just the right
distance).

d is kept secret to the receiver, N is published and used to encrypt
by the sender (as is the source code, patent expired).  Unless you
know totient(N) you're unable to crack c, but that requires knowing
the two prime factors of N, which got thrown away.  totient(N) =
(p-1)*(q-1).

Example:
N = 17 * 23
totN = 16 * 22
m = 111
Go c = pow(111, 3, N)
get d such that 3*d % totN == 1

Brute force why not:

>>> for i in range(1, totN):
	if (3*i) % totN == 1:
		print(i)

		
235

get m back:

>>> c
304
>>> (3 * d) % totN
1
>>> pow(c, d, N)
111

Ta da!

In SSL, you don't need any published N, can establish that upon
handshaking.  If you want your email encrypted, then publish your N.

Thanks to our early group theory exercises (e.g. Vegetable Group
Soup), our South Africans, North Americans or whatever, know "inverse"
means something vis-a-vis a multiplicative identity, i.e. 1 or unity.
These "modulo numbers" (as we call them), may be defined as a simple
Python class and made to spit out their tables, including their power
tables.

We override __mul__ to get these, study group properties of Closure,
Associativity, Inverse and Neutral element (CAIN).

Even before this, we've used the concept of "relatively prime" to
define totatives and totient.  The whole discussion of primes versus
composites goes into this, which is where we get to these generators.

Miller-Rabin is a strong primality tester, stronger than Fermat's, and
might be used as a generator also (it's not a sieve).

We can use the extended version of Euclid's Algorithm for the gcd, to
compute the inverse of a modulo number, build it right into the class
definition.

>
> An interesting fact is that, except for 2 and 3, all primes are adjacent to
> a multiple of 6.  That is easy to prove:
>

That's true of every odd number not a multiple of 3 (it's next to an
even number that is a multiple of 3), some of which are also prime.

>     Let n be a multiple of 6.
>     n+1 might be prime.
>     n+2 is divisible by 2.
>     n+3 is divisible by 3.
>     n+4 is divisible by 2.
>     n+5 might be prime
>     n+6 is another multiple of 6.
>
> Here's a generator that uses this jumping by 6 approach:
>
> def primes():
>     p = [-1, 2, 3]
>     for x in p: yield x
>     def is_prime(n):
>         for factor in p[1:]:
>             if factor**2 > n: return True
>             if n%factor == 0: return False
>     multiple = 6
>     while True:
>         if is_prime(multiple-1): yield multiple-1; p.append(multiple-1)
>         if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1)
>         multiple += 6
>

Yes, another way of doing trial by division, checking all odd-number
candidates (automatically skipping those divisible by 3).

Kirby

> - Michel