1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.math.random;
18
19 import java.io.Serializable;
20 import java.security.MessageDigest;
21 import java.security.SecureRandom;
22 import java.security.NoSuchAlgorithmException;
23 import java.security.NoSuchProviderException;
24 import java.util.Collection;
25
26 /**
27 * Implements the {@link RandomData} interface using a {@link RandomGenerator}
28 * instance to generate non-secure data and a
29 * {@link java.security.SecureRandom} instance to provide data for the
30 * <code>nextSecureXxx</code> methods. If no <code>RandomGenerator</code>
31 * is provided in the constructor, the default is to use a generator based on
32 * {@link java.util.Random}. To plug in a different implementation,
33 * either implement <code>RandomGenerator</code> directly or extend
34 * {@link AbstractRandomGenerator}.
35 * <p>
36 * Supports reseeding the underlying pseudo-random number generator (PRNG).
37 * The <code>SecurityProvider</code> and <code>Algorithm</code>
38 * used by the <code>SecureRandom</code> instance can also be reset.
39 * <p>
40 * For details on the default PRNGs, see {@link java.util.Random} and
41 * {@link java.security.SecureRandom}.
42 * <p>
43 * <strong>Usage Notes</strong>: <ul>
44 * <li>
45 * Instance variables are used to maintain <code>RandomGenerator</code> and
46 * <code>SecureRandom</code> instances used in data generation. Therefore,
47 * to generate a random sequence of values or strings, you should use just
48 * <strong>one</strong> <code>RandomDataImpl</code> instance repeatedly.</li>
49 * <li>
50 * The "secure" methods are *much* slower. These should be used only when a
51 * cryptographically secure random sequence is required. A secure random
52 * sequence is a sequence of pseudo-random values which, in addition to being
53 * well-dispersed (so no subsequence of values is an any more likely than other
54 * subsequence of the the same length), also has the additional property that
55 * knowledge of values generated up to any point in the sequence does not make
56 * it any easier to predict subsequent values.</li>
57 * <li>
58 * When a new <code>RandomDataImpl</code> is created, the underlying random
59 * number generators are <strong>not</strong> intialized. If you do not
60 * explicitly seed the default non-secure generator, it is seeded with the current time
61 * in milliseconds on first use. The same holds for the secure generator.
62 * If you provide a <code>RandomGenerator</code> to the constructor, however,
63 * this generator is not reseeded by the constructor nor is it reseeded on
64 * first use. </li>
65 * <li>
66 * The <code>reSeed</code> and <code>reSeedSecure</code> methods delegate
67 * to the corresponding methods on the underlying <code>RandomGenerator</code>
68 * and<code>SecureRandom</code> instances. Therefore,
69 * <code>reSeed(long)</code> fully resets the initial state of the non-secure
70 * random number generator (so that reseeding with a specific value always
71 * results in the same subsequent random sequence); whereas reSeedSecure(long)
72 * does <strong>not</strong> reinitialize the secure random number generator
73 * (so secure sequences started with calls to reseedSecure(long) won't be
74 * identical).</li>
75 * <li>
76 * This implementation is not synchronized.
77 * </ul>
78 *
79 * @version $Revision: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $
80 */
81 public class RandomDataImpl implements RandomData, Serializable {
82
83 /** Serializable version identifier */
84 private static final long serialVersionUID = -626730818244969716L;
85
86 /** underlying random number generator */
87 private RandomGenerator rand = null;
88
89 /** underlying secure random number generator */
90 private SecureRandom secRand = null;
91
92 /**
93 * Construct a RandomDataImpl.
94 */
95 public RandomDataImpl() {
96 }
97
98 /**
99 * Construct a RandomDataImpl using the supplied {@link RandomGenerator}
100 * as the source of (non-secure) random data.
101 *
102 * @param rand the source of (non-secure) random data
103 * @since 1.1
104 */
105 public RandomDataImpl(RandomGenerator rand) {
106 super();
107 this.rand = rand;
108 }
109
110 /**
111 * <strong>Algorithm Description:</strong> hex strings are generated
112 * using a 2-step process. <ol>
113 * <li>
114 * len/2+1 binary bytes are generated using the underlying Random</li>
115 * <li>
116 * Each binary byte is translated into 2 hex digits</li></ol>
117 * @param len the desired string length.
118 * @return the random string.
119 */
120 public String nextHexString(int len) {
121 if (len <= 0) {
122 throw new IllegalArgumentException("length must be positive");
123 }
124
125
126 RandomGenerator ran = getRan();
127
128
129 StringBuffer outBuffer = new StringBuffer();
130
131
132 byte[] randomBytes = new byte[(len / 2) + 1];
133 ran.nextBytes(randomBytes);
134
135
136 for (int i = 0; i < randomBytes.length; i++) {
137 Integer c = new Integer(randomBytes[i]);
138
139
140
141
142
143
144 String hex = Integer.toHexString(c.intValue() + 128);
145
146
147 if (hex.length() == 1) {
148 hex = "0" + hex;
149 }
150 outBuffer.append(hex);
151 }
152 return outBuffer.toString().substring(0, len);
153 }
154
155 /**
156 * Generate a random int value uniformly distributed between
157 * <code>lower</code> and <code>upper</code>, inclusive.
158 *
159 * @param lower the lower bound.
160 * @param upper the upper bound.
161 * @return the random integer.
162 */
163 public int nextInt(int lower, int upper) {
164 if (lower >= upper) {
165 throw new IllegalArgumentException
166 ("upper bound must be > lower bound");
167 }
168 RandomGenerator rand = getRan();
169 return lower + (int) (rand.nextDouble() * (upper - lower + 1));
170 }
171
172 /**
173 * Generate a random long value uniformly distributed between
174 * <code>lower</code> and <code>upper</code>, inclusive.
175 *
176 * @param lower the lower bound.
177 * @param upper the upper bound.
178 * @return the random integer.
179 */
180 public long nextLong(long lower, long upper) {
181 if (lower >= upper) {
182 throw new IllegalArgumentException
183 ("upper bound must be > lower bound");
184 }
185 RandomGenerator rand = getRan();
186 return lower + (long) (rand.nextDouble() * (upper - lower + 1));
187 }
188
189 /**
190 * <strong>Algorithm Description:</strong> hex strings are generated in
191 * 40-byte segments using a 3-step process. <ol>
192 * <li>
193 * 20 random bytes are generated using the underlying
194 * <code>SecureRandom</code>.</li>
195 * <li>
196 * SHA-1 hash is applied to yield a 20-byte binary digest.</li>
197 * <li>
198 * Each byte of the binary digest is converted to 2 hex digits.</li></ol>
199 *
200 * @param len the length of the generated string
201 * @return the random string
202 */
203 public String nextSecureHexString(int len) {
204 if (len <= 0) {
205 throw new IllegalArgumentException("length must be positive");
206 }
207
208
209 SecureRandom secRan = getSecRan();
210 MessageDigest alg = null;
211 try {
212 alg = MessageDigest.getInstance("SHA-1");
213 } catch (NoSuchAlgorithmException ex) {
214 return null;
215 }
216 alg.reset();
217
218
219 int numIter = (len / 40) + 1;
220
221 StringBuffer outBuffer = new StringBuffer();
222 for (int iter = 1; iter < numIter + 1; iter++) {
223 byte[] randomBytes = new byte[40];
224 secRan.nextBytes(randomBytes);
225 alg.update(randomBytes);
226
227
228 byte hash[] = alg.digest();
229
230
231 for (int i = 0; i < hash.length; i++) {
232 Integer c = new Integer(hash[i]);
233
234
235
236
237
238
239 String hex = Integer.toHexString(c.intValue() + 128);
240
241
242 if (hex.length() == 1) {
243 hex = "0" + hex;
244 }
245 outBuffer.append(hex);
246 }
247 }
248 return outBuffer.toString().substring(0, len);
249 }
250
251 /**
252 * Generate a random int value uniformly distributed between
253 * <code>lower</code> and <code>upper</code>, inclusive. This algorithm
254 * uses a secure random number generator.
255 *
256 * @param lower the lower bound.
257 * @param upper the upper bound.
258 * @return the random integer.
259 */
260 public int nextSecureInt(int lower, int upper) {
261 if (lower >= upper) {
262 throw new IllegalArgumentException
263 ("lower bound must be < upper bound");
264 }
265 SecureRandom sec = getSecRan();
266 return lower + (int) (sec.nextDouble() * (upper - lower + 1));
267 }
268
269 /**
270 * Generate a random long value uniformly distributed between
271 * <code>lower</code> and <code>upper</code>, inclusive. This algorithm
272 * uses a secure random number generator.
273 *
274 * @param lower the lower bound.
275 * @param upper the upper bound.
276 * @return the random integer.
277 */
278 public long nextSecureLong(long lower, long upper) {
279 if (lower >= upper) {
280 throw new IllegalArgumentException
281 ("lower bound must be < upper bound");
282 }
283 SecureRandom sec = getSecRan();
284 return lower + (long) (sec.nextDouble() * (upper - lower + 1));
285 }
286
287 /**
288 * Generates a random long value from the Poisson distribution with the
289 * given mean.
290 * <p>
291 * <strong>Algorithm Description</strong>:
292 * Uses simulation of a Poisson process using Uniform deviates, as
293 * described
294 * <a href="http://irmi.epfl.ch/cmos/Pmmi/interactive/rng7.htm">
295 * here.</a>
296 * <p>
297 * The Poisson process (and hence value returned) is bounded by
298 * 1000 * mean.
299 *
300 * @param mean mean of the Poisson distribution.
301 * @return the random Poisson value.
302 */
303 public long nextPoisson(double mean) {
304 if (mean <= 0) {
305 throw new IllegalArgumentException("Poisson mean must be > 0");
306 }
307 double p = Math.exp(-mean);
308 long n = 0;
309 double r = 1.0d;
310 double rnd = 1.0d;
311 RandomGenerator rand = getRan();
312 while (n < 1000 * mean) {
313 rnd = rand.nextDouble();
314 r = r * rnd;
315 if (r >= p) {
316 n++;
317 } else {
318 return n;
319 }
320 }
321 return n;
322 }
323
324 /**
325 * Generate a random value from a Normal (a.k.a. Gaussian) distribution
326 * with the given mean, <code>mu</code> and the given standard deviation,
327 * <code>sigma</code>.
328 *
329 * @param mu the mean of the distribution
330 * @param sigma the standard deviation of the distribution
331 * @return the random Normal value
332 */
333 public double nextGaussian(double mu, double sigma) {
334 if (sigma <= 0) {
335 throw new IllegalArgumentException("Gaussian std dev must be > 0");
336 }
337 RandomGenerator rand = getRan();
338 return sigma * rand.nextGaussian() + mu;
339 }
340
341 /**
342 * Returns a random value from an Exponential distribution with the given
343 * mean.
344 * <p>
345 * <strong>Algorithm Description</strong>: Uses the
346 * <a href="http://www.jesus.ox.ac.uk/~clifford/a5/chap1/node5.html">
347 * Inversion Method</a> to generate exponentially distributed random values
348 * from uniform deviates.
349 *
350 * @param mean the mean of the distribution
351 * @return the random Exponential value
352 */
353 public double nextExponential(double mean) {
354 if (mean < 0.0) {
355 throw new IllegalArgumentException
356 ("Exponential mean must be >= 0");
357 }
358 RandomGenerator rand = getRan();
359 double unif = rand.nextDouble();
360 while (unif == 0.0d) {
361 unif = rand.nextDouble();
362 }
363 return -mean * Math.log(unif);
364 }
365
366 /**
367 * <strong>Algorithm Description</strong>: scales the output of
368 * Random.nextDouble(), but rejects 0 values (i.e., will generate another
369 * random double if Random.nextDouble() returns 0).
370 * This is necessary to provide a symmetric output interval
371 * (both endpoints excluded).
372 *
373 * @param lower the lower bound.
374 * @param upper the upper bound.
375 * @return a uniformly distributed random value from the interval (lower, upper)
376 */
377 public double nextUniform(double lower, double upper) {
378 if (lower >= upper) {
379 throw new IllegalArgumentException
380 ("lower bound must be <= upper bound");
381 }
382 RandomGenerator rand = getRan();
383
384
385 double u = rand.nextDouble();
386 while(u <= 0.0){
387 u = rand.nextDouble();
388 }
389
390 return lower + u * (upper - lower);
391 }
392
393 /**
394 * Returns the RandomGenerator used to generate non-secure
395 * random data.
396 * <p>
397 * Creates and initializes a default generator if null.
398 *
399 * @return the Random used to generate random data
400 * @since 1.1
401 */
402 private RandomGenerator getRan() {
403 if (rand == null) {
404 rand = new JDKRandomGenerator();
405 rand.setSeed(System.currentTimeMillis());
406 }
407 return rand;
408 }
409
410 /**
411 * Returns the SecureRandom used to generate secure random data.
412 * <p>
413 * Creates and initializes if null.
414 *
415 * @return the SecureRandom used to generate secure random data
416 */
417 private SecureRandom getSecRan() {
418 if (secRand == null) {
419 secRand = new SecureRandom();
420 secRand.setSeed(System.currentTimeMillis());
421 }
422 return secRand;
423 }
424
425 /**
426 * Reseeds the random number generator with the supplied seed.
427 * <p>
428 * Will create and initialize if null.
429 *
430 * @param seed the seed value to use
431 */
432 public void reSeed(long seed) {
433 if (rand == null) {
434 rand = new JDKRandomGenerator();
435 }
436 rand.setSeed(seed);
437 }
438
439 /**
440 * Reseeds the secure random number generator with the current time
441 * in milliseconds.
442 * <p>
443 * Will create and initialize if null.
444 */
445 public void reSeedSecure() {
446 if (secRand == null) {
447 secRand = new SecureRandom();
448 }
449 secRand.setSeed(System.currentTimeMillis());
450 }
451
452 /**
453 * Reseeds the secure random number generator with the supplied seed.
454 * <p>
455 * Will create and initialize if null.
456 *
457 * @param seed the seed value to use
458 */
459 public void reSeedSecure(long seed) {
460 if (secRand == null) {
461 secRand = new SecureRandom();
462 }
463 secRand.setSeed(seed);
464 }
465
466 /**
467 * Reseeds the random number generator with the current time
468 * in milliseconds.
469 */
470 public void reSeed() {
471 if (rand == null) {
472 rand = new JDKRandomGenerator();
473 }
474 rand.setSeed(System.currentTimeMillis());
475 }
476
477 /**
478 * Sets the PRNG algorithm for the underlying SecureRandom instance
479 * using the Security Provider API. The Security Provider API is defined in
480 * <a href="http://java.sun.com/j2se/1.3/docs/guide/security/CryptoSpec.html#AppA">
481 * Java Cryptography Architecture API Specification & Reference.</a>
482 * <p>
483 * <strong>USAGE NOTE:</strong> This method carries <i>significant</i>
484 * overhead and may take several seconds to execute.
485 * </p>
486 *
487 * @param algorithm the name of the PRNG algorithm
488 * @param provider the name of the provider
489 * @throws NoSuchAlgorithmException if the specified algorithm
490 * is not available
491 * @throws NoSuchProviderException if the specified provider
492 * is not installed
493 */
494 public void setSecureAlgorithm(String algorithm, String provider)
495 throws NoSuchAlgorithmException, NoSuchProviderException {
496 secRand = SecureRandom.getInstance(algorithm, provider);
497 }
498
499 /**
500 * Uses a 2-cycle permutation shuffle to generate a random permutation.
501 * The shuffling process is described
502 * <a href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html">
503 * here</a>.
504 * @param n the population size.
505 * @param k the number to choose.
506 * @return the random permutation.
507 */
508 public int[] nextPermutation(int n, int k) {
509 if (k > n) {
510 throw new IllegalArgumentException
511 ("permutation k exceeds n");
512 }
513 if (k == 0) {
514 throw new IllegalArgumentException
515 ("permutation k must be > 0");
516 }
517
518 int[] index = getNatural(n);
519 shuffle(index, n - k);
520 int[] result = new int[k];
521 for (int i = 0; i < k; i++) {
522 result[i] = index[n - i - 1];
523 }
524
525 return result;
526 }
527
528 /**
529 * Uses a 2-cycle permutation shuffle to generate a random permutation.
530 * <strong>Algorithm Description</strong>: Uses a 2-cycle permutation
531 * shuffle to generate a random permutation of <code>c.size()</code> and
532 * then returns the elements whose indexes correspond to the elements of
533 * the generated permutation.
534 * This technique is described, and proven to generate random samples,
535 * <a href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html">
536 * here</a>
537 * @param c Collection to sample from.
538 * @param k sample size.
539 * @return the random sample.
540 */
541 public Object[] nextSample(Collection c, int k) {
542 int len = c.size();
543 if (k > len) {
544 throw new IllegalArgumentException
545 ("sample size exceeds collection size");
546 }
547 if (k == 0) {
548 throw new IllegalArgumentException
549 ("sample size must be > 0");
550 }
551
552 Object[] objects = c.toArray();
553 int[] index = nextPermutation(len, k);
554 Object[] result = new Object[k];
555 for (int i = 0; i < k; i++) {
556 result[i] = objects[index[i]];
557 }
558 return result;
559 }
560
561
562
563 /**
564 * Uses a 2-cycle permutation shuffle to randomly re-order the last elements
565 * of list.
566 *
567 * @param list list to be shuffled
568 * @param end element past which shuffling begins
569 */
570 private void shuffle(int[] list, int end) {
571 int target = 0;
572 for (int i = list.length - 1 ; i >= end; i--) {
573 if (i == 0) {
574 target = 0;
575 } else {
576 target = nextInt(0, i);
577 }
578 int temp = list[target];
579 list[target] = list[i];
580 list[i] = temp;
581 }
582 }
583
584 /**
585 * Returns an array representing n.
586 *
587 * @param n the natural number to represent
588 * @return array with entries = elements of n
589 */
590 private int[] getNatural(int n) {
591 int[] natural = new int[n];
592 for (int i = 0; i < n; i++) {
593 natural[i] = i;
594 }
595 return natural;
596 }
597 }