aboutsummaryrefslogtreecommitdiff
path: root/src/Java/gtPlusPlus/api/objects/random
diff options
context:
space:
mode:
Diffstat (limited to 'src/Java/gtPlusPlus/api/objects/random')
-rw-r--r--src/Java/gtPlusPlus/api/objects/random/CSPRNG_DO_NOT_USE.java271
-rw-r--r--src/Java/gtPlusPlus/api/objects/random/XSTR.java266
2 files changed, 537 insertions, 0 deletions
diff --git a/src/Java/gtPlusPlus/api/objects/random/CSPRNG_DO_NOT_USE.java b/src/Java/gtPlusPlus/api/objects/random/CSPRNG_DO_NOT_USE.java
new file mode 100644
index 0000000000..b2dc984456
--- /dev/null
+++ b/src/Java/gtPlusPlus/api/objects/random/CSPRNG_DO_NOT_USE.java
@@ -0,0 +1,271 @@
+/*
+ * 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
+ */
+
+package gtPlusPlus.api.objects.random;
+import java.math.BigInteger;
+import java.security.SecureRandom;
+import java.util.Random;
+
+import gtPlusPlus.api.interfaces.IRandomGenerator;
+import gtPlusPlus.core.util.Utils;
+
+/**
+ * The Blum-Blum-Shub random number generator.
+ *
+ * <p>
+ * The Blum-Blum-Shub is a "cryptographically secure" random number
+ * generator. It has been proven that predicting the ouput
+ * is equivalent to factoring <i>n</i>, a large integer generated
+ * from two prime numbers.
+ * </p>
+ *
+ * <p>
+ * The Algorithm:
+ * </p>
+ * <ol>
+ * <li>
+ * (setup) generate two secret prime numbers <i>p</i>, <i>q</i> such that
+ * <i>p</i> &ne; <i>q</i>, <i>p</i> &equiv; 3 mod 4, <i>q</i> &equiv; 3 mod 4.
+ * </li>
+ * <li> (setup) compute <i>n</i> = <i>pq</i>. <i>n</i> can be re-used, but
+ * <i>p</i>, and <i>q</i> are secret and should be disposed of.</li>
+ * <li> Generate a (secure) random seed <i>s</i> in the range [1, <i>n</i> -1]
+ * such that gcd(<i>s</i>, <i>n</i>) = 1.
+ * <li> Compute <i>x</i> = <i>s</i><sup>2</sup> mod <i>n</i></li>
+ * <li> Compute a single random bit with:
+ * <ol>
+ * <li> <i>x</i> = <i>x</i><sup>2</sup> mod <i>n</i></li>
+ * <li> return Least-Significant-Bit(<i>x</i>) (i.e. <i>x</i> & 1)</li>
+ * </ol>
+ * Repeat as necessary.
+ * </li>
+ * </ol>
+ *
+ * <p>
+ * The code originally appeared in <a href="http://modp.com/cida/"><i>Cryptography for
+ * Internet and Database Applications </i>, Chapter 4, pages 174-177</a>
+ * </p>
+ * <p>
+ * More details are in the <a href="http://www.cacr.math.uwaterloo.ca/hac/"><i>Handbook of Applied Cryptography</i></a>,
+ * <a href="http://www.cacr.math.uwaterloo.ca/hac/about/chap5.pdf">Section 5.5.2</a>
+ * </p>
+ *
+ * @author Nick Galbreath -- nickg [at] modp [dot] com
+ * @version 3 -- 06-Jul-2005
+ *
+ */
+public class CSPRNG_DO_NOT_USE extends Random implements IRandomGenerator {
+
+ // pre-compute a few values
+ private static final BigInteger two = BigInteger.valueOf(2L);
+
+ private static final BigInteger three = BigInteger.valueOf(3L);
+
+ private static final BigInteger four = BigInteger.valueOf(4L);
+
+ /**
+ * main parameter
+ */
+ private BigInteger n;
+
+ private BigInteger state;
+
+ /**
+ * 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.
+ *
+ * @param bits Number of bits in prime
+ * @param rand A source of randomness
+ */
+ private static BigInteger getPrime(int bits, Random rand) {
+ BigInteger p;
+ while (true) {
+ p = new BigInteger(bits, 100, rand);
+ if (p.mod(four).equals(three))
+ break;
+ }
+ return p;
+ }
+
+ /**
+ * This generates the "n value" -- the multiplication of two equally sized
+ * random prime numbers -- for use in the Blum-Blum-Shub algorithm.
+ *
+ * @param bits
+ * The number of bits of security
+ * @param rand
+ * A random instance to aid in generating primes
+ * @return A BigInteger, the <i>n</i>.
+ */
+ public static BigInteger generateN(int bits, Random rand) {
+ BigInteger p = getPrime(bits/2, rand);
+ BigInteger q = getPrime(bits/2, rand);
+
+ // make sure p != q (almost always true, but just in case, check)
+ while (p.equals(q)) {
+ q = getPrime(bits, rand);
+ }
+ return p.multiply(q);
+ }
+
+ /**
+ * Constructor, specifing bits for <i>n</i>
+ *
+ * @param bits number of bits
+ */
+ public CSPRNG_DO_NOT_USE(int bits) {
+ this(bits, new Random());
+ }
+
+ /**
+ * Constructor, generates prime and seed
+ *
+ * @param bits
+ * @param rand
+ */
+ public CSPRNG_DO_NOT_USE(int bits, Random rand) {
+ this(generateN(bits, rand));
+ }
+
+ /**
+ * A constructor to specify the "n-value" to the Blum-Blum-Shub algorithm.
+ * The inital seed is computed using Java's internal "true" random number
+ * generator.
+ *
+ * @param n
+ * The n-value.
+ */
+ public CSPRNG_DO_NOT_USE(BigInteger n) {
+ this(n, SecureRandom.getSeed(n.bitLength() / 8));
+ }
+
+ /**
+ * A constructor to specify both the n-value and the seed to the
+ * Blum-Blum-Shub algorithm.
+ *
+ * @param n
+ * The n-value using a BigInteger
+ * @param seed
+ * The seed value using a byte[] array.
+ */
+ public CSPRNG_DO_NOT_USE(BigInteger n, byte[] seed) {
+ this.n = n;
+ setSeed(seed);
+ }
+
+ /**
+ * Sets or resets the seed value and internal state
+ *
+ * @param seedBytes
+ * The new seed.
+ */
+ public void setSeed(byte[] seedBytes) {
+ // ADD: use hardwired default for n
+ BigInteger seed = new BigInteger(1, seedBytes);
+ state = seed.mod(n);
+ }
+
+ /**
+ * Returns up to numBit random bits
+ *
+ * @return int
+ */
+ @Override
+ public int next(int numBits) {
+ // TODO: find out how many LSB one can extract per cycle.
+ // it is more than one.
+ int result = 0;
+ for (int i = numBits; i != 0; --i) {
+ state = state.modPow(two, n);
+ result = (result << 1) | (state.testBit(0) == true ? 1 : 0);
+ }
+ return result;
+ }
+
+
+ public static CSPRNG_DO_NOT_USE generate(){
+ return generate(512);
+ }
+
+ /**
+ * @return CSPRNG_DO_NOT_USE
+ * @Author Draknyte1/Alkalus
+ */
+ public static CSPRNG_DO_NOT_USE generate(int bitsize){
+ // First use the internal, stock "true" random number
+ // generator to get a "true random seed"
+ SecureRandom r = Utils.generateSecureRandom();
+ r.nextInt(); // need to do something for SR to be triggered.
+ // Use this seed to generate a n-value for Blum-Blum-Shub
+ // This value can be re-used if desired.
+ BigInteger nval = CSPRNG_DO_NOT_USE.generateN(bitsize, r);
+ // now get a seed
+ byte[] seed = new byte[bitsize/8];
+ r.nextBytes(seed);
+ // now create an instance of BlumBlumShub
+ CSPRNG_DO_NOT_USE bbs = new CSPRNG_DO_NOT_USE(nval, seed);
+ return bbs;
+ }
+
+
+ /**
+ * @return CSPRNG_DO_NOT_USE
+ * @Author Draknyte1/Alkalus
+ */
+ public static CSPRNG_DO_NOT_USE generate(Random aRandom){
+ return generate(512, aRandom);
+ }
+
+ /**
+ * @return CSPRNG_DO_NOT_USE
+ * @Author Draknyte1/Alkalus
+ */
+ public static CSPRNG_DO_NOT_USE generate(int aBitSize, Random aRandom){
+ // First use the internal, stock "true" random number
+ // generator to get a "true random seed"
+ SecureRandom r = Utils.generateSecureRandom();
+ r.nextInt(); // need to do something for SR to be triggered.
+ // Use this seed to generate a n-value for Blum-Blum-Shub
+ // This value can be re-used if desired.
+ int bitsize = aBitSize;
+ // now create an instance of BlumBlumShub
+ // do everything almost automatically
+ CSPRNG_DO_NOT_USE bbs = new CSPRNG_DO_NOT_USE(bitsize, aRandom);
+ return bbs;
+ }
+
+}
diff --git a/src/Java/gtPlusPlus/api/objects/random/XSTR.java b/src/Java/gtPlusPlus/api/objects/random/XSTR.java
new file mode 100644
index 0000000000..7f83df52c4
--- /dev/null
+++ b/src/Java/gtPlusPlus/api/objects/random/XSTR.java
@@ -0,0 +1,266 @@
+package gtPlusPlus.api.objects.random;
+/**
+ * A subclass of java.util.random that implements the Xorshift random number
+ * generator
+ *
+ * - it is 30% faster than the generator from Java's library - it produces
+ * random sequences of higher quality than java.util.Random - this class also
+ * provides a clone() function
+ *
+ * Usage: XSRandom rand = new XSRandom(); //Instantiation x = rand.nextInt();
+ * //pull a random number
+ *
+ * To use the class in legacy code, you may also instantiate an XSRandom object
+ * and assign it to a java.util.Random object: java.util.Random rand = new
+ * XSRandom();
+ *
+ * for an explanation of the algorithm, see
+ * http://demesos.blogspot.com/2011/09/pseudo-random-number-generators.html
+ *
+ * @author Wilfried Elmenreich University of Klagenfurt/Lakeside Labs
+ * http://www.elmenreich.tk
+ *
+ * This code is released under the GNU Lesser General Public License Version 3
+ * http://www.gnu.org/licenses/lgpl-3.0.txt
+ */
+
+import java.util.Random;
+import java.util.concurrent.atomic.AtomicLong;
+
+/**
+ * XSTR - Xorshift ThermiteRandom
+ * Modified by Bogdan-G
+ * 03.06.2016
+ * version 0.0.4
+ */
+public class XSTR extends Random {
+
+ private static final long serialVersionUID = 6208727693524452904L;
+ private long seed;
+ private long last;
+ private static final long GAMMA = 0x9e3779b97f4a7c15L;
+ private static final int PROBE_INCREMENT = 0x9e3779b9;
+ private static final long SEEDER_INCREMENT = 0xbb67ae8584caa73bL;
+ private static final double DOUBLE_UNIT = 0x1.0p-53; // 1.0 / (1L << 53)
+ private static final float FLOAT_UNIT = 0x1.0p-24f; // 1.0f / (1 << 24)
+
+ /*
+ MODIFIED BY: Robotia
+ Modification: Implemented Random class seed generator
+ */
+ /**
+ * Creates a new pseudo random number generator. The seed is initialized to
+ * the current time, as if by
+ * <code>setSeed(System.currentTimeMillis());</code>.
+ */
+ public XSTR() {
+ this(seedUniquifier() ^ System.nanoTime());
+ }
+ private static final AtomicLong seedUniquifier
+ = new AtomicLong(8682522807148012L);
+
+ private static long seedUniquifier() {
+ // L'Ecuyer, "Tables of Linear Congruential Generators of
+ // Different Sizes and Good Lattice Structure", 1999
+ for (;;) {
+ final long current = seedUniquifier.get();
+ final long next = current * 181783497276652981L;
+ if (seedUniquifier.compareAndSet(current, next)) {
+ return next;
+ }
+ }
+ }
+
+ /**
+ * Creates a new pseudo random number generator, starting with the specified
+ * seed, using <code>setSeed(seed);</code>.
+ *
+ * @param seed the initial seed
+ */
+ public XSTR(final long seed) {
+ this.seed = seed;
+ }
+ @Override
+ public boolean nextBoolean() {
+ return this.next(1) != 0;
+ }
+
+ @Override
+ public double nextDouble() {
+ return (((long)(this.next(26)) << 27) + this.next(27)) * DOUBLE_UNIT;
+ }
+ /**
+ * Returns the current state of the seed, can be used to clone the object
+ *
+ * @return the current seed
+ */
+ public synchronized long getSeed() {
+ return this.seed;
+ }
+
+ /**
+ * Sets the seed for this pseudo random number generator. As described
+ * above, two instances of the same random class, starting with the same
+ * seed, produce the same results, if the same methods are called.
+ *
+ * @param seed the new seed
+ */
+ @Override
+ public synchronized void setSeed(final long seed) {
+ this.seed = seed;
+ }
+
+ /**
+ * @return Returns an XSRandom object with the same state as the original
+ */
+ @Override
+ public XSTR clone() {
+ return new XSTR(this.getSeed());
+ }
+
+ /**
+ * Implementation of George Marsaglia's elegant Xorshift random generator
+ * 30% faster and better quality than the built-in java.util.random see also
+ * see http://www.javamex.com/tutorials/random_numbers/xorshift.shtml
+ *
+ * @param nbits
+ * @return
+ */
+ @Override
+ public int next(final int nbits) {
+ long x = this.seed;
+ x ^= (x << 21);
+ x ^= (x >>> 35);
+ x ^= (x << 4);
+ this.seed = x;
+ x &= ((1L << nbits) - 1);
+ return (int) x;
+ }
+ boolean haveNextNextGaussian = false;
+ double nextNextGaussian = 0;
+ @Override
+ synchronized public double nextGaussian() {
+ // See Knuth, ACP, Section 3.4.1 Algorithm C.
+ if (this.haveNextNextGaussian) {
+ this.haveNextNextGaussian = false;
+ return this.nextNextGaussian;
+ }
+ double v1, v2, s;
+ do {
+ v1 = (2 * this.nextDouble()) - 1; // between -1 and 1
+ v2 = (2 * this.nextDouble()) - 1; // between -1 and 1
+ s = (v1 * v1) + (v2 * v2);
+ } while ((s >= 1) || (s == 0));
+ final double multiplier = StrictMath.sqrt((-2 * StrictMath.log(s))/s);
+ this.nextNextGaussian = v2 * multiplier;
+ this.haveNextNextGaussian = true;
+ return v1 * multiplier;
+ }
+ /**
+ * Returns a pseudorandom, uniformly distributed {@code int} value between 0
+ * (inclusive) and the specified value (exclusive), drawn from this random
+ * number generator's sequence. The general contract of {@code nextInt} is
+ * that one {@code int} value in the specified range is pseudorandomly
+ * generated and returned. All {@code bound} possible {@code int} values are
+ * produced with (approximately) equal probability. The method
+ * {@code nextInt(int bound)} is implemented by class {@code Random} as if
+ * by:
+ * <pre> {@code
+ * public int nextInt(int bound) {
+ * if (bound <= 0)
+ * throw new IllegalArgumentException("bound must be positive");
+ *
+ * if ((bound & -bound) == bound) // i.e., bound is a power of 2
+ * return (int)((bound * (long)next(31)) >> 31);
+ *
+ * int bits, val;
+ * do {
+ * bits = next(31);
+ * val = bits % bound;
+ * } while (bits - val + (bound-1) < 0);
+ * return val;
+ * }}</pre>
+ *
+ * <p>The hedge "approx
+ * imately" is used in the foregoing description only because the next
+ * method is only approximately an unbiased source of independently chosen
+ * bits. If it were a perfect source of randomly chosen bits, then the
+ * algorithm shown would choose {@code int} values from the stated range
+ * with perfect uniformity.
+ * <p>
+ * The algorithm is slightly tricky. It rejects values that would result in
+ * an uneven distribution (due to the fact that 2^31 is not divisible by n).
+ * The probability of a value being rejected depends on n. The worst case is
+ * n=2^30+1, for which the probability of a reject is 1/2, and the expected
+ * number of iterations before the loop terminates is 2.
+ * <p>
+ * The algorithm treats the case where n is a power of two specially: it
+ * returns the correct number of high-order bits from the underlying
+ * pseudo-random number generator. In the absence of special treatment, the
+ * correct number of <i>low-order</i> bits would be returned. Linear
+ * congruential pseudo-random number generators such as the one implemented
+ * by this class are known to have short periods in the sequence of values
+ * of their low-order bits. Thus, this special case greatly increases the
+ * length of the sequence of values returned by successive calls to this
+ * method if n is a small power of two.
+ *
+ * @param bound the upper bound (exclusive). Must be positive.
+ * @return the next pseudorandom, uniformly distributed {@code int} value
+ * between zero (inclusive) and {@code bound} (exclusive) from this random
+ * number generator's sequence
+ * @throws IllegalArgumentException if bound is not positive
+ * @since 1.2
+ */
+ @Override
+ public int nextInt(final int bound) {
+ //if (bound <= 0) {
+ //throw new RuntimeException("BadBound");
+ //}
+
+ /*int r = next(31);
+ int m = bound - 1;
+ if ((bound & m) == 0) // i.e., bound is a power of 2
+ {
+ r = (int) ((bound * (long) r) >> 31);
+ } else {
+ for (int u = r;
+ u - (r = u % bound) + m < 0;
+ u = next(31))
+ ;
+ }
+ return r;*/
+ //speedup, new nextInt ~+40%
+ this.last = this.seed ^ (this.seed << 21);
+ this.last ^= (this.last >>> 35);
+ this.last ^= (this.last << 4);
+ this.seed = this.last;
+ final int out = (int) this.last % bound;
+ return (out < 0) ? -out : out;
+ }
+ @Override
+ public int nextInt() {
+ return this.next(32);
+ }
+
+ @Override
+ public float nextFloat() {
+ return this.next(24) * FLOAT_UNIT;
+ }
+
+ @Override
+ public long nextLong() {
+ // it's okay that the bottom word remains signed.
+ return ((long)(this.next(32)) << 32) + this.next(32);
+ }
+
+ @Override
+ public void nextBytes(final byte[] bytes_arr) {
+ for (int iba = 0, lenba = bytes_arr.length; iba < lenba; ) {
+ for (int rndba = this.nextInt(),
+ nba = Math.min(lenba - iba, Integer.SIZE/Byte.SIZE);
+ nba-- > 0; rndba >>= Byte.SIZE) {
+ bytes_arr[iba++] = (byte)rndba;
+ }
+ }
+ }
+} \ No newline at end of file
generated by cgit (git 2.46.0) at 2025-04-17 05:53:23 +0000