YAFU factors a 100 digit number for me…

On Friday, I left YAFU factoring a 100 digit number. I returned to find that it had discovered:

57790 93002 97410 10009 81807 59480 96292 62385 64081 79034 01512 68667
60949 55202 41611 02063 00992 86747 29621 36069 = 
85404 41503 10330 70274 85067 33621 20528 36393 71759 33321 * 
67667 37996 94567 83271 38746 19751 00109 79749 75402 10589

It took about 7.6 hours of compute time.

Addendum: I was reading “Factoring by electronic mail”, a 1990 paper by Lenstra and Manasse, and they listed some times for factorization of some large numbers. In Table 4, they list a bunch of challenging numbers, including the 93 digit composite factor of 7139+1. Their system took 13 days. YAFU was able to factor it in about 70 minutes on my current desktop machine:

Total factoring time = 4283.6700 seconds

***factors found***

P1 = 2
P1 = 2
P1 = 2
P3 = 557
PRP22 = 5312442648966139012589
PRP57 = 651666519182971782190402264651775450396158503528225547931
PRP36 = 190705279598948669274660288301207361

It found the small primes via trial division, the 22 digit prime factor via the ECM method, and then churned the rest out using the quadratic sieve.

On Factoring, by Jevons’ The Principles of Science

While reading the section on factorization of large numbers in Knuth’s Seminumerical Algorithms, I encountered a reference to an interesting claim by William Stanley Jevons. I did a google search, and found it in google books:

Knuth was quick to point out that the number that he gave was easily factorable in short order (even by hand, even in Jevons’ day) using Fermat’s method. I of course just handed it to the little program I wrote, and it instantly returned

8,616,460,799 =
	89,681 *

Addendum: How does Fermat’s method work? You basically try to express the prime as the difference of two squares. Let’s say that the prime P = u * v. If P = x^2 – y^2, then P = (x + y) (x – y), so the two factors u = x + y and v = x – y. You start by setting x to be just above the sqrt(P), and compute x*x – P. If the remainder is a square, then you have have two factors. Knuth gives several hints on how you could avoid testing many possible squares, but even acting trivially, you would only have to try 55 numbers before finding that…

8616460799 = 92880**2 - 3199**2
8616460799 = 96079 * 89681

Addendum: Lehmer factored this number in 1903. Golomb apparently had a Cryptologia article showing how it could be easily factored with a hand calculator, but I don’t want to pay $37 to get the 3 page reprint.

A Simple Python Program for Factoring…

Sometimes, your interests converge. Over on Programming Praxis, he had a coding challenge to implement Monte Carlo factorization. The last couple of days, I have been thinking a bit more about factorization, so it seemed like a good idea to give it a whack. I cribbed a version of the Rabin Miller primality tester off the web, and then coded the rest up in python.

#!/usr/bin/env python

# a basic implementation of the Pollard rho factorization
# Written by Mark VandeWettering <markv@pixar.com>

import sys
import locale
import random

class FactorError(Exception):
    def __init__(self, value):
	self.value = value 
    def __str__(self):
	return repr(self.value)

def miller_rabin_pass(a, n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1

    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in xrange(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1

def isprime(n):
    for repeat in xrange(20):
        a = 0
        while a == 0:
            a = random.randrange(n)
        if not miller_rabin_pass(a, n):
            return False
    return True

def gcd(a, b):
    while b != 0:
	a, b = b, a%b
    return a 

def findfactor(n):
    for c in range(1, 50):
	x = y = random.randint(1, n-1)
	x = (x * x + c) % n
	y = (y * y + c) % n
	y = (y * y + c) % n
	while True:
	    t = gcd(n, abs(x-y))
	    if t == 1:
		x = (x * x + c) % n
		y = (y * y + c) % n
		y = (y * y + c) % n
	    elif t == n:
		return t
    raise FactorError("couldn't find a factor.")
def factor(n):
    r = []
    while True:
	if isprime(n):
	    f = findfactor(n)
	    n = n / f
	except FactorError, msg:
    return r 

def doit(n):
	flist = factor(n)
	print locale.format("%d", n, True), "="
	for f in flist:
		print "\t%s" % locale.format("%d", f, True)

locale.setlocale(locale.LC_ALL, "")


This is a fairly challenging factorization, and after a few seconds, it outputs:

316,912,650,057,057,350,374,175,801,343 =

Use a Wii Balance Board with Linux

An interesting part of the Nintendo Wii design is that they rely on bluetooth for connecting their joysticks and (as it turns out) their Balance Board peripheral. This makes them pretty darned hackable. I’ve seen lots about using the “WiiMote” with computers, but this is the first I’ve seen that interfaces with the Balance Board. Nifty.

Use a Wii Balance Board with Linux
Use a Wii Balance Board with Linux

Factoring Large Numbers…

A few days ago, I mentioned that I was pondering the stages of Simon Singh’s Cipher Challenge that I didn’t complete “back in the day”. I was examining the DES portion, which still seems like it would take a while to solve, so I decided to skip ahead and figure out what the final stage was like. It seems to require the factoring of a 155 digit number. A bit of research reveals that such a number is still a pretty darned hard thing to factor. But while toying around, I downloaded YAFU, and tried to factor some numbers on my AMD machine. It took about an hour and a half to factor this 91 digit product of two primes:

22341447307961894892019996002707152857987347 =
411268404095925771725738109950909913561283687 * 3448123407928803465744207062833069247853720181

This corresponds to about a 300 bit RSA key.

It can factor 60 digit products in about 10 seconds.

Breaking Stage 10 of the Challenge requires factoring this 155 digit

10742 78829 12665 65907 17841 12799 42116 61266 39217 94753 29458
88778 17210 35546 41509 80121 87903 38329 26235 28109 07506 72083
50494 19964 33143 42555 83344 01855 80898 94268 92463

I should learn how this stuff works.

Looking back at Michael Jackson

Today came the news that Michael Jackson, the legendary King of Pop, died of cardiac arrest at age 50. Yes, I was a fan. Who wasn’t in the eighties? He was absolutely brilliant. He brought the combination of music, choreography, and film making together to completely change the landscape of pop music and television.

As I was driving home, I was listening to some of his songs on the radio, and I was remembering all the great video moments. The natural question was: what was his best video? It’s hard to argue with Thriller, but I think Black and White, Scream and Smooth Criminal are also good suggestions. Oh, and Billy Jean… Oh heck. I’m curious. What do you all think? Vote on your favorite below.


Magic Lantern Firmware for the Canon 5D

I’m a huge fan of gadgets which have the possibility of open source third party updates. I have a couple of Linksys routers that I’ve reflashed with DDWRT and/or Tomato and/or OpenWRT. I’ve played with the NSLU2. I have a Canon SD1100 which I run CHDK.

Today, I discovered another interesting one:

Magic Lantern Firmware Wiki

This is firmware for the Canon 5D Mark II DSLR to adapt it to the specific needs of film makers. While the 5D is nominally intended as a still camera, it has many advantages when compared to equivalently priced setups when used as a motion picture camera. This firmware is designed to expand this use considerably. Very cool.

Magic Lantern firmware introduction from Trammell Hudson on Vimeo.

Mmm… Cobbler

I like cooking. Well, eating really. Okay, eating and cooking. But in particular, I like what is generally called comfort food. The silly thing about most restaurants is that they don’t do a very good job of making comfort food. If you really want comfort food, the best way is to learn how to make it yourself.

When I was a kid, we used to pick blackberries and huckleberries, and my grandmother would turn them into delicious pies and my special favorite: cobbler. Oh, and strawberry rhubarb. Oooh, or apple cobbler. Served with creme. Or a scoop of good vanilla ice cream. Yum.

Why am I musing about this? Surfing while hungry…

Practical Alchemy: Cobbling Together a Cobbler – Video Game Podcast and Geek Culture Blog | The Weekly Geek

Taking my own code challenge…

Back in 2007, I made a blog post entitled “Code Challenge”, where I put forth a code challenge.

Code Challenge | brainwagon.

Nobody took the challenge. But what was slightly odder was that I had no recollection of making this challenge, or even what type of cipher it was. The only clue that I had was that it was apparently in response to an episode of the increasingly mediocre television show Numb3rs.

So, I considered it a challenge sent from past Mark to future Mark. The first thing I had to do was to try to identify the type of cipher. I had made this posting in June of 2007, and I guessed that I would have been watching episodes from that season (season 3) but possibly in reruns. I relatively quickly located “The Janus List” and its “straddling checkerboard cipher” as the likely method. Indeed, reading the description of the cipher (try this blog entry for details) it began to come back to me.

So, I tried to think of how to crack it. Here’s the insight. The straddling checkerboard cipher is essentially a simple subsitution cipher, except that each character is either encoded into one or two characters. What makes it easy is that there are eight single character letters, and twenty double character letters, but all double character letters start with one of the two non-single character letters. So, you can proceed by guessing what those two prefix characters are, and then scanning through the message. If you get more than 26 (or 28, if you include period and slash as most straddling checkerboard implementations do), then you know you haven’t gotten the right answer. But a quick look at the single letter frequencies in my case indicated that the characters 6 and 8 were vastly more frequent than the other characters, so I guessed that those were the right characters. When I busted the cipher up into characters, I ended up with 23 distinct symbols, which seemed entirely appropriate. I could then assign a random letter to each of those 23 symbols, and I’d have a simple cryptogram.

Here’s the resulting cryptogram:


Mind you, I might have accidently assigned a letter to itself here, so it’s not quite like a normal cryptogram. But it isn’t hard to make some guesses. ‘I’ is the most common letter, so is probably E. The last three characters are TTM, which implies a double letter right at the end, which suggested LLY. The double letter digraph FF occurs three times, which suggests that F might map to S. Putting these together makes the last word to look like SuccESSluLLY. Wow! U and C both look like they map to themselves. L is F. The message starts TraS, which suggests THIS. R becomes H, A becomes I. Now we have traction, K is A, S is M, V is G…


It’s a short skip and a jump to the complete decode:


Apparently, I was tenacious enough.

iPhone 3GS: My Early Experience

Well, my iPhone 3GS arrived on Friday, and I’ve had a couple of days of tinkering with it, so I thought I’d give my impressions about what’s cool.

First off, it’s a G3 phone (I previously had the first generation, EDGE only phone) so it’s networking is significantly faster. Combined with the processor speed increase, it’s really quite snappy. Email downloads faster, and displays faster. Google maps loads and updates quickly, zooming in and out nearly as fast as you can gesture. Even large webpages seem to load up nicely. Speed is nice.

The second thing I noticed immediately seems trivial: the screen is coated with an “oleophobic” coating, which means that it repels grease. It really works, and should be standard on all touch screen devices. My old iPhone was continually smudged by fingerprints, the new one looks great!

iPhone 3G owners have had the benefit of a true GPS for quite some time, but it was new to me, and works well. The iPhone 3GS is also augmented by a digital compass, which is frankly of little use to most of us, but might be useful in some later user applications.

It also has the iPhone 3.0 OS that was just recently released, so it now supports the advanced stereo Bluetooth headsets. Carmen has one for her Google phone, which I tested and it appears to work just fine.

The camera gets a nice upgrade to 3.2GS, and includes video capture, editing and upload to YouTube. That functionality all seems to work quite well (I’ll shoot some video shortly as well as some pictures as example). The camera also has autofocus, and can focus down to short distances. Both are nice improvements.

For me, the upgrade was a no-brainer really, and I’m quite pleased. I loved my old iPhone, and I love my new iPhone. The couple of gripes that I have are mostly with pricing. I was eligible for upgrading the phone for the $199 price (I got the 16gb model) which was good, but I ordered this through Apple which means I got hit with sales tax on the full price of the phone, resulting in a fifty something dollar sales tax. Ouch. And, of course AT&T slaps you with an $18 activation as well as an $18 upgrade fee, which seems like at least like they should waive one of those for customers who’ve been sending them substantial sums of money for the previous two years. So, it’s not cheap, but no smart phone is.

Revisiting Simon Singh’s Cipher Challenge…

The other day, my friend Jeff sent me an email detailing the latest benchmarking of his new 8 core Intel box. He had written a program to compute return rates for all possible draws in video poker. A few years ago, this program had taken a month of computer time to complete, and he wondered how how quickly it would run on his new box. The answer: around 12 hours.

This got me thinking back to my experience using Simon Singh’s “Cipher Challenge” that I did back in 2000. I hadn’t tried to solve Stage 9, because at the time it seemed a daunting task, requiring computational resources far in excess of what I had at the time. But Jeff’s email got me thinking, so I decided to run an experiment: how long would it really take?

I didn’t have a fast, optimized DES implementation of my own, so I decided to dig around. It turns out that OpenSSL contains an implementation of DES, and a few minutes of writing some code verified that it could actually decode the challenge message. So, the question was: how long would it take to break this code?

Stage 8 had revealed 8 of the 56 key bits, leaving a keyspace of 2^48 entries left (about 281 trillion entries). So, I coded up a small test program that did a million DES_set_key calls, followed by a decryption of the message. I found that it took about 21 microseconds to do a test. On average, we’ll search half the keyspace (around 140 trillion keys) before we find the key, so if you multiply it out, you get…. 93.65 years. We have eight cores, which brings it down to about 11.7 years. Not so good…

But here’s the thing: we probably don’t have to really decode the entire message. If we believe that the output is ASCII, then each of the output bytes should have the top bit clear. Any block which doesn’t have this feature indicates our key is on the wrong track. The odds of getting all those bits clear by random chance is one in 256. If we try to only decode the first six blocks, then our chance that we got something wrong is about one in 2^48th, which is just about the size of the keyspace, so we’d probably wouldn’t see very many false positives. If we modify the rule to just check the first six blocks, then it only takes about 1.16 microseconds to do a key set and a decode. Now my single machine can get the run time down to 236 days. Still pretty darned slow actually. It’s clear that openssl’s DES implementation isn’t really up to the task. I suspect that there are software implementations which are several times faster than this. I’ll try to dig one up and see what could really be done.

Addendum: When I got home, I dug up a copy of Eric Young’s libdes library, and ran some basic speed tests using the “speed” program that’s part of the distributions. I wasn’t running it on the same machine, so the numbers aren’t directly comparable, but my home machine quite a bit slower. Nevertheless, I got some interesting numbers:

[chessboard] % ./speed
Doing set_key for 10 seconds
29270676 set_key's in 10.00 seconds
Doing des_encrypt's for 10 seconds
54502334 des_encrypt's in 9.93 second
Doing des_cbc_encrypt on 1024 byte blocks for 10 seconds
402292 des_cbc_encrypt's of 1024 byte blocks in 10.00 second
Doing des_ede_cbc_encrypt on 1024 byte blocks for 10 seconds
146870 des_ede_cbc_encrypt's of 1024 byte blocks in 10.01 second
Doing crypt for 10 seconds
1731166 crypts in 9.92 second
set_key            per sec =   2927067.60 (    0.342uS)
DES raw ecb bytes  per sec =  43909231.82 (    0.182uS)
DES cbc bytes      per sec =  41194700.80 (    0.194uS)
DES ede cbc bytes  per sec =  15024463.54 (    0.532uS)
crypt              per sec =    174512.70 (    5.730uS)

If you add the set_key time to 48 times the raw ecb encode, you get about 9 microseconds. Using both of its two cores, that works out to about 20 years. That’s about 31 times slower, or nearly 8x slower per core.

No early iPhone joy in Mudville

The blogosphere was atwitter with the news that many iPhone 3GSs seemed to have shipped early, and indeed might be delivered early. I checked mine, and found that it had indeed arrived in Anchorage yesterday afternoon, but alas, checking it’s status today online met me with the following screen on UPS’s website:


So, it looks like mine will likely arrive on the 19th, just as they had originally claimed. Quel dommage.

NOAA Satellite Frequencies

I haven’t been goofing around much with receiving APT weather satellite data, but I was going to try to record some passes now that the days are longer and we get more daylight passes over North America. But I hadn’t programmed the frequencies into my radio, and was forced to look them up. So, here they are, all in one place, for future reference:

Satellite Frequency
NOAA 15 137.500 Mhz
NOAA 17 137.620 Mhz
NOAA 18 137.100 Mhz
NOAA 19 137.9125 Mhz

Matt Blaze: Security and Human Behavior 2009

For all the people who’ve come to see this as my ham radio blog, I apologize, but I do have other interests, and computer security is one of them. It’s not that I am any kind of expert, but I have played around quite a bit with various bits of computer security and cryptography over the years, and enjoy reading up on it. Recently a small interdisciplinary workshop was held at MIT on this subject, and Matt Blaze was kind enough to make recordings of the workshop. I’m loading these onto my iPhone (perhaps the last thing new it will see before my new iPhone 3GS arrives!) Haven’t checked the audio quality yet, but hopefully the sessions will be interesting…

Matt Blaze: Security and Human Behavior 2009