|Blum Blum Shub
||[Oct. 23rd, 2008|10:42 am]
Ugh. I just found out that my Basic Stat Mech class is, in fact, only a half-semester class, and so I've got an exam next week to study for. So maybe my coding has to be put on hold. Blech.
Blum Blum Shub is a simple pseudorandom number generator: given two prime numbers p and q, and some random number x between, say, sqrt(pq) and pq, you just start squaring x, modulo pq. You usually just take one or two bits from the result, so that it's hard to find out subsequent numbers. And it has one magical property: *any* statistical attack on Blum Blum Shub is also a statistical attack on integer factorization. So if you can statistically predict Blum Blum Shub, you can also statistically predict how to factor N = pq. (Unfortunately, the proof of this fact is asymptotic, and so we don't even know what "small" means when we say, 'for small N, this proof might fail.')
Probably, my best bet is to break them up into 24-bit blocks, for some N. Why? Well, you probably know this trick for calculating whether a number is divisible by 3 or 9: add up all of the digits individually, then see if the result is divisible by 9. It turns out that this works because 9 is the number-system base (10) minus 1 -- and all factors of B-1 will have that property in base B arithmetic.
In particular, in 3-bit octal arithmetic, 8-1 = 7 has that property; and in 4-bit hexadecimal, 3 and 5 (factors of 16-1 = 15) has that property. In 12-bit arithmetic, both of these conditions coincide. For example, the factors of 212 - 1 are: = 212 - 1 = 4095 = 3*3*5*7*13. (Just divide by 5 first, 9 second, and 7 third. Easy peasy.)
Since 224 - 1 = (212+1)(212-1) = 4095 * 4097, and no prime factor of 4095 could divide 4097 (they're just too close together), we can quickly search for prime factors of 4097: we check 2 (easy no) and then 11 (another easy no) and finally 17 (harder, but 4097 = 17*241). And 241 is less than 172, so because it's not divisible by 2, 3, 5, 7, 11, or 13, it must also be prime. (You don't need to actually divide by any of those to see that, because, again, 4097 is too close to 4095.)
So 224-1 = 3*3*5*7*13*17*241. If I divide my numbers into 24-bit blocks, I can rapidly test for divisibility by 2 by checking the last bit, and I can sum the blocks together to test for divisibility by 3,5,7,13,17, and 241. That reduces my search space for primes to around 1/5 of its former size with almost no real effort.