## Numbers and imagination: notation and literature

I had the good pleasure to watch Batman vs. Superman this past weekend (I loved it)
with my niece and her father.  In the conversation preceding it she asked about Knuth arrows. I had shown them to her previously and she was trying to remember the details to show her boyfriend something cool in math. As a disclaimer: I’m not informed enough to comment on where these are actually used in mathematics. I can say things like
“Ramsey Theory” and what not but I would just be pretending to understand any of the
research that goes on such areas. Regardless, Knuth arrows are a neat notation that
allows us to write down numbers of unimaginable magnitude. This is a neat feature of
mathematics, maybe particular to western mathematics, to exceed our own imaginations.
We stretch them constantly with new questions and then seek to create a road from here
to … where ever those questions take us. Notation is a powerful tool for exploring
new lands. Let’s get into it.

Multiplication is a shorthand for repeated addition. So when we see 3×4 we know it
means we should add the first number,3, to itself 4 times:

$3\times 4 = 3+3+3+3$

Exponentiation is just repeated multiplication so we know that 34 indicates that we
should multiply the first number, 3, by itself 4 times:

$3^4 = 3\times(3\times(3\times 3))$

While multiplication is commutative, 3×4=4×3, exponentiation is not, 34≠ 43. What if
we want to repeat exponentiation? We could write something like:

$3^{3^{3^3}}$

Where we start by evaluating it at the top, so:

$3^{3^{3^3}} = 3^{3^{27}} = 3^{7 625 597 484 987}$

Yeah that’s big. In fact if you’re familiar with logarithms you can change the
expression to a power of ten and you’ll find out that the number above has over three
trillion digits in it (this is already difficult to comprehend.  For example, using typical margins, Arial font, 11pt, how many 8.5″x11″ pages would be required to type this number out?). The above notation isn’t that bad for repeating exponentiation
addition and multiplication a silly number of times, consider the meaning of something
like 3×100 or $3^{100}$ How do we repeat exponentiation a hundred times without
taking up the hold page with a stack of 100 threes (often called a power tower ).

Knuth arrow notation allows us to repeat exponentiation more than almost anyone could
want. It starts with repeated multiplication. So instead of writing $3^4$ for
$3\times 3\times 3\times 3$ we write

$3\uparrow 4 = 3\times 3\times 3\times 3$

The 4 tells us how many threes we’re going to use and the single arrow tells us we’re going to multiply. Nothing special yet. The point of the arrows is that they are recursively defined. That means that the double arrow operation is defined using the single arrow
operation. So an expression like $3\uparrow\uparrow 4$ is understood as
repeated single arrow.

$3\uparrow\uparrow 4 = 3\uparrow (3\uparrow (3\uparrow3))$

The parantheses are necessary because exponentiation (single arrow) isn’t commutative.
We’ve already worked this one out but let’s do it again:

$3\uparrow\uparrow 4 = 3\uparrow (3\uparrow 27) = 3\uparrow 7,625,597,484,987$

So what should we do first? Make the 4 bigger (i.e. try something like $3\uparrow\uparrow 5$) or add any extra arrow (i.e. try something like $3\uparrow\uparrow\uparrow 4$)? Let’s try both and compare, you may want to try this on your own first.

$3\uparrow\uparrow 5 = 3\uparrow (3\uparrow (3\uparrow (3\uparrow 3))) = 3\uparrow (3\uparrow 7,625,597,484,987)$
A bit hard to grasp eh? $3\uparrow 7,625,597,484,987\approx 10^ {3,638,334,600,000}$. So this boils down to multiplying  a lot of threes (many many more
than a googol, what do you call a number with over three trillion digits?).

vs

$3\uparrow\uparrow\uparrow 4 = 3\uparrow\uparrow (3\uparrow\uparrow (3\uparrow \uparrow 3)) = 3\uparrow\uparrow (3\uparrow\uparrow 7,625,597,484,987)$
Whoa. $3\uparrow\uparrow 7,625,597,484,987$ alone represents a power tower
with 7,625,597,484,987 threes in it!!  But that’s just the number of the number of
threes in the power tower that represents $3\uparrow\uparrow\uparrow 4$!!

