""" Adapted from http://javarng.googlecode.com/svn/trunk/com/modp/random/BlumBlumShub.java Original license follows:- Copyright 2005, Nick Galbreath -- nickg [at] modp [dot] com All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of the modp.com nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. This is the standard "new" BSD license: http://www.opensource.org/licenses/bsd-license.php """ import primes; import random; import sys; class BlumBlumShub(object): def getPrime(self, bits): """ Generate appropriate prime number for use in Blum-Blum-Shub. This generates the appropriate primes (p = 3 mod 4) needed to compute the "n-value" for Blum-Blum-Shub. bits - Number of bits in prime """ while True: p = primes.bigppr(bits); if p%4 == 3: break return p def generateN(self, bits): """ This generates the "n value" for use in the Blum-Blum-Shub algorithm. bits - The number of bits of security """ p = self.getPrime(bits/2) q = self.getPrime(bits/2) # make sure p != q (almost always true, but just in case, check) while p == q: q = getPrime(self, bits/2); # print "GenerateN - p = " + repr(p) + ", q = " + repr(q) return p * q; def __init__(self, bits): """ Constructor, specifing bits for n. bits - number of bits """ print "bits",bits self.n = self.generateN(bits) print "self.n",self.n # print "n set to " + repr(self.n) length = self.bitLen(self.n) seed = random.getrandbits(length) self.setSeed(seed) def setSeed(self, seed): """ Sets or resets the seed value and internal state. seed -The new seed """ self.state = seed % self.n def bitLen(self, x): " Get the bit lengh of a positive number" assert(x>0) q = 0 while x: q = q+1 x = x>>1 return q def next(self, numBits): "Returns up to numBit random bits" result = 0 for i in range(numBits,0,-1): self.state = (self.state**2) % self.n result = (result << 1) | (self.state&1) return result def sample(self, population, k): """Chooses k unique random elements from a population sequence. Returns a new list containing elements from the population while leaving the original population unchanged. The resulting list is in selection order so that all sub-slices will also be valid random samples. This allows raffle winners (the sample) to be partitioned into grand prize and second place winners (the subslices). Members of the population need not be hashable or unique. If the population contains repeats, then each occurrence is a possible selection in the sample. To choose a sample in a range of integers, use xrange as an argument. This is especially fast and space efficient for sampling from a large population: sample(xrange(10000000), 60) """ # Sampling without replacement entails tracking either potential # selections (the pool) in a list or previous selections in a set. # When the number of selections is small compared to the # population, then tracking selections is efficient, requiring # only a small set and an occasional reselection. For # a larger number of selections, the pool tracking method is # preferred since the list takes less space than the # set and it doesn't suffer from frequent reselections. n = len(population) if not 0 <= k <= n: raise ValueError("sample larger than population") def random() : return float(self.next())/9999999999 _int = int result = [None] * k setsize = 21 # size of a small set minus size of an empty list if k > 5: setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets if n <= setsize or hasattr(population, "keys"): # An n-length list is smaller than a k-length set, or this is a # mapping type so the other algorithm wouldn't work. pool = list(population) for i in xrange(k): # invariant: non-selected at [0,n-i) j = _int(random() * (n-i)) print j result[i] = pool[j] pool[j] = pool[n-i-1] # move non-selected item into vacancy else: try: selected = set() selected_add = selected.add for i in xrange(k): j = _int(random() * n) print j while j in selected: j = _int(random() * n) selected_add(j) result[i] = population[j] except (TypeError, KeyError): # handle (at least) sets if isinstance(population, list): raise return self.sample(tuple(population), k) return result def main(): bbs = BlumBlumShub(159); #print "Generating 10 numbers" for i in range (0,10): print bbs.next(159) #print bbs.sample(range(10),5) if __name__ == "__main__": main()