The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » Education » math-teach

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Signuture Lesson Plans (intro)
Replies: 7   Last Post: Apr 13, 2009 11:12 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Kirby Urner

Posts: 4,713
Registered: 12/6/04
Re: Signuture Lesson Plans (intro)
Posted: Apr 7, 2009 6:24 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Apropos of Dr. Renfro's recent remarks [0], there's a
segregation of topics in 9-12 called "fish ladder math"
that goes Alg1, Geom, Alg2, Calc, with Trig/Stats on the
side, maybe some computer science (CS) as another
elective, though that usually just means "Excel", other
bizapps, little programming per se (all the programmers
are off making money I think is the problem there --
can't retain 'em).

Some constructivist curricula have offered more of a mix,
to the dismay of objectivists, who dislike the "watering
down" and far be it from me to champion competing brands
that use the constructivist label (I come by it through
Caleb Gattegno and the ATM, Britain's equivalent to the
NCTM but far less obstructive). "More of a mix" just
means keeping the dots connecting, showing the segues.
It's more a disc jockey approach in that we show what
easily blends into what ("seamless math" is another word
for it, although topologically I think a graph of
connected trails -- Dr. Talman's image -- is a better
way to go (implies big holes, which we want to admit to,
not cover up)).

The signature algorithm of the ages, named for Euclid is
(drum roll) Euclid's Algorithm. You'd be surprise how
many 9-12 state standards don't include it, even though
it's an Alg1 topic, involves relative primality, reducing
fractions (lowest terms) plus anchors the whole idea of
what an "algorithm" is (just talking about "the four
operations" as all we mean by "algorithms" is mind-
numbing and not to be encouraged).

In Python:

def gcd(a, b):
while b:
a , b = b, a % b
return a

There's that % operator again, from "clock arithmetic",
also not given much focus in Alg1, objectively speaking
(just do a survey, get back to me with evidence?). The
way this works is you try to divide one into the other
and if there's no remainder (b is 0) you're done.
Otherwise, take the remainder you *do* get and try it
against the next larger leftover and so on, until you
get down to 1 (unity), in which case a, b are relatively
prime. Since 1 always divides evenly, b becomes zero at
that point and you get 1 as your answer (a = 1). So
maybe that wasn't so clear? You get more chances to get
it, including with animations. We're into repetition,
which objectivists like, but with the student, the
learner, having a lot of control over where (and how)
to deliver the reinforcement.
(Lower 48 kids, struggling to remain on task)
(primitive camera, clear example)

Note that in Guido's version, we don't care if a > b or
b < a to start because a % b, a < b, just returns a,
which becomes the the next b, so the division attempt
automatically reverses, no need for that extra logic.

Why do we care about the GCD? Not just because of our
need to reduce Fractions (rational numbers Q, which we
implement as math objects in Python). We also want to
understand what's meant by "the totatives of a number".

At this point, 9-12 teachers are shaking their heads,
because they know full well that upline academics have
completely failed in their mission to keep the lower
grades current or, to put it another way, the backlash
in the wake of New Math decimated the ranks of reformer,
pushing a lot of the best ones to the sidelines. The
Gnu Math subculture, in picking up that mantle to some
degree, at least has the Internet to work with, which
SMSG did not. YouTube (written in Python) is one of our
best selling points. But then many schools block it,
won't assign YouTubes for homework, so back to square one
(in those schools).

What happened in the 20th century is difficult to
summarize in one short post, but basically it went
"hyperdimensional" in various ways (I can think of three
ways), while algebra took off along lines pioneered by
Grassmann and Clifford. Topology grew up, giving us a
more flexible and coordinate-free way of thinking. But
hey, that's just a snapshot (Thurston was one of my math
teachers by the way -- a good thing about Princeton is
you're really there to teach undergrads, all your other
skills as a researcher are consider secondary to your
teaching abilities, why undergrad rating systems are
encouraged, officially, not just through the informal
social networking systems -- how about in your school?
(remember, Bologna was so successful because the students
had hire and fire powers, screened their own teachers!)).

In the topological realm, we got Euler's V + F = E + 2
(with variants, depending on "Euler characteristic") and
this is so simple as to be teachable in 2nd or 3rd grade,
in conjunction with building some of that geometric
vocabulary that'll come in handy later, through all of
life in fact. Remember: the virus tends to be "icosa-
hedral" and icosa means 20, where hedron means "face".
A 20-faced wireframe is one of the Platonics, its dual
being the pentagonal dodecahedron (although "dual" is
not strictly the same as "inverse", the five Platonics
give a good mental picture of "group" in the sense of
closure under the dual operation, with the central
and simplest poly dual to itself, then maybe put as pairs
on either side: (cube, octahedron), (pentagonal dodeca-
hedron, icosahedron)).

I mention Euler because we're using his theorem in public
key cryptography as well, which is where the GCD comes in.
The totatives of a number all all numbers relatively
prime thereto and less than, down to 1 inclusive. So like
for 12: 11, 7, 5 and 1 have no factors in common (other
that 1 itself). In Python then:

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

>>> totatives(100)
[1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37,
39, 41, 43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 69, 71,
73, 77, 79, 81, 83, 87, 89, 91, 93, 97, 99]

