Factoring Numbers in a Computer Lab
Eric Lengyel • May 2, 2021
This is a short story from my college years. It was originally posted on Twitter.
Back in 1993, I was taking a number theory class, and there was a semester-long factorization contest that we could participate in. I implemented a distributed multiple polynomial quadratic sieve (MPQS) for the Mac, and I needed a cluster of computers to run it on. The computer lab in the math building had a bunch of Mac Centris 650s on an AppleTalk network. But they were running software called At Ease that secured the computer and didn’t give you access to the Finder, only specific software, so I couldn’t just pop in a disk and run my own programs.
You can see in this picture that the Centris had two little buttons on the front. One was a reset button, and the other generated a non-maskable interrupt (NMI). If Macsbug was installed, the NMI button froze everything and dropped you into the system debugger. If no debugger was installed, then the NMI button brought up a small system monitor window. It was extremely basic and didn’t do much more than let you look at raw memory and, importantly, let you poke new byte values into memory at arbitrary addresses.
On my own computer, I wrote a tiny program that would display the system file picker and execute whatever file was chosen. I printed out the machine code for that program and brought it with me to the lab. It was only a few dozen 8-bit hex values. I could enter that program in the system monitor, but I needed a way to run it. For reasons I don’t entirely remember, using the G command for “go” in the monitor ended up crashing the machine, so it wasn’t an option.
The Mac had several hooks (function pointers) at fixed low-memory addresses that were documented in Inside Macintosh, Apple’s set of official programming manuals. One of them was a callback that would be repeatedly invoked as the user was dragging something in the GUI. So I put my program’s address into that hook, exited the monitor, and dragged a scroll bar indicator somewhere. Bam! The system file picker appears. I navigate to the Finder program, select it, and click Open. The Finder launches, and I now have full access to the computer.
I repeated this on about 15 computers and loaded my MPQS program on each of them. About half the lab was now running a distributed factorization algorithm controlled by a central host over the network, and the whole thing actually got results! On these computers, I could factor a general number with around 70 decimal digits in a reasonable amount of time (like overnight). And yes, I won the contest.
I’d like to clarify that my code was running only on machines that were otherwise idle. Not many people were in the lab late in the evenings. MPQS processing nodes could be added and removed dynamically, so if somebody needed a computer that was part of my cluster, they could just quit my program and everything would go back to normal. Also, once the number theory professor learned of what I had implemented, he worked out an agreement with the lab manager to give me legitimate access to the machines. :)
See Also
- Hacker News thread about this post.