(no subject)

What do you do if you want to post a wide flat 101g envelope? According to the royal mail website you can't send it straight first class, it's too heavy. You can't send it large letter first class, it's too wide. And you can't send it first class packet because it's too thin.

What's wrong with that picture? First class packet rates apply if *any* of the four dimensions (length, width, thickness, weight) supernumerarynesses apply.

OK, you can deduce that after considering the page. It's the only way you'd ever design it. But (a) by that argument, they might as well just encrypt everything with a 20-bit key. You can deduce what that says, right? And (b) Sometimes bureaucracies polices do have to be complicated and counter-intuitive, so you can't always just assume it's the way you'd do it.

Why don't they just say what they mean? Then you wouldn't have to guess.

*gasp* *inhale* I also have a lot of objections to the pricing.

I the "ways to pay" section, there's half-a-dozen, including "first class stamps". You used to be able to use *any* stamps adding up to the required postage, nth-class stamps being valued at the current rate. I *assume* you still can. I bet it says somewhere. But I couldn't find it.

Surely more people have two first class stamps than one large letter first class stamp? And don't get me started on the idea of placing the weight boundaries so the prices are all simple multiples of each other!

OK, the site is *fairly* well designed. And ok, to be fair, I ought to know exactly how it works beforehand. And there is a convenient local post-office which I bet would have sold me whatever I needed. But a nice little tutorial on posting a letter wouldn't seem out of place -- someone has to do this for the first time, making it easy for them can only encourage them! :)

Weekend

Friday

People came over for bridge. It was fun. Though I'm inclined to gripe about not having an opening hand, considering what I did with it when I did, I won't complain.

Saturday Morning

I did a variety of productive and tidying things, making the weekend feel successful before it was over, and being able to relax for the rest of it.

Saturday Evening

I joined Mark in the Carlton, where I met a wide variety of people (including Ben with a surprise voles attack), including several I hadn't seen for a while and it was very nice to see again. Thank you Mark!

I came home quite drunk and late, and played computer games and tidied for a bit.

Sunday Afternoon

I went to Tim's birthday barbecue at his parents'. They've always been very nice to us, at university we visited a few times, and it was like a breath of home to be received into a proper house :)

Sunday Evening

The lovely Mair stopped over. We didn't get to see anyone else, but we chatted about books until late, and she divested herself of some she was trying to clear out, which I picked a bunch out of, also to be distributed to Cambridge friends at her direction (list of books to follow).

Monday Afternoon

I took a day's holiday and we went swimming and lounging at Jesus Green, and then read until pizza.

Monday Evening

Pizza was a little quieter than normal, so there was discussion including politics and genetics.

I went to bridge. Every bridge evening seems to have some theme, this could probably be best described as "be careful what you wish for, the gods' most savage curses come as responses to your own prayers." If you've got six diamonds, what do you want partner to say? Any other suit, and you're going to have difficulty showing what you have. And then he does, and what do you say then? You've got an eleven card fit, but 5D probably has three losers off the top. (In the most prominent example, we bid it successfully. As did the hand with a 7-6 zero-pointer :))

RSA

At some point, I read a description of how RSA works (I think in Simon Singh's book). In the first term of university, we did some simple modular arithmetic.

But only when I reread those notes did I realise that they met handily in the middle. I'd thought the RSA algorithm complicated, but from my notes, it seemed that it could be explained to an intelligent person with any knowledge of modular arithmetic in one page.

(Of course, the ways to use it are complicated.)

Lemma: Fermat's Little Theorem

This says that a^(p-1)==a mod p. I mentioned this before in the description of my example sheet. The proof says:

a.2a.3a...(p-1)a=(a^p-1).(1.2.3...p-1) mod p

But a,2a,3a... and 1,2,3... are each all distinct (else some 9a-7a is a multiple of p, so p divides 2 or a, contradiction). So they're simply a rearrangement and the products are the same. Cancel them from both sides and get:

1 = a^p-1

However, if you consider p not prime, but instead, say, mod pq, then the proof works the same if instead of considering all multiples of a, you just consider those that are a multiple of neither p nor q, ie. coprime to pq. There are pq-p-q+1 of these: pq numbers, less p multiples of q, less q multiples of p, plus one because we counted pq itself twice.

Then you get a^(pq-p-q+1)=a^(p-1)(q-1) which is what you need.

Wikipedia has a nice description and an explanation of the modular arithmetic necessary, if you want to be complete.

The algorithm

You do everything mod pq, the point being that it's easy to *do* it, but hard to *undo* it. (Like taking a square is easier than taking a square root, but lots more so, which is a feature of modular arithmetic.)

However, knowing p and q gives you an easy shortcut to undo it, so you tell everyone else the product, but keep the primes themselves secret.

Specifically, you treat the message as a number, a. You raise it to some power, e mod pq. (It doesn't matter what this is, so long as it's fairly big and coprime to everything. Wikipedia suggests just always use 2^16+1.)

That's encryption.

To decrypt, you raise it to *another* power, such that the total becomes a^(p-1)(q-1)+1, which is now a again.

In fact, you take e mod (p-1)(q-1). It's coprime so it has an inverse d, ed==1 mod (p-1)(q-1). Then a^ed==a^((p-1)(q-1)*lots+1)==1^lots*a=a.

Only you can do this, because finding the inverse used (p-1)(q-1) which only you know. Everyone else needs to work out what p and q are from pq, which is hard (tm), and why factorising large numbers is so important.

Addenum

1. That's all a bit informal. The wikipedia page is actually quite well written, and a good place to go if you want to see it properly.

2. I haven't touched on how to use it for cryptography, why it's hard to reverse it, how to avoid lots of clever lateral thinking attacks that bad people think of. That's all beyond me, cryptography requires more conscientiousness than I can bring to bear.

3. Fermat's Little Theorem is *also* used to *find* these large prime numbers. Just pick a probable prime, p. And apply a^p-1 to lots of different a's. If it ever fails, p isn't prime. If it never fails, it probably is. (In fact, this always fails for some notprimes, other tests do it differently. Wikipedia on primality tests gives details, which are really interesting.)

Addendum

You know how I love inventive special powers? This is great: http://www.misterkitty.org/extras/stupidcovers/stupidcomics65.html Not only is there an interplanetary force of dogs, the space canine patrol agents, who have special powers like having lots of legs, or an elastic tail, or "prophetic pup", but they're so unclear they stand around explaining them to each other :)

(no subject)

I watched Sky High again. Twice. It's a superhero-school movie. I'm not sure why I came back to it. It's a generic disney-ish movie, but feel good and pleasant -- and never painful to see, which is valuable extra -- and funny, though not ever so so.

Good things

* The special powers. They're mostly well chosen, they feel right, define the characters, and are cool without being too silly.

* Feel good. Yay, I'm happy that the good guys win.

* Warren Peace is cool. (Those of my friends who like bad boys I think will be pleased. Though none of the photos show him throwing fire. Somehow the whoosh as he throws his hands down and they ignite is just right. It does say something that the only interesting character is so gruff.)

* The scene where Leila starts to sit at Warren's table is the funniest I've seen in a little while.

Bad things

* Will's parents are superheroes, one who can fly and a master of martial arts, and one who's superstrong and invulnerable. One is always named first. Can you guess which?

( Some spoilers )