Wednesday, January 10, 2007

The RSA Challenge

I was just browsing through some more of my old projects and came upon this crazy little thing. If I recall correctly, some years ago I was surfing the net as usual and I began to read about the RSA challenge. I've always been quite fascinated with mathematics, numbers and especially prime numbers and perfect numbers....In fact some of my earliest childhood memories are of prime-related programming projects and later on spend countless cpu-hours on the mersenne project, looking for new big primes...but I digress.
Anyway, back when I started reading about the RSA challenge and the stories about the numbers already factored I quickly realized that I'd have probably as much chance of winning one of the prices there as a blind man would have of finding a needle in a haystack. But even so, he most definetly won't find it if he isn't even looking. So naturally I began my search...

The $20.000 RSA challenge award was paid november 2005 to a research team that had spend around 30 2.2 GHz Opteron CPU years finding the prime factors to a 640-bit number. Since I don't have that kind of time or CPU power on my hands (nor the algorithms / mathematical knowledge) I decided on another approach: I was going to play in the big Prime Lottery.
I made a small windows application that would pick out random numbers (pseudo primes) around the right size as I could imagine a factor to a challenge number would be, and then check if they were in fact a factor. Crazy? perhaps a bit when I think about it retrospective. Hopeless? Yes indeed.
I've always believed that people who buy a lottery ticket for "lotto", danish state lottery are in fact just paying an extra tax for being bad at maths....Yet the probability for them of winning the big price is probably bigger than mine at finding a prime. Anway it was fun coding and I hope you'll get a laugh out of playing with it.

The application uses the BigInteger class from Chew Keong TAN, which can be found on

Download my RSALottery app here. The zip contains both the VS solution as well as a compiled executable.

No comments: