# Copyright (C) 2001 Christopher Craig # # This program is free software; you can redistribute it and/or # modify it under the terms of the GNU General Public License # as published by the Free Software Foundation; either version 2 # of the License, or (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program; if not, write to the Free Software # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. # """ This module is mostly compatible with the Python's random module, but uses Linux or BSD's /dev/urandom device to generate numbers, thus yielding more random output than the default Python module. Incompatibilities are as follows: getstate, setstate, jumpahead : Because the core entropy generator is a stateless random number generator and not a pseudo-random number generator these are not supported. They will raise an exception if they are run. randrange, randint : This module was intended to be used for cryptography so the 32 bit range limit on the default randrange was not sufficient. These functions have been modified to return longints and support the full range of the longint type if Bos' real.py module is installed. If real.py is not installed and the range of the function exceeds the maximum float, these functions will fail without notice. randrange is probabilistic and does not guarantee a return (though it has a greater than 1-(1/2**n) chance of returning within n attempts). See the doc string of randrange for more information. a setmode function was added accepting the values "strong" or "secure". See doc string for details. """ __version__ = "$Revision: 1.2 $" import sys import random try: from real import log # use the real module if it exists except ImportError: from math import log # else use math RandomError="ccRandomError" class Random(random.Random): def __init__(self, mode="strong"): self.file = None self.setmode(mode) def setmode(self, newmode): """ sets the mode to either "strong" or "secure" "strong" (default) will use a fill requests even if it runs out of entropy in the entropy pool. This can theoretically be compromised (though no attack is known) "secure" will return only bytes within the estimated entropy of the entropy pool. This means that even if the algorithm is broken in theory the number generator cannot be compromised. This has the major drawback that it will block indefinately if there is insufficient entropy. """ if self.file: self.file.close() if newmode=="secure": self.file=open("/dev/random") self.mode="secure" elif newmode=="strong": self.file=open("/dev/urandom") self.mode="strong" else: raise RandomError, "Incorrect arguments" def randrange(self, start, stop=None, step=1): """randrange(start, stop=None, step=1) -> long Choose a random item from range(start, stop[, step]). Follows randrange from the default random module fairly closely. Differs mainly in that it allows for long integers and guarantees no loss of entropy from entropy source. (The default gets its entropy from a call to random() which only allows for 52bits of entropy) If Jurjen N.E. Bos's "real" module is not installed, then large spans (where the size of the range is greater than the maximum floating point value on this machine) will fail without notice. ------------------------ Notes on non-determinism ------------------------ The point of this generator was to have something to build my large random keys for cryptosystems, which meant that I wanted probability of any integer in the specified range to be _exactly_ the same as any other integer. This meant that I could not use a normal mapping function to get my random numbers because that would make some integers more probable than others. A simple example of this would be to try to map the set range(8) into the set range(5), but it holds true for mapping 2**52 (the size of the significand on a double precision float) to any number that does not divide 2**52. My solution to this was to drop the most signicant bits down to the minimum bit space that could contain the requested range and then discard all generated numbers that were greater than the requested range. This means that this function isn't guaranteed to stop, but it has a probability greater than 1-(1/2**n) of returning before having to generate n integers. (Ignoring negligable rounding errors in exceptionally large ranges) """ if stop==None: stop = start start = 0 if step > 0: size = (stop - start + step - 1) / step elif step < 0: size = (stop - start + step + 1) / step else: ValueError, "zero step for randrange()" if size <= 0: raise ValueError, "empty range for randrange()" numbits = long(log(size)/log(2))+1 # the +1 is for rounding errors numbytes, t = divmod(numbits, 8) bitshift = -t % 8 if t: numbytes += 1 while 1: rval = 0L data = self.randbytes(numbytes) for byte in data: rval = (rval << 8) + ord(byte) rval >>= bitshift if rval < size: break return start + step*rval def random(self): """random() -> float returns a random float on the interval [0,1) """ # IEEE double precision floats have 6 bytes of precision, # so to be sure this uses 12 data = self.randbytes(12) rval = 0.0 for byte in data: rval = (rval / 256) + ord(byte) return rval / 256 def choice(self, seq): """choice(seq) -> choice returns a random element from the sequence """ return seq[self.randrange(len(seq))] def shuffle(self, x): """x, random=random.random -> shuffle list x in place; return None. Optional arg random is a 0-argument function returning a random float in [0.0, 1.0); by default, the standard random.random. Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that "most" permutations of a long sequence can never be generated. """ for i in xrange(len(x)-1, 0, -1): # pick an element in x[:i+1] with which to exchange x[i] j = randrange(i+1) x[i], x[j] = x[j], x[i] def randbytes(self, n): """rand(n) -> string returns n random bytes """ return self.file.read(n) #------- Do nothing functions -------- # these functions are included only to maintain compatibility with # random def seed(self, a): return def setstate(self, state): raise RandomError, "ccrandom does not support state setting" def getstate(self): raise RandomError, "ccrandom does not support state setting" def jumpahead(self, n): raise RandomError, "ccrandom does not support state setting" __all__ = ["Random","setmode","seed","random","uniform","randint","choice", "randrange","shuffle","normalvariate","lognormvariate", "cunifvariate","expovariate","vonmisesvariate","gammavariate", "stdgamma","gauss","betavariate","paretovariate","weibullvariate", "getstate","setstate","jumpahead"] _inst = Random() seed = _inst.seed random = _inst.random uniform = _inst.uniform randint = _inst.randint choice = _inst.choice randrange = _inst.randrange shuffle = _inst.shuffle normalvariate = _inst.normalvariate lognormvariate = _inst.lognormvariate cunifvariate = _inst.cunifvariate expovariate = _inst.expovariate vonmisesvariate = _inst.vonmisesvariate gammavariate = _inst.gammavariate stdgamma = _inst.stdgamma gauss = _inst.gauss betavariate = _inst.betavariate paretovariate = _inst.paretovariate weibullvariate = _inst.weibullvariate getstate = _inst.getstate setstate = _inst.setstate jumpahead = _inst.jumpahead setmode = _inst.setmode