Friday, January 02, 2015

[itzdrlca] Square root as RNG

Take a random positive integer that is not a perfect square and calculate its square root to arbitrary precision in binary.  Use the fractional part (perhaps dropping an initial prefix) as a random number generator, a source of random bits.

The interesting observation is that this is not that impractical these days for up to billions or even trillions of bits.  (Though run time does grow faster than linearly.)  Arbitrary precision arithmetic algorithms have gotten quite good (perhaps inspired by efforts to calculate pi further and further).  Memory is cheap, as is disk for out-of-core huge multiplications.  Calculating square roots is much faster than pi.

Ideally start with a squarefree integer.  Is the best way to construct one to multiply a set of distinct random primes?  I'm guessing there is no efficient algorithm to test whether a given integer is square free.

Reciprocal of square root might be marginally faster to compute.

Is this source of random bits good for anything?  How good a source of randomness (pseudo of course) is it?  One worry is that its continued fraction is periodic.

Assume the initial integer is the product of some subset of (say) the first 256 prime numbers, so there are 2^256 possibilities.  Given sufficient bits of the fractional part of the square root (perhaps missing an initial prefix), how difficult is it to determine the initial integer, thereby making the entire rest of the stream predictable?  Probably easy: continued fraction.  Is there a way to process the bits to make discovering the key more difficult?  Perhaps sample the bits in an irregular pattern.  Compress the stream by a factor of 2 by XORing of pairs of bits.  Are there other arithmetic functions that are better than square root but as easily calculated?  AGM seems promising though much more time consuming, equivalent to the difficulty of pi.

There probably exist cryptographic stream ciphers which are much faster even at their most paranoid settings, and certainly don't encounter greater than linear computational effort nor greater than constant space to generate.

No comments :