Blum Blum Shub 
[Oct. 23rd, 200810:42 am]
drostie

Ugh. I just found out that my Basic Stat Mech class is, in fact, only a halfsemester 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.')
In any case, I've implemented Whirlpool in Javascript, and am now turning to Blum Blum Shub. Javascript doesn't have a good longinteger type. In fact, Javascript doesn't have integers at all: numbers are always secretly stored as doubleprecision floating point numbers (52 bits of precision). To do Blum Blum Shub at its maximum speed, then, we would need x^2 to be less than 2^52. Hence x must be less than 2^26, hence pq must be less than 2^26, so we're looking at factoring a number that's around 64 million.
In other words, an efficient BlumBlumShub generator in Javascript *must* break up its numbers into arrays, because I can probably easily factor a 26bit number. I mean, the largest that my lookup table needs to be is sqrt( 2^{26} ) = 2^{13} = 8192, and there's only on the order of a thousand or so entries for that. I can create a script that does a thousand % operations. No problem.
Probably, my best bet is to break them up into 24bit 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 numbersystem base (10) minus 1  and all factors of B1 will have that property in base B arithmetic.
In particular, in 3bit octal arithmetic, 81 = 7 has that property; and in 4bit hexadecimal, 3 and 5 (factors of 161 = 15) has that property. In 12bit arithmetic, both of these conditions coincide. For example, the factors of 2^{12}  1 are: = 2^{12}  1 = 4095 = 3*3*5*7*13. (Just divide by 5 first, 9 second, and 7 third. Easy peasy.)
Since 2^{24}  1 = (2^{12}+1)(2^{12}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 17^{2}, 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 2^{24}1 = 3*3*5*7*13*17*241. If I divide my numbers into 24bit 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.
And the native data type of Javascript is large enough that I should be able to carry out the long multiplication algorithm inplace, since b1*b2 is never more than 48 bits, and I have 52 to work with. I don't know whether peculiarities occur when it transfers from integer mode to float mode, but I'll find that out when I implement it. 

