Daily Archives: April 19, 2012

My daughter’s possibly useless school laptop

Some years ago, Kevin Rudd, then the opposition leader, made a promise to deliver laptops to all senior high school students:

Kevin Rudd with laptop

Since that time he has been Prime Minister and been deposed, but the Labor party, still in power, have maintained his vision. Yesterday my daughter, in year 10 (there are 13 years in Australian schooling, starting with Prep, then years 1-12), received her laptop.

Now, I’m all for learners of all ages having access to the best technology which supports and facilitates their learning. Technology for its own sake, however, leaves me cold.

But this seems to be the case here. This laptop program, officially known as a 1-to-1 program (1 laptop for 1 child), no matter how noble its reasons, has been poorly implemented. For one thing, the laptops aren’t insured outside of school, which means we have to cough up a year’s insurance (you can’t insure for a shorter period), even though my daughter will be handing hers back before the end of this year. Her school has acquired 173 laptops, but no charging stations or trolleys, so students are expected to take their laptops home each night to charge them. Students who ride bikes (such as my daughter) or who take public transport, are naturally worried about the safety of their laptops.

The laptops will not replace textbooks. Students will still be expected to have their huge textbooks, and lug them between home and school. This is a hugely wasted opportunity. I’m not sure (and as far as I can tell, neither is the school) what the laptops will be used for, and how they will enhance student learning. The days are long gone when laptops were seen as new and exciting technology. You can pick up second hand ones very cheaply now, and probably ones more powerful than these school laptops. (In fact, you could probably buy a decent but oldish machine for the cost of the insurance of these new ones.)

Maybe a teacher (or a politician) once had a vision of a class of bright eyed children, each sitting with his or her own laptop… but so what? Where’s the pedagogy? Maybe these machines will just be glorified typewriters, and in the couldn’t-be-bettered words of Gary Stager, used for: “…making PowerPoint presentations about topics you don’t care about for an audience you will never meet.”

Let me be quite clear: I love technology, and I think the educational possibilities and potential are enormous. But just putting technology in place is not, in itself, educationally sound. What this program needs is an infrastructure to support it: for example wikis and school-based chat, digital textbooks, access to collaborative software (out with MS Word, in with Google Docs), robust and fast networking (that is, open up the laptop, and it automatically and quickly accesses the school intranet), digital art and music software, well-trained and enthusiastic teachers, and so on.

Here are a few interesting reads:

The Chor-Rivest cryptosystem

This is a public key knapsack system which (like all knapsack systems) has been broken.  However, it took longer to break than most, and is a very elegant use of finite fields.  I like to use it for two things: as a nice example of finite fields in practice for students, and as a test for a computer algebra system.  All CAS’s can do calculus and some algebra, but not all of them are equal when it comes to abstract algebra.

Anyway, here is a simplified version of this cryptosystem.  (The full version includes a permutation, which I’ve left out as it has nothing to do with the finite field computations).

First, the setup.

  1. Choose a prime p and integer h, and create a finite field GF(p^h)=\mathbb{Z}_p[x]/f(x) where f(x) is a polynomial of degree h which is irreducible over the field \mathbb{Z}/p\mathbb{Z}.  Let g(x) be a primitive element in the field.
  2. For each i\in\mathbb{Z}/p\mathbb{Z} compute the discrete logarithms a_i=\log_{g(x)}(x+i).
  3. Choose a random integer d with 0\le d\le p^h-2.
  4. Compute c_i=(a_i+d)\mod{p^h-1} for all 0\le i\le p-1.
  5. Then your public key is ([c_0,c_1,\ldots,c_{p-1}],p,h) and your private key is [f(x),g(x),d].

Messages are binary strings of length p with exactly h ones.  (It is easy to represent numbers in this format.)  Encryption is obtained by

C=\sum_{i=0}^{p-1}m_ic_i\pmod{p^h-1}.

Note that this is a standard knapsack-style encryption.  The difficulty, as with any knapsack, is to determine which of the c_i values were used to create the sum.

For decryption, the following steps are used:

  1. Compute r=(C-hd)\bmod(p^h-1).
  2. Compute u(x)=g(x)^r\pmod{f(x)}
  3. Compute s(x)=u(x)+f(x).
  4. Factor s(x) into linear factors

    s(x)=\prod_{j=1}^h(x+t_j)

    where each t_j\in\mathbb{Z}/p\mathbb{Z}. The values of the t_j in the factorization are the positions of the 1′s in the message.

To see that this works, first notice that u(x)=g(x)^{C-hd}\pmod{f(x)}. Then

u(x)=g(x)^{(\sum_{i=0}^{p-1}m_ic_i)-hd}\pmod{f(x)}.

Replacing c_i with its definition using a_i produces

u(x)=g(x)^{(\sum_{i=0}^{p-1}m_i(a_i+d))-hd}\pmod{f(x)}.

Since exactly h of the m_i values are 1, this can be rewritten as

u(x)=g(x)^{(\sum_{i=0}^{p-1}m_ia_i)}\pmod{f(x)}.

Writing the left hand side as a product of powers produces

u(x)=\prod_{i=0}^{p-1}[g(x)^{a_i}]^{m_i}\pmod{f(x)}.

Since by definition we have g(x)^{a_i}=x+i this last equation can be written as

u(x)=\prod_{i=0}^{p-1}(x+i)^{m_i}\pmod{f(x)}.

Finally, since both sides of this equation are monic polynomials, and are equal modulo f(x), it follows that

s(x)=u(x)+f(x)=\prod_{i=0}^{p-1}(x+i)^{m_i}

and since the m_i values are either zero or one, we end up with a polynomial which can be factored into the terms we need.

For further discussion, see the Handbook of Applied Cryptography, chapter 8.

In future posts, I’ll show how this cryptosystem can be quickly implemented in Sage, Axiom, and Maxima.