If that’s not enough for you you can use exponents in arrow notation, for example:
$3\uparrow^{8} 4 = 3\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow \uparrow 4$.  If you’d like to learn more listen to an actual mathematician (of well earned fame) talk about how he’s used Knuth arrows.

I could end here after introducing a curious bit of mathematical notation but I feel
there’s more to say. This notation allows us to capture numbers that are beyond
imagining. Numbers that would be too large for the universe to hold them (quite possibly literally in the sense that the universe, at least the observable universe, is finite) and yet we can represent them with some marks on a piece of paper. We can prove things about
them, manipulate them even though we can never see them in their entirety, that’s
incredible but it doesn’t just happen in math.

“The Library of Babel” by Jorge Borges is a fantastic story concerning a very special library.
This library contains every possible 410 page book that could be created using 25 symbols. That description is mundane but the consequences are anything but. I won’t spoil the fun of figuring things out for you, but there are more books in such a library than there are atoms in this universe. What if we conceive of the universe as a sphere with radius 14 billion light years (or approx $10^{26}$ meters) which gives a volume of around $10^{79}$ cubic meters. What if we consider the number of Planck volumes (cubes $10^{-35}$ meter on a side so $10^{-105}$ cubic meters. Then there are around $10^{184}$ plank volumes in the universe. If we put a book in each one, would we have enough space? Laughable. You’ve not even dented the library, it’s a laughable attempt! What percentage? There aren’t words to describe what a miniscule portion of the library
$10^{184}$ represents.

I include this brief description because this is another way of capturing something
unimaginably large. At five pages of text it’s not the most efficient way to denote
the number which represents the amount of books in the library. Certainly five pages
of arrows would create some more fantastical monster of unimaginable magnitude. I
like the story for many reasons but one is certainly how the magnitude of the library
takes some work to appreciate. It begins as large and as the story progresses becomes
hauntingly vast and perilous in its unfathomability. The more you try to crunch the
numbers the more the implications unfold. There are many other questions you can ask
mathematical consequences by William Bloch called the Unimaginable Mathematics of Borges’ Library of Babel.

It’s almost paradoxical.  We can imagine that which is unimaginable.  Keep in mind I have written nothing here about the many levels of infinity that mathematics has studied.  These unimaginable quantities I’ve written about today are merely finite.

## The meaning of numbers

A brief post of a few thoughts and a link my friend Tom sent me to an interview with Randall Monroe, the author of XKCD.  The interview was a timely read so I’ll start with a great quote:

A good rule of thumb might be, “If I added a zero to this number, would the sentence containing it mean something different to me?” If the answer is “no,” maybe the number has no business being in the sentence in the first place. – Randall Monroe

When we’re teaching mathematics, especially if we’re trying to teach with applications or plausible scenarios we are confronted by all sorts of non-integer craziness.  How do we help ourselves and our students put these numbers into context.  Is a million a big number?  Depends.  Depends on what?   Teaching moments abound from there.  In a similar sense when you have students work on realistic models that require technology the discussion of accuracy and round off errors inevitably comes up.  Recently during an session of group work students used software to find the eigenvalues of a 3×3 matrix (of decimals). One of them was something like 7.891393×10-17. Is this an actual eigenvalue? Is something growing extremely slowly? These are good questions that come up when using realistic numbers. Another day recently we looked at the classic predator-prey equations which are nonlinear. They found the two equilibria and, using the jacobian, linearized the system at each point. At the non trivial equilibrium you should end up with two pure imaginary eigenvalues indicating closed cycles orbiting the equilibrium. Many of them approximated the fractions in the coordinates for the equilibrium and because of that ended up with complex eigenvalues that suggested a decaying spiral. It was a matter of 1/30 vs. 0.033. Not a lot but a great conversation starter.

The other quote that stands out to me, from the interview, is

But I’m also wary of people saying “everyone should know” some skill from their area of expertise, because people have their own stuff to deal with. It’s easy for me to imagine an abstract person and then say, “Wouldn’t it be better if that person knew how to program?” And maybe it would. But real people are complicated and busy, and don’t need me thinking of them as featureless objects and assigning them homework. Not everyone needs to know calculus, Python or how opinion polling works. Maybe more of them should, but it feels a little condescending to assume I know who those people are. I just do my best to make the stuff I’m talking about interesting; the rest is up to them. – Randall Monroe

You hear a lot of wishful thinking amount some educators.  It’s understandable but on the other hand, what is the point of complaining what they don’t know instead of figuring out what you could show them.  I think sometimes it boils down to a complaint “why aren’t they just like me” which is unfortunate because if you take the time to talk to your students, let them  write about their beliefs or ideas, even if you don’t agree with them, I think you’ll find they’re a clever bunch of folks interested in different things with different beliefs.  In trying to understand those differences there are tremendous opportunities for your teaching, to teach to those who are trying to learn from  you as opposed to teaching the way you like to teach.

One last comment on numbers and students.  If you use blackjack as an example in a math class (and there is a lot you can do with blackjack) and if you teach them what basic strategy is you might notice some resistance.  For example: hit 16 if the dealer has a 10.  Not everyone will want to do this.  You can try all you want to convince them with arcane symbols but it’s their gut, not their brain, doing the resisting.  I have found some anecdotal success with the classes carrying out trials (always hit or always stand) and tallying up the results. Even still, the odds of winning (which are poor) on such a hand are fairly close and you have to wonder if their decision to buck statistics isn’t a good one possibly.  Statistically you’ll always hit because you’ll win a couple more 16 vs 10 hands for every hundred such hands you come across.  To optimize your long term bankroll the solution is clear, but what if you’re trying to optimize something else?  What if you like the risk, the unknown, the fear of losing and the thrill of winning for no good reason.  It’s not unreasonable.  Even the most calculating among us act irrationally towards our love interest (did you check her investment portfolio and genetic history before marrying and reproducing?).  The many conversations I’ve had with students about these topics leave me a bit perplexed but with a feeling that I’m not seeing the whole person because of my own perspective (I’ve happily memorized the relevant strategy chart and deviations, woohoo!)

## Context in mathematics

Ever since reading about ethnomathematics I’ve been wondering how to identify what is western about western mathematics.  Moreover, if we view culture more abstractly as groups of individuals connected by traditions, beliefs, practices etc then 19th century woodworkers could have a ‘mathematics’ just as well as the Polynesian tribe of the Malekula.  This idea of each culture (or community of practice, to use another common term) having it’s own mathematics is a fairly powerful one.  Do physicists use math sloppily or do mathematicians use math too carefully?  Viewing mathematics as a cultural practice, they each have their own mathematical practice.  It’s not that one is better than the other, they’re different.

Isn’t there a right way and a wrong way?  Are facts facts and that’s that?  I admit to being in a crisis of sorts over such questions.  Even within the culture of western mathematical practice there are many different logical foundations. Which should you use?  The consequences of your choice are severe in terms of what you can prove.  Why do we make the choices that we do (in western foundations)?

Viewing mathematics as an inherently human activity but also a cultural practice can be an asset for a teacher like myself trying to understand my audience.  They are not in my culture, by that I mean the culture of a western mathematician.  In fact, I’m only peripheral to that culture as I don’t (and haven’t) conducted an original research (though I have engaged in a caricature of it when playing with mathematical ideas).  The way in which I think about mathematical ideas, mathematical truth, context, explanation and evidence are all tied to my cultural practice of mathematics.

What are these cultural practices?  There’s so much to write about (and many have written far better about it and I’ll discuss their contributions eventually).  For this post, just to get it off my chest, I want to address context.  Western math tends to strip context from the mathematics.  This can be strength certainly.  We can weave disparate ideas together in a uniform tapestry of knowledge that can be applied to seemingly anything.  This is done despite the varied origins of those ideas.

While powerful as a tool for abstraction I think we forget how important context is in our everyday lives and how important it might be to the mathematical practice of our students.  For example, I could show my students a system of three linear differential equations.  We could analyze the coefficient matrix and find that there are two complex eigenvalues and a real eigenvalue of zero.  I could talk about what those mean (spirals etc) and write down the general solution and then, given an initial condition, a particular solution.  Or I could say, suppose there has been a wildfire and there are now ten acres of bare ground.  In this region, the first plant to grow in such conditions is a certain grass.  The rate of reclamation is 30% per year.  The grass dies off at 5% per year and yields to a second species, shrubs, at 20% per year.  The shrubs then die off at 15% per year.  What happens?  What’s the region look like in 10 years.

As far as the math content goes there’s nothing new here.  But we know some people will be more interested in this problem now because it relates to something they care about.  We could restate this problem in several other ways as well.  Each context would not change any of the essential mathematical content but it would change the mathematical context.  I think our students need and want that context.  As an anecdote last semester while covering logarithms I became frustrated by the usual precalculus content.  Logarithms are presented as a weird afterthought, a consequence of the exponential function passing the vertical line test or as some need to solve seemingly arbitrary exponential equations.  I took a small detour and talked about log tables and how those worked.  I showed my students a picture of a room full of computers pre WW2.  That was a room full of people of course.  I could hear the surprise.  I mentioned that such engineering marvels as the Hoover Dam were built with those types of  computers, people, using mechanical adding machines and tables of logarithms.  You could hear the difference in the room.  A small number of people came down afterwards and we talked about the pre-analog/digital computer age.  It was only a few, but the context woke them up.  They were interested in the fact that logs, log tables and incredible structures had been built with them. Of course that’s just the tip of the iceberg, historically, with regards to logarithms.

Context is important.  This morning as I came into school it occurred to me that this might be like the analysis of a joke.  I’m sure someone has categorized joke structures and form.  I imagine there’s a rich theory of humor which describes why certain ideas work and others don’t.  As powerful as that method might be, you would still need to add context to that joke form or joke structure to make it funny.  Western mathematics removes context and places value on abstraction.  With that value it has made important discoveries and contributions.  However, when we share that math back to our students, just like when we tell a joke, we need add that context back in for it to make sense, for it to mean something.

Posted in Uncategorized | 1 Comment

## Animated Engines and Mechanical Movements

I endeavour to keep this dying blog aloft.  It’s not actually dying so much as it’s in a medically induced coma while I recover from the consequences of reproduction.  I have been motivated recently by learning that someone has been enjoying reading some of the posts.  A professor here where I work, we’ll call him Ben because that’s his name, popped his head into my office to let me know that a friend/associate of his had stumbled across this humble attempt and wondered who I was.  In this world made small by the internet it turned out that Ben did indeed know  who I was and told me so.  It was great to know that something here has been of value.  I’ve been putting some time into some more substantial posts on my teaching, philosophy of mathematics and some other errata that hopefully will become posts in the near future.  For now, I can’t resist sharing a couple of neat websites I found yesterday.

In calculus 2 when I discuss related rates I like to model the motion of a piston in a 2-stroke engine as example.  The up and down motion of the piston is related to the rotation of the crank shaft and deriving the equation for that relationship is a good review of the law of cosines, quadratic formula etc.  The resulting equation is not too bad and it’s good for the students to see ‘messy’ functions that require the chain rule that are not simply dreamed up by their instructor.  Animated Engines is a website which does what you’d expect.  I used their animated 2-stroke engine to prime the students for the drawings and derivations I did thereafter (these engines, if you don’t know, are common in things like chain saws, weed trimmers, lawn mowers, etc)

When you visit Animated Engines they advertise a related site called 507 Mechanical Movements, again, no surprises when you visit.  These are mechanisms from an 1868 book by a fellow named Henry T. Brown.  Not all the movements have been animated but many have and I wonder if I couldn’t find some uses in my math courses.  Take a look at Movement 68

I imagine displaying the animation and asking them to sketch a graph of the motion of the teeth on the red gear perhaps.  Not a bad example of a piecewise function.  Movement 38 is likewise fascinating.

My last thought for now is that Mechanical Movements would also be a great inspiration for some woodworking projects that result in interactive wall art for the home or office.  Someday…when I’m rehabilitated.

## Mathematical Thinking vs. Mathematical Content

I had an epiphany recently regarding my teaching.  This past spring I had decided to include a unit on Rubik’s cube.  My goal was to introduce cyclic notation, commutators and conjugates as methods for devising algorithms or uncovering appealing patterns on the cube.  To do this I would need the students to be able to solve the cube.  I decided to give them quiz credit for being able to solve the cube in under 10 minutes using a sheet of notes.   Most of them used the solution on Rubiks.com which is very straightforward.   Here is the material for the epiphany.  I did this, gave quiz credit, because I needed them to be able to restore the cube as a matter of practical importance.  When playing around with the mathematics that I wanted to share with them you enviably lose track and end up with a scrambled cube.  I felt a little guilty giving them a solid grade for this accomplishment because they were just learning an online solution.

Months later I realized that when they were solving the cube they were, in effect, going through the same thought process that many students have in a mainstream math course.  You begin with a problem similar to a previous problem.  You have been taught methods of rearranging, modifying, massaging or what have you in order to reduce the problem to another problem or solve it altogether.   If I ask a student to differentiate a function such as $\sin(e^{x^2-4x})$ then they recall a number of different facts and algorithms.  The derivative of the sine function, the chain rule, the derivative of the exponential function and the power rule. They apply these in a certain order to arrive at a product of their manipulations.  Contrast this with solving the Rubik’s cube.

You start with a scrambled state, unlikely to be one you’ve seen before.  You probably begin by correctly positioning and orienting the four edge pieces of a particular side forming a ‘plus sign’ (usually called the  bottom or top cross depending on how you hold the cube).  From there you proceed to position and orient the corners of that side which restores that layer of the cube.  This continues.  At each step there are various possibilities and accompanying algorithms for those possibilities.  The student has to decide which algorithm to use to accomplish the desired result given the initial state.

This is certainly analogous to the type of thinking we have our students perform during drills and practice and so is at least as valid as that mode.  However there are some key differences, differences that I can use to my advantage.  When a student successfully solves Rubik’s cube lay persons are generally impressed and interested.  They tend to engage the student and ask questions.  They might even ask if the student can teach them. So here we have a situation where a student who has likely not felt competent in mathematics and has likely been viewed that way by others ending up in a potentially empowering position.  They have learned something of interest to other people.  Something that is deemed difficult (and frankly it does take time and patience to learn these algorithms) and desired.  It’s not often the case that when you work out a problem from traditional mathematics content that lay persons engage you with praise and interest.  “Goodness, did you just work out that integral!  That’s impressive, what trick did you use?  Could you show me?” It’s also not likely the case that after a rousing good semester with partial differential equations you went home to regal your folks with solutions of the heat equation (though I used to send my mother Mathematica graphs of the functions with a short explanation :).

For non-STEM students the reason to teach them mathematics can’t be mathematics content which seems to be entirely for the purpose of preparing a student for calculus.  It must be that we hope that the process of studying mathematical content will result in mathematical thinking that they will carry with them after they have forgotten the content specifics.

Let’s put this in context here, because it’s important.  I teach a college course MAT101.  By the time my students walk into my classroom they have completed 11-13 years of mathematics instruction and I have them for about 14 weeks.  Whatever grand ideas I can imagine I have to set it into this reality.  This is not their only class.  This is an attempt to satisfy a requirement in a less painful way and hopefully an easier way.  The numbering of my course is suggestive: 101.  There isn’t a MAT100 on campus.  They’re generally not walking in hoping to undo all the unsatisfying experiences of their past.  They’re hoping to survive, to be done with mathematics and to move on with what they really enjoy.  I don’t mean to be negative.  The students are very often wonderful to work with and this class is my favorite to teach.  I’d prefer it over any other class, however I have understand how they perceive the class (through surveys) and work with that as my starting point.

I already have a course which assumes little prerequisite knowledge (I don’t want the past to continue to convince them of what they can’t do).  Now I have another goal: choose content that has or could have, lay audience interest.  That is, choose content that if performed in a public area is more likely to illicit comments or questions, Rubik’s cube being the easiest example.  In fact I have a number of properties I’ve been thinking about when looking at content in addition to public interest.  For example, it’s clear when you have solved Rubik’s cube.  It’s not often clear (for those that struggle with the skills) when an equation is solved correctly.  We as teachers attempt to give our students methods of checking their work and these are important but these almost assume the same skills, or in some cases, deeper understanding, in order to carry out.  The ability to creatively experiment or engage in some sort of ‘play’ or fiddling with the possibility of discovery would be another important property.

Another property would be some cultural connection, though this is tied in with public interest.  Consider string figures (which I’ll eventually write about here) of which cat’s cradle is a two person version.  There are a great deal of string figures from around the world in many  cultures and this activity has many mathematical aspects, is visually appealing and is the sort of thing you’d like to share with others.  It, like the cube, also invite different levels of problem formalization which is a neat idea I came across somewhere on the internet.  Certainly one of the things we do as mathematicians (scientists as well) is to formalize a problem so we can understand it better and break it down.  Develop a language to talk about it, to communicate ideas.  Build a model to work out various aspects of the problem, etc.  For the cube and string figures, building a language, a short hand seems very necessary.  Writing out prose would be prohibitive (check out the online version of Jayne’s classic book on string figures: http://www.stringfigures.info/cfj/) or at least cumbersome.  Breaking down the process of string figures in order to experiment with different algorithms and the resulting figures is a wonderful way to connect mathematical thinking with tactile manipulation and culture studies of pre-literate societies.  (check out James Murphy’s excellent book on this topic, he taught string figures at a high school in NY for many years).

Beyond those two examples: origami and other folding math (Fold and cut theorem for example), Blackjack and card counting, paper topology (lot’s of room here for predict and check activities), compass and straightedge tessellations (particularly Islamic geometry art).

The properties mentioned above also have the potential for another benefit.  They might be able to save me from myself.  It’s very easy to become excited about a topic in mathematics and to want to share it with your students.  It’s hard to tell what will fly and with whom it’ll fly.  For several semesters I followed a unit on Fermi problems with a unit on ridiculously  huge numbers (exponential growth, factorials, Knuth arrow notation etc) and would include such stories as Borge’s Library of Babel.  While some students really enjoyed this unit, it mostly fell flat.  The mathematical content seemed too similar to traditional mathematics and the skills needed to really enjoy the content, while basic, were frankly out of reach (whether because of self confidence or inability I’m not sure).  Likewise I sometimes would follow that unit with an introduction of infinity.  Again, some students would be floored by these ideas, but for most not so much.  However, the abovementioned unit on Fermi problems generally went quite well, perhaps because of the perception of no single  right answer?

The mentioned activities certainly are used as vehicles to introduce and work on what would  be considered traditional mathematical ideas, but they’re pretty well disguised.  Students find themselves challenged and engaged and it’s that second bit that I constantly strive for.  Watching my students glow with pride having solved the cube, watching them help each other, watching them find patterns and share them, watching them fiddle with their cubes instead of their phones, watching them play blackjack and have wonderful conversations about card counting and odds these have been some really great experiences to have.

The hope is that by focusing on novel and engaging content, content that they want to share and content that others want to hear about, that my students will feel a sense of confidence or enjoyment in an activity they didn’t think could happen.  It takes objects of mathematical thought and makes them relevant to their lives.  Mind you, these kids know that mathematics is important and they understand that their phones and what not rely on mathematics, but they don’t want to build phones or power grids.  However, some of them may want to tessellate, solve puzzles, fold paper or play games.   If you’re the first to introduce them to this activity and if you can get them thinking mathematically about it, that connect may well persist and blossom.

Many ideas presented here today have been bubbling in my mind for the past two months.  I hope to develop them more this fall and will try to blog as the 101 course unfolds.

## Reflections and Reports of Representation Theory – Spring 2015 – 1

I’m sitting in a course on representation theory this semester and though it will primarily deal with finite groups I’m extremely excited!  The professor is very good, very clear and motivates material very well.  The past few days has been a review of basic group theory but today a few nice items came up I wanted to share.

I’ve known about the first isomorphism theorem for a while but I saw a lovely example of it today.  Take the general linear group over an arbitrary field F then the determinant is a surjective homomorphism $det: GL_n(F)\to F^*$ where F* is the field without it’s ‘addition’ identity (i.e. zero).  Then the kernel of this map  are those matrices with determinant a unit in F, so $SL_n(F)$!  While a quotient like $GL_n/SL_n$ certainly taxes my mind, we know from the first isomorphism theorem that this is isomorphic to F*.

I’ll try to keep this blog in the loop of this class.  Also I’m trying to form a reading group on campus on the Foundations of Mathematics by Kunen so with any luck I will have some posts on that as well.

Posted in Uncategorized | 2 Comments

## RSA encryption from a novice point of view – 1

I mentioned in a previous post that I covered RSA encryption in the liberal arts math course I teach.  It was part of a progression of exposing the students to larger and larger finite numbers before tackling the concept of infinity.  RSA is a neat idea because you give out certain public information that allows anyone to encrypt a message and send it to you but you possess the only means of decrypting the message.  This sort of encryption is called asymmetric for that reason.

The basic idea is to take a couple of large prime numbers p and q and multiply them to form the RSA modulus, n.  This will be a public number.  The size of these numbers depends on the level of security you’re interested in.   Next you calculate the totient of n, $\phi$ which is generally difficult to do except when you know the prime factorization of the number.  In that case $\phi(n) = (p-1)(q-1)$.  This totient is then used to create the other public number, the public exponent.  We look for a number e such that $1 and that $GCD(e,\phi(n))=1$.  I’ve read that general practice is to use $e=65,537$ as long as it’s relatively prime to $\phi(n)$.  In class I had the students start with 3 and work their way through the primes checking divisibility of the totient $\phi(n)$.

EXAMPLE: choose p=19 and q=41.  Then n=779 is the RSA modulus.  The totient is $\phi(779)=(19-1)(779-1)=720$.  At this point any prime that doesn’t divide the totient will work as our public key, so e=7 would work.  The private key depends on this value and sometimes can be awkwardly large for casual calculations even for the large integer calculator I’ll be using (for example using 7 will result in a private exponent of 103).  So our public key is (7,779)

EXAMPLE: Suppose we want to send the  message “To be?”  We’ll need to convert the 6 characters in this message to their numerical value.

084  111  032  098  101  063

concatenating,

084111032098101063

Which is a number bigger than n (which is three digits) so we’ll chop it up into strings 2 digits long.

08  41  11  03  20  98  10  10  63

Pretty neat eh?  The numbers we end up exponentiating don’t directly represent the encoded characters we wish to send.  The next step is to exponentiate the message modulo n.  As you might imagine, there are clever ways of implementing modular exponentiation (try figuring out $3^{3827616842}=??mod(5)$ for example) but that’s not the focus of the post. Our goal now is to take our numerical message m and create our encrypted version $c=m^e mod(n)$.

EXAMPLE: Our public exponent is e=7 and our RSA modulus is n=779 so we compute such things as,

$08^7=84 mod(779)$

Doing this for nine strings results in,

084  287  486  629  172  420  756  756  503

Notice I added a leading zero to the first number, 84 to make it a string of three digits, 084, the same length as the RSA modulus n.  Now concatenate the numbers into the string we’ll send.

084287486629172420756756503

Now we have our encrypted message.  We then send this in plain sight of any nefarious individuals.  As long as our modulus is sufficiently large it will be impossible to factor on any reasonable time scale and as long as our implementation of the encryption scheme is sound the strength of the encryption will be that of the mathematics.

The individual who gave us the public key has a private key, which is a single number that only they know.  The process of decryption is essentially identical to the process of encryption.  The receiver uses their private key as an exponent and exponentiates our encrypted message modulo n.  This will result in the original message.  How do we find this private key?  Let the private exponent be called d.  Then we require d be such that $ed=1 \mbox{mod}(\phi(n))$.  This essentially means that our original message m when raised in succession to those two exponents, $m^{ed}=m \mbox{mod}(n)$ returns the original message.  There are clever ways of doing this and then there are easy ways to show your students.  Essentially we’re requiring that $ed-1$ be a multiple of the totient so $ed-1=k\phi(n)$ for some natural number k.  Solving for d, $d=(k\phi(n)+1)/e$ where d must be a natural number as well.  You can just try values for k until d ends up an integer.  Not practical for an actual implementation of RSA but easier for students than explaining the extended Euclidean algorithm.  My students were very successful with this approach.  It’s true that I tested all the exercises to make sure they never had to try anything larger than k=10 (and often much less) but I wanted the focus to be on the encryption process which is essentially very straight forward.

EXAMPLE: We’re looking for $d=(k(720)+1)/7$.  Try $k=1,2,3$ etc.  We happen to get lucky and when k=1 we have our private exponent, d=103

Let’s decrypt the message we received, 084287486629172420756756503

The recipient knows that this is a concatenated series of strings all of string length equal to the number of digits in the RSA modulus, n, that all parties know.  So they break up the message and remove any leading zeroes.

84 287 486 629 172 420 756 756 503

Each of these numbers is exponentiated modulo n using the private exponent, d.  So for example,

$84^{103} = 8 \mbox{mod}(779)$

Do this for all nine strings, adding in leading zeroes to keep string length to equal one digit less than the RSA modulus.

08 41 11 03 20 98 10 10 63

Concatenate these strings and then break up into blocks of length three, the length of the ASCII code,

084 111 032 098 101 063

Which yields “To be?”

The mathematics behind this is surprisingly accessible, though the implementations seem to possess endless details, pitfalls, and tricks to avoid the nefarious from gaining advantage in the application of the mathematics to this attempt to protect information.  It’s also incredible, as I’ve already talked about, that some of the largest numbers used in any application are used in this application.  Safe browsing of the internet relies, in part, on the massive numbers used in RSA encryption.  This realization has certainly pushed me down a path of philosophical reflection over the nature of large numbers and their existence.

If I had a wish list of things to follow this post with it would be (1) learning enough about sniffing wifi networks to ‘see’ this encryption happening and ‘see’ the public key given to my browser (I’d like to show my classes), (2) learn more about how secure certificates are made using encryption so that you know that the website you’re looking at really is the website you’re looking at and (3) A bit about alternative encryption schemes such as Elliptic Curve Cryptography, or ECC which is supposed to be ‘stronger per digit’ if you will. Meaning that you can use smaller numbers without sacrificing encryption strength, something which is supposed to be helpful in this mobile computing age where we want to be able to securely interact with the internet on smaller devices while at the same time nefarious agents are constantly looking for vulnerabilities and all the time gaining more powerful computing hardware.

I’m a novice at this to be sure but hopefully this whets your appetite for more and enables  you to share these ideas with your students with less leg work than I have had to do.

If you’d like to see this done a bit more realistically you can find RSA key generators online.