Note that we got away with *one line* of Python, once
gcd had been defined (also very simply). We now have a
constructivist environment. Students will try very large
numbers and find this doesn't work, as there's an upper
limit to what this somewhat inefficient algorithm might
handle. Lots of calories, lots of memory... but it does
the job we need it to do, for the small numbers we wish
to sample.

What Euler's Theorem says is if you call "the number of
totatives of N" the "totient of N", then if you raise
some base to the totient of N power, modulo N, you always
get 1 as a remainder. Stipulation: your base and
N need to have no factors in common.[1]

Writing a totient function is easy, just count the number
of totatives:

>>> def totient( n):
return len(totatives(n))

>>> totient(100)

So now we might simply test Euler's Theorem, to see
*what it means*. All too often, a proof is introduced
before there's any understanding of the meaning or
applications of a theorem. Here, we go for the meat,
want to establish relevance first. Proofs will come
later (maybe not until college in some cases).

>>> N = 100
>>> assert pow(3, totient(N), N) == 1
>>> pow(3, totient(N), N) == 1

>>> N = 12
>>> assert pow(3, totient(N), N) == 1

Traceback (most recent call last):
File "<pyshell#26>", line 1, in <module>
assert pow(3, totient(N), N) == 1
>>> assert pow(5, totient(N), N) == 1

Notice we broke our rule of no factors in common for a
sec, had to change the base.

I don't find any YouTubes explaining this yet. My
ShowMeDo clip on RSA doesn't count I don't think.

Why is any of this relevant. Because the next power
higher than the totient power, or multiple thereof,
will be b itself (the base). In public key cryptography,
that base is our encrypted ciphertext, already to a power
mod N, say the 7th power. In finding some d such that 7
* d == 1 mod totient(N), we're causing the ciphertext to
divulge its pre-power value. The only way to get d is to
know N's two prime factors to begin with, and those we
throw away. Finding them again is really computationally
expensive (there're those calories again!). That's RSA in
a nutshell, but in the actual curriculum, we have like
four years to build out to it. We also study Diffie-
Helman-Merkle perhaps.[2]

We like to assign *trade book* readings more than
physical textbook readings, e.g. 'In Code' and
'Cryptonomicon'. We handle exercises in class, over the
Internet, or by scavenging from existing texts. FOSS
gets us off that hugely expensive textbook treadmill,
empowers teachers to swap lesson plans, use collaborative
tools (like Anna knows about). This cost savings alone
more than pays for the hardware, which is also

Again, we're talking industry standards here. At the
Hyatt near O'Hare recently, I led a 3 hour workshop called
Python for Teachers wherein I went through the RSA
algorithm in some detail. Dr. Ian Benson (Tizard,
Stanford) showed a video clip about HDM, which is used by apparently, to exchange confidential credit
card information. We're talking real world relevant
algorithms and a way to motivate what I think Dr. Renfro
would consider "beyond Alg2" in some ways. However,
thanks to our concrete, hands-on, constructivist approach,
we're able to get there, at least in the pilots.[3]

Many complain that we "guinea pig" but cultures that
don't experiment, try new things, simply wither on the
vine. So I'm not about to apologize for being an
experimentalist and encouraging others to be such as well.
We explain everything to the parents, and mostly they
approve of the results. Saturday Academy keeps asking
me back. I have my eye on Alaska. I'd like to train
more "clones of Kirby" although that's just an in-house
joke (we know we're not carbon copies of one another,
each has a different angle and spin, even if we share a
lot of the same materials).




Diffie-Hellman key agreement was invented in 1976 during
a collaboration between Whitfield Diffie and Martin
Hellman and was the first practical method for
establishing a shared secret over an unprotected
communications channel. Ralph Merkle's work on public key
distribution was an influence. John Gill suggested
application of the discrete logarithm problem. It had
been discovered by Malcolm Williamson of GCHQ in the UK
some years previously, but GCHQ chose not to make it
public until 1997, by which time it had no influence on
research in academia.

The method was followed shortly afterwards by RSA,
another implementation of public key cryptography using
asymmetric algorithms.

In 2002, Martin Hellman wrote:

The system...has since become known as Diffie-Hellman
key exchange. While that system was first described in a
paper by Diffie and me, it is a public key distribution
system, a concept developed by Merkle, and hence should
be called 'Diffie-Hellman-Merkle key exchange' if names
are to be associated with it. I hope this small pulpit
might help in that endeavor to recognize Merkle's equal
contribution to the invention of public key cryptography.

U.S. Patent 4,200,770 , now expired, describes the
algorithm and credits Hellman, Diffie, and Merkle as


We like the Escalante model, but why make him so dependent
on LAUSD? Either let him teach teachers, or syndicate
him through the Internet? Of course guys like that enjoy
working directly with the kids, won't settle for some
studio. On the other hand, you can have kids in the
studio (Disney model, most kid programming -- produce it
as reality TV then?).

Do cutaways, don't just have talking heads. Saturday
Morning is a wasteland these days, lots of money-grubbing
sugar pushers trying to supersize the kids, but without
the common decency to put anything positively futuristic
on the cereal boxes, not even the XO. The Lower 48 ag-
industrialists don't like children apparently. Why let
misanthropes corner a strategic market? Homeland Security
where are you?

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.