> 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
_______________________________________________
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig
