[Edu-sig] creating an interface vs. using one

[kirby urner]

>  I think there should be more number theory in the math curriculum, and we could
> provide that beautifully with something like Python.
>
> But I will remain alert to site-specific issues that the use of Python could address.
>
> - Michel

On the number theoretic front, once kids get it about __ribs__ and
know they're able to overload __add__ and __mul__, we're ready for an
abstract algebra unit.

Define a Class of integer that adds and multiplies modulo some modulus
N, which may be set as a class-level variable (inherited by all
instances).

Then use Guido's ultra-simple GCD function to generate the totatives
of the same N, i.e. those positives < N with no factors in common.

Here's the code:

IDLE 1.2b2
>>> def gcd(a,b):
	while b:
		a, b = b, a%b
	return a

>>> def totatives(n):
	return [k for k in range(1,n) if gcd(k,n)==1]

>>> totatives(20)
[1, 3, 7, 9, 11, 13, 17, 19]
>>> totatives(12)
[1, 5, 7, 11]

You'll find that the totatives of 20, multiplied modulo 20, form an
Abelian Group.  This isn't too hard to model in Python.  Just come up
with a row-column multiplication table, maybe a literal XHTML table
computed server side (that'd be one option).

If N happens to be prime, then you get a Galois Field, i.e. you can
bring __add__ into it, provided you now also have 0 (still excluded as
a divisor).

>>> class Modint(object):
	modulus = 20
	def __init__(self, v):
		self.v = v % Modint.modulus
	def __mul__(self, other):
		return Modint(self.v * other.v)
	def __add__(self, other):
		return Modint(self.v + other.v)
	__rmul__ = __mul__
	__radd__ = __add__
	def __repr__(self):
		return "%s modulo %s" % (self.v, Modint.modulus)


>>> numset = totatives(20)	
>>> group = [Modint(j) for j in numset]
>>> table = [i*j for i in group for j in group]
>>> table
[1 modulo 20, 3 modulo 20, 7 modulo 20, 9 modulo 20, 11 modulo 20, 13
modulo 20, 17 modulo 20, 19 modulo 20, 3 modulo 20, 9 modulo 20, 1
modulo 20, 7 modulo 20, 13 modulo 20, 19 modulo 20, 11 modulo 20, 17
modulo 20, 7 modulo 20, 1 modulo 20, 9 modulo 20, 3 modulo 20, 17
modulo 20, 11 modulo 20, 19 modulo 20, 13 modulo 20, 9 modulo 20, 7
modulo 20, 3 modulo 20, 1 modulo 20, 19 modulo 20, 17 modulo 20, 13
modulo 20, 11 modulo 20, 11 modulo 20, 13 modulo 20, 17 modulo 20, 19
modulo 20, 1 modulo 20, 3 modulo 20, 7 modulo 20, 9 modulo 20, 13
modulo 20, 19 modulo 20, 11 modulo 20, 17 modulo 20, 3 modulo 20, 9
modulo 20, 1 modulo 20, 7 modulo 20, 17 modulo 20, 11 modulo 20, 19
modulo 20, 13 modulo 20, 7 modulo 20, 1 modulo 20, 9 modulo 20, 3
modulo 20, 19 modulo 20, 17 modulo 20, 13 modulo 20, 11 modulo 20, 9
modulo 20, 7 modulo 20, 3 modulo 20, 1 modulo 20]

Thanks to Euler's Theorem, we know that a message sent into orbit part
way (e), will decrypt once we come back around (e*d), modulo N.
That's RSA in a nutshell:  N is the public key modulus while e*d is
one power beyond a phi power (name collision with golden mean) -- here
phi means "number of totatives of N".

d is of course the big secret, and only needs to be stored on the
local machine i.e. you don't need to export it to a receiver (hence
the term "public key" (everything you need is in the open, even the
algorithm itself (patent expired))).

Kirby