Newsgroups: comp.security.misc,sci.crypt,alt.security
Path: news.io.com!news.tamu.edu!news.utdallas.edu!news.starnet.net!wupost!
+     howland.reston.ans.net!swrinde!gatech!news.sprintlink.net!demon!uknet!
+     strath-cs!info!aba
From: aba@dcs.exeter.ac.uk (Adam Back)

Subject: Re: Random Number Generators
In-Reply-To: peter@nmti.com's message of Wed, 31 May 1995 14:26:35 GMT
Message-ID: 
Sender: news@exeter.ac.uk (news admin)
Organization: Department of Computer Science, University of Exeter, U.K.
References: 
+           <1995May28.131614.4713@ullisys.pond.sub.org>
+           <3qfbkc$pnp@sol.ctr.columbia.edu> 
Date: Thu, 1 Jun 1995 14:46:49 GMT
Lines: 51
Xref: news.io.com comp.security.misc:17494 sci.crypt:38160 alt.security:25287


Peter da Silva  writes:
| Seth Robertson  writes:
| > Something like: ((double)seed) / ((double)(1<<27)) * 100000000.0
|
| But this will still produce a situation where some numbers are more
| likely than others, since you're still mapping between the same sets of
| integers.

Here's a method which I think solves this problem.  It uses integer
maths only which is safer anyway.  Given a uniformly distributed
random generator it should ensure uniform randomness where the range
generated by the random number generator is different to that
required.

Say we were using rand() producing numbers r,

        r in [0..2**32)

And we want to transform this into a random number in the range

        r' in [0..n)

Then you could calculate an integer scale factor S:

        S = int( 2**32 / n )

ie integer division of 2**32 / n

And take for use this algorithm to generate random numbers in [0..n)

  1)    x = rand();
  2)    x' = int( x / S );
  3)    if x' > n goto 1)

The generated number x' should be uniformly distributed in [0..n) if
x was uniformly distributed in [0..2**32)

If you want floating point just generate a bigger number and divide by
10**d where you want d digits after the point.

Adam
--
HAVE *YOU* EXPORTED A CRYPTO SYSTEM TODAY? --> http://dcs.ex.ac.uk/~aba/rsa/
--rsa--------------------------------8<-------------------------------------
#!/usr/local/bin/perl -s-- -export-a-crypto-system-sig -RSA-in-3-lines-PERL
($k,$n)=@ARGV;$m=unpack(H.$w,$m."\0"x$w),$_=`echo "16do$w 2+4Oi0$d*-^1[d2%
Sa2/d0