Log in

No account? Create an account
Small things amuse small minds - Many a mickle maks a muckle

> Recent Entries
> Archive
> Friends
> Profile

August 11th, 2002

Previous Entry Share Next Entry
01:56 am - Small things amuse small minds
It has been a pretty lousy couple of days.

I am part of the Great Internet Mersenne Primes Search project, which uses computers all around the world to look for prime numbers when they aren't doing anything else. So far, my computer has confirmed that (2^6423367)-1 is not prime, which took three and a half weeks, and that (2^12877243)-1 is not prime, which took three and a half months. Currently it is trying to establish whether (2^33299459)-1 is prime or not and it has been working on this for about four and a half months. There's approximately a 1 in 250,000 chance that it'll turn out to be prime; if it is, I'll probably win about US$50,000. I ought to know whether it is or not in about the middle of 2004; faster if I upgrade the processor, slower if I get a 9-5 job and don't need to leave the computer on at home all day. I dare say that this is the last 100-digit prime I'll be trying for a while - back to the tiddlers after this.

However, from time to time I look at the Prime95 client which faithfully reports its progress through a particular part of the calculation. (I tend to look at this client a couple of times a day, usually just before I am about to turn the computer off.) Part of the fun is that it will do this to whatever extent of precision you specify; numbers, numbers, numbers.

By the happiest of coincidences, a quick check of the client reveals that it is now 12.3456% of the way through this part of the calculation. No, I wasn't waiting for this string of digits to crop up - it was what came up at a pure chance glance.

It has been a pretty lousy couple of days, but I will be going to bed tonight with a big smile on my face.

There are quite a few distibuted computing projects of this type. Probably the most famous is the SETI-at-home project, which was always famous for its high concept and its particularly attractive screen saver. (As far as I am aware, the project finished a couple of years ago, but I dare say that people are still running it just for the pretty pics.)

Much older, but now only second most famous, is the RC5 cryptography cracking effort. Thousands (probably thousands of thousands, I can't remember) of computers around the world are trying to decipher a message encrypted using a 64-bit key. The theory is, at least in part, that if a network of amateurs can work together to crack a key then 64-bit encryption is in some sense not safe and so the world at large should be permitted to use stronger encryption than that.

There are a few arguments as to why this isn't all it might be cracked up to be. Firstly, there is a nagging doubt that the Big Bads (whoever they may be) might have computing power massively in excess of that produced by the global network of amateurs. Secondly, people tend to use far more bits than 64 in their encryption, even though I vaguely recall something like encryption using more than 80 bits being illegal outside the US.

However, the fact that the project exists at all is inherently great fun and so very interesting. Unfortunately, the stats currently seem to be broken, but a week ago, the global team had searched something like 81% of all possible 64-bit keys in nearly five years, and so the chance of the message being deciphered tomorrow had grown as high as 1 in 160-ish.

Incidentally, the chance of the key being in the last 19% of the keyspace to be searched is (assuming decent randomness) just 19%, so we're starting to get to the point where we really wonder whether the correct decipherment has been discovered and somehow lost. It's just about possible that this figure might get to 100% without the answer being found, which would represent a waste of thousands of computers for, say, five and a half years, which would be vicariously amusing and a victory for the self-destructiveness of human nature.

However, the project has successfully cracked smaller codes in the past without screwing up in this way, so they at least have a good track record. If the cipher is cracked then there will be a strange "end of an era" party sensation among the users. You can't turn your nose up at five years' work, whose cost might be estimated at thousands (or millions?) of dollars.

One of the other geekycoolsillynice features of the project is the competitiveness that it has inspired, for, really no particularly good reason other than a testament to the vagaries of human nature. Much as kids have joined gangs since early childhood, much as online gamers join clans and guilds for mutual protection in online games, various cracking teams have formed to compete for, well, the sake of competition. Naturally, once one team starts doing well, other people want to join it, because being part of a winning team is nice; however, there are a vast number of teams in competition, promoting (usually...?) friendly rivalries between countries, between operating systems, between fandoms, between organisations, between web sites. After all, there aren't enough arbitrary rivalries in the world already, oh no, not at all.

The most famous teams are the Dutch Power Cows, effectively a Dutch national side, and Team AnandTech. AnandTech is a hardware news site about fast PCs, so the theory goes that people might learn about fast PCs from that web site and demonstrate their knowledge by using their fast PCs to crack the code.

If I were to join this project and affiliate myself to a team, it would probably be to that of Oxford University. (Duh.) I knew quite a few of the movers and shakers instrumental in the establishment of the team at the time when the 64-bit version of the project started; indeed, in the early days, the Oxford University team got somewhere in the top 100, maybe even top 40 or so. However, since then, enthusiasm has waned and we're not allowed to run the project on the vast networks of computers there any more. Currently the team is languishing at #875 and falling. (Hmm. Alternatively, I could join the team of users from the ISP I use, Demon Internet, who are at #155.)

The GIMPS project doesn't currently have the same sort of team competition aspect to it, which is kind of a shame. I looked into both GIMPS and RC5 when I decided to start some distributed client running. Can't really remember the reasons why I picked one over the other. (I can guess at them: theoretical better cause, bigger hugely theoretical prize, client produces funkier "percentage done" reports.)

There are plenty of other similar projects which have all the fun, competitiveness and geekiness without even the same weak sort of social or scientific cause. Here are two of my favourites.

Project Dolphin is all about keeping track as to who presses the most buttons on their keyboard. Err... that's it. It's as untrustworthy as hell if you don't believe that people can maintain 100 wpm+ for 24 hours a day, which I don't, but it is pure geekery just for the sake of it, which always has a strange sort of chutzpah. After all, you're pressing all these buttons anyway, so you may as well rack up some sort of score - and hence a world ranking - as a result.

Project Dolphin warn that Continued use of Pulse has been known to be psychologically addictive. After prolonged use of this software, not having it loaded may make you feel slightly "empty", and as though you are wasting your keystrokes for every key you type that is not being counted. ...stating that the warning is only half in jest. I can believe it.

(I suddenly feel the need for some sort of project to keep count of who enters the most in their LJ. Instead of establishing formal teams, you could establish average scores for each interest, thus determining which interest contributes most to the world of LJ and so is coolest. After all, part of the joy of the world of LJ is that almost everything else is tracked, so why not this...?)

Even more goodnaturedgeekygentlydaft still is Progress Quest. It is ostensibly a pastiche of yer MMORPGs like EverQuest, Ultima Online and so forth, in which people spend huge amounts of time performing repetitive tasks purely to get a stronger character.

(Big digression: occasionally, I feel grateful that I have decided to adopt the LJ sort of waste of time, which is at least theoretically vaguely creative, cathartic, social and inspirational of improved writing skills and personal development, rather than the MMORPG sort of waste of time. Still, you pays your money, you takes your choice. At least in MMORPGs, you can sell your castles, game gold, characters and so forth to generate real-life money. Anyone want to bid for the very desirable LJ nickname jiggery_pokery with a hopefully entertaining history of geeky posts behind it?)

The gimmick behind ProgressQuest is that your character goes around killing monsters, getting loot and magical items, purchasing weapons and armour, fetching and delivering miscellaneous goodies, improving statistics and learning spells... with absolutely no input from you whatsoever.

I managed to get my character, Spogalot, a Half Hobbit Half Panda HemiSemiDemiRuneCasterLordMage (or at least something like that - that's an exaggeration, but not a huge exaggeration) from #50,000 up to #15,000 by the time I finally got bored of remembering to start the program and leave it running in the background every time I booted up. (Yes, I am aware it's possible to automate this.) I'd be idly curious to know how many characters have since overtaken him by now.

Well worth a try if you have even the vaguest sort of interest in statistics-based RPGs, parodies of statistics-based RPGs or miscellaneous cute, geeky things which take no effort on your part. It's an in-joke for in-jokes' sake, it's MMORPGington Crescent. Give it a try: in ten minutes, plus checking in for one minute every two hours for four days, you'll have seen 99% of all there is to see. It's something to do, really - and it doesn't slow down your other background processes by as much as 1%.

Prime95 is up to 12.3624% by now; I have written 1800ish words in the intervening 90ish minutes. The smile at the numerical coincidence has faded, but I am definitely in a better mood than I was before.

(6 comments | Leave a comment)


[User Picture]
Date:August 10th, 2002 08:07 pm (UTC)

Proud member of GIMPS since 1996

The GIMPS project has come a long way since I joined them in 1996. You can see my name on George Woltman's page at http://mersenne.org/credits.htm - which goes to show that the special interest spotter that LJ offers can point people in the right direction.
Not only that, but I took part in The Weakest Link in New Zealand last year, which should interest your game-show side. (The episode never made it to air unfortunately, but I can provide some eye-witness information as to how it all hangs together, if you are interested.)
[User Picture]
Date:August 11th, 2002 06:52 am (UTC)

Re: Proud member of GIMPS since 1996

That's cool! I saw a couple of other names I recognised in there too - those of the Ricketts brothers.

When you have a list of (well, I didn't count, but it must be 500-1000) names, I tend to wonder what the chances are of two or more of them being the same. I only looked through the Smiths, Joneses and Browns and there weren't any given-name matches there...

TWL player? That's cool. I'm on mailing lists with a goodly number of others, to the point where it might start to be interesting and worthwhile to produce a document comparing experiences round the world. Let me ponder on this awhile.

12.3699% - I don't hang around before I check LJs...
[User Picture]
Date:August 11th, 2002 02:56 am (UTC)


"the global team had searched something like 81% of all possible 64-bit keys in nearly five years, and so the chance of the message being deciphered tomorrow had grown as high as 1 in 160-ish."

That's interesting, because it gives us a measure of the extent to which the total power of the computers involved has increased across the five years.

Or does it ? The power increase seems too low, so I'm betting that what this stat actually represents is a considerable increase in computing power combined with the migration of a huge number of participants across to SETI.
[User Picture]
Date:August 11th, 2002 06:41 am (UTC)

Re: Umm...

I'm sure you're right. Four and a half years ago, RC5 was the only famous distributed computing project known, now it is one of many and not nearly the best of the causes.

The RC5 stats are working again now. The project is 85.677% completed (only five digits of precision? Ha!) by now. "The odds are 1 in 184 that we will wrap this thing up in the next 24 hours. (This also means that we'll exhaust the keyspace in 184 days at yesterday's rate.)" It also means there's a decent chance (I'm not sure whether it's possible to assume a constant rate of progress in the future, but it isn't very likely to drop very much) that the whole shebang will get wrapped up by, say, the end of October - which is within touching distance. We are now at the point where if we see the headline "RC5-64 cracked!" on Slashdot then it won't come as a surprise.

Also note "There have been 329,151 participants since the beginning of this project. 25,661 of them were active yesterday..." which gives us a number of participants (presumably participants ~= machines?) and a proportion of dropouts.
Date:August 12th, 2002 10:09 am (UTC)
Chris, I assume that you know of books like Simon Singh's The Code Book, as well as Fermat's Enigma Last Theorem. Probably two books that are right up your alley.

Also, there are an interesting discovery in the world of primality within the last week. From slashdot.org -- Manindra Agrawal et. al. of the Indian Institute of Technology Kanpur CS department have released a most interesting paper today. It presents an algorithm that determines whether a number is prime or not in polynomial time. While I haven't gone through the presentation in detail, it looks like a promising, albeit non-optimized, solution for the famous PRIMES in P problem.

The link is here, but you'll need Adobe Acrobat Reader to see the article.
[User Picture]
Date:August 12th, 2002 10:20 am (UTC)
First para: yep, yep. In fact, one of my other Friends (madlori) wrote recommending the latter last week, and I replied to her recommending the former. (Well spotted on the different names across the Atlantic issue, too!) Definitely the Right Sort Of Thing, though.

Saw what you mentioned about primes on slashdot, too. Frankly, the words make sense on their own, but the sentences don't. :-)

> Go to Top