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 * 96,079
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.
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 <firstname.lastname@example.org> # 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: break else: return t raise FactorError("couldn't find a factor.") def factor(n): r =  while True: if isprime(n): r.append(n) break try: f = findfactor(n) r.append(f) n = n / f except FactorError, msg: r.append(n) break r.sort() 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, "") doit(2**98-1)
This is a fairly challenging factorization, and after a few seconds, it outputs:
316,912,650,057,057,350,374,175,801,343 = 3 43 127 4,363,953,127,297 4,432,676,798,593
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