Tuesday, August 31, 2021

On Chained Relations

In all of the college math courses I teach -- from basic algebra, precalculus, calculus, discrete mathematics, etc. -- there's a particular piece of syntax that perpetually trips up students, and it's this: chained relations

To be clear, chained relations are compound statements in mathematics with more than one relational symbol (including equalities and inequalities). Crack open any math textbook and you're bound to see almost any piece of symbolic expression written in that format. And yet my students are always tripping all over themselves at the difficulty of either reading or writing them. Have you ever noticed that before? Let's consider the several factors contributing to this difficulty:

  1. Even a single equality is hard for people to truly understand. Numerous academic papers have been written on this. More than one person has pointed out that the use of the equals-sign in grade-school problems and the calculator point people in the incorrect direction of a functional understanding, rather than a relational understanding.

  2. There is no explicit instruction in the form in any curriculum. To my knowledge, I've never seen the status of chained relations directly addressed or tested in any math textbook at any level (again, whether in basic algebra, precalculus, etc., etc.). At some point instructors just start using it and we assume students will understand by osmosis.

  3. The compound form is entirely foreign to a natural language like English. Consider something super simple like \(a = b = c\). Translated literally to English, it says, "a is equal to b is equal to c" -- and that's a run-on sentence, disallowed by the rules of English grammar. But here in the algebraic language we have an entirely novel mode of permitted expression.

Considering that last point,we might observe that there is (surprisingly, for such a basic point?) unresolved confusion about how one should even pronounce out loud a simple chained relation. For example:

(Note that while the question is essentially the same, those two queries have entirely different top-voted answers.)

So in my opinion, the status of chained relations is one of those classic blindspot/submarined issues that's buried in math education, and winds up troubling students throughout their career. To instructors: it's "obvious" and never rises to consciousness as an issue. To students: it's a quagmire that's never clearly addressed or exercised.

To this end, I've found that I need to start my discrete mathematics classes foremost with direct instruction on this issue; namely a short document that I ask students to read -- and that I'll be referring them back to throughout the semester when mistakes are made. You can download that here:

On Chained Relations (PDF)

And then to practice reading them, a timed quiz at the Automatic Algebra site:

Quiz on Chained Relations

Interestingly with that quiz, I've had different math-trained professionals try it and tell me variously that (a) it was entirely trivial and of unclear value, or (b) it was entirely impossible within the span given on the timer. Isn't that interesting? What do you think?

Tuesday, July 20, 2021

Veritasium on Learning Styles

The Veritasium channel on YouTube recently released a very high-quality video on "The Biggest Myth in Education", to wit: the Learning Styles theory. It's much needed and much appreciated. Includes comments by famed cognitive psychologist Daniel Willingham, with whom I had the chance to speak in person on this (constantly frustrating) subject a few years ago. From the climax:

Review articles of learning styles consistently conclude there is no credible evidence that learning styles exist. In a 2009 review, the researchers note: "The contrast between the enormous popularity of the learning styles approach within education and the lack of credible evidence for its utility is, in our opinion, striking and disturbing... If classification of students' learning styles has practical utility, it remains to be demonstrated."

Big thanks to Veritasium for producing this. Pass it on!

Tuesday, July 6, 2021

Minimal Mental RSA Cryptosystem

As an exercise, I went hunting for smallest possible RSA cryptosystem such that I could perform all of the encryption and decryption calculations in my head. This turns out to be quite silly, of course. But perhaps you could consider using this as a toy-box classroom example, or possibly like me, you may find it helps you remember the process by being able to exercise the whole thing concretely in your brain. 

I'll use the same notation as in the Wikipedia: RSA (cryptosystem) article, which you may want to review (I'll avoid repeating the basic principles of the system here). So our system needs distinct primes p and q, the product n = pq, and decryption/encryption exponent keys d and e. I'll also use, as per the original RSA paper, φ(n) = (p − 1)(q − 1) as the value with which our keys need to avoid common factors.

Obviously, the fundamental calculation for both encryption and decryption is computations of me mod n. Which looks pretty simple, unless you have a large exponent e, and you're trying to do this in your head. Secondarily, having big plaintext values m complicates the job. Being able to reduce modulo n seems nice, but even as an intermediary step I don't want to be raising double-digits m's to double-digit e's, say. 

So the first job is to find a usable encryption exponent e. As noted on Wikipedia, "the smallest (and fastest) possible value for e is 3". Let's just reflect on why that is for a second. You can't use e = 0, aside from collapsing every block to a value of 1, because gcd(0, φ(n)) = φ(n) ≥ 2, instead of the required 1 (since the minimal primes p and q are 2 and 3, the minimal φ(n) is (1)(2) = 2). You can't use e = 1, because that would send every block to itself, and not demonstrate any encryption at all. You can't use e = 2, because at least one of your pair of primes is odd, so either (p − 1) or (q − 1) has a factor of 2, which can't be shared by e; and for the same reason e can't be any other even number.

So our first valid option for exponentiation is e = 3, and the next one is e = 5, etc. I don't know about you, but I really don't think I can do 5th or 7th powers of arbitrary numbers reliably in my head (even modulo n), so I'm aiming to just use e = 3 here.

Now, what can we use for the primes p and q? Even using one as big as 7 causes problems; say if p = 7, then (p − 1) = 6 = 2(3), at which point the factor of 3 blocks you from using our desired encryption key of e = 3. If I used a pair like 5 and 11, then n = 55, and I'm poised to be cubing numbers as big as 54, which is way outside my mental times-tables. So it looks like I'll be compelled just use 3 and 5 as our prime pair.

In this case, if p = 3 and q = 5, so n = 15, then we don't even have sufficient space to encode all the letters of the alphabet (I said this was silly, right?). Also, we'll only be able to encode one of our limited characters at a time, which loses sight of the fact that RSA is a block cipher, but let's choose to forgive that. We'll enumerate the first part of the alphabet as A = 0, B = 1, C = 2, ... O = 14. Also note that
φ(n) = 2(4) = 8 (so the only factor we need to avoid in e is 2, and we can indeed use e = 3).

What about our decryption key exponent d? Well, there's a goofy coincidence here: solving the required congruence de ≡ 1 (mod φ(n)), that is, 3d ≡ 1 (mod 8)), we get d = 3 (because 3(3) = 9 = 8 + 1). Here we have d = e, so our encryption and decryption keys happen to be the exact same thing. On the one hand, this seems like a degenerate example for how the RSA system should work, but for our mental arithmetic, it's pretty darned nice that both keys are the smallest value possible. (As noted, I really didn't want to be raising values to a 7th power or something for decryption purposes!). So we can work with that.

Here's an example. Let's say we want to mentally encrypt the plaintext message "MIND". Using our number-encoding scheme, these four characters are represented by the numbers (12, 8, 13, 3). Computing the necessary cubings-modulo-15 to encrypt, we can feasibly find in our head:

  • 12³ = (144)(12) = (135 + 9)(12) ≡ (9)(12) = 108 = 105 + 3 ≡ 3 (mod 15)
  • 8³ = (64)(8) = (60 + 4)(8) ≡ (4)(8) = 32 = 30 + 2 ≡ 2 (mod 15)
  • 13³ = (169)(13) = (165 + 4)(13) ≡ (4)(13) = 52 = 45 + 7 ≡ 7 (mod 15)
  • 3³ = (9)(3) = 27 = 15 + 12 ≡ 12 (mod 15)

So our encrypted message is (3, 2, 7, 12), or "DCHM" if we send it as alphabetic characters. Decrypting is (fortunately or unfortunately, depending on your perspective) exercising the exact same mental algorithm:

  • ≡ 12 (mod 15) [as above]
  • ≡ 8 (mod 15) [super easy!]
  • 7³ = (49)(7) = (45 + 4)(7) ≡ (4)(7) = 28 = 15 + 13 ≡ 13 (mod 15)
  • 12³ ≡ 3 (mod 15) [as above]

And indeed we recover our original transmission of (12, 8, 13, 3), or "MIND".

Okay, hopefully you can appreciate that example. Because I had to work really, really hard to find one that avoided being totally nonsensical. Here's why: In our toy cryptosystem, most characters get sent to themselves under encryption! Specifically (looking at the numerical representations): 0 → 0, 1 → 1, 2 → 8, 3 → 12, 4 → 4, 5 → 5, 6 → 6, 7 → 13, 8 → 2, 9 → 9, 10 → 10, 11 → 11, 12 → 3, 13 → 7, 14 → 14.

In summary: Only the six plaintext values 2, 3, 7, 8, 12, and 13 get sent to other images; the other nine values all get sent to themselves. That is, the only letters that get transformed are C, D, H, I, M, N -- and you'll notice that I carefully constructed my example of "MIND" to use exclusively, and almost all of, these available characters. Note in particular that "I" is the only available vowel in that set (initially I considered encoding A = 1, B = 2, etc.; but in that case we get no vowels with images different from themselves.)

In case you want to memorize these transformations directly, then it might help to observe the pattern, starting with 14 and wrapping around, that you get 3 values sent to the same as themselves, then 2 with different images, then 3 same, 2 different, 3 same, and 2 different. (Again noting a total of 6 characters that get sent to images different from themselves.) And the decryption function is, obviously, identical. 

Is that of any interest? As I opened with, it's pretty darned silly. We can only handle letters up to O, we lose the block-cipher action, the encryption and decryption keys are identical, and most of our values get sent to themselves under the transformation. But I thought it was an interesting puzzle to see if there as any example that I could compute mentally without any mechanical or even pen-and-paper aid, and it turns out there is.

Leave a comment if you ever use that in a class or paper as a warm-up demonstration!