Quadratic Congruence Pseudo Random Number Generator
NewGenerator( opt1, opt2, ... )
opt1, opt2, ...
(optional) argument of the form option=value where option is one of primes, range, or seed
The NewGenerator command outputs a Maple procedure, a pseudo-random number generator, which when called outputs one pseudo-random integer. The output of the generator depends on the options described below. The default is to output integers on the range 0..999999999999, i.e., a random 12 digit integer.
The generator is a Quadratic Congruence (QC) generator. A QC generator uses the quadratic recurrence xk+1=xk2modn which generates a sequence of integers x1,... where n is a product of two primes p and q and x0 is determined from the seed of the generator. The pseudo-random integers are extracted from the sequence x1,... by using the least significant half of the digits of the xk's.
The quality of the pseudo-random numbers generated is expected to be good because the least significant bits of the xk+1 are cryptographically secure. See RandomTools[BlumBlumShub].
The primes p and q are chosen to be of the form p=2s+1 and q=2t+1 where s and t are prime and 2 is a primitive element in the Z mod s and in Z mod t. The initial value x0 is chosen as a function of the seed so that the period of the generator is maximal where the maximal period is lcm(s-1,t-1) which about n/8. We have precomputed random primes p and q satisfying these requirements of lengths 10, 12, 15 and 16 decimal digits in length. They are
Thus there are four choices of n available which have lengths 20, 24, 30, and 32 digits respectively with periods > 10^19, 10^23, 10^29 and 10^31, respectively. The larger primes will give ``better'' pseudo-random numbers and provide a longer the period. For most applications the smallest choice, the default, will be fine and it will be slightly faster than the larger choices.
The following optional arguments are supported. They are input as equations in any order.
The given integer is the seed of the generator. The value used for x0 is computed from the value of the seed argument It will be a quadratic residue in Z mod n of maximal period and x0 will be larger than the sqrt(n). The default value for seed is 3.
range=integer..integer or integer
If the value of the range argument is a range, then the integer will be chosen from that range. If the value of the range argument is an integer, then the integer will be take from the range [0..value). The default range is 1000000000000.
primes=10, 12, 15 or 16
The integer l, which must be one of 10, 12, 15 and 16 specifies the choice of the length of the primes p and q in decimal digits. The default value for primes in 10.
Q ≔ NewGenerator⁡range=1..6
Q ≔ procx ≔ irem⁡x^2,n;irem⁡x,6+1end proc
Q ≔ NewGenerator⁡range=1010
Q ≔ procx ≔ irem⁡x^2,n;irem⁡x,10000000000end proc
Q ≔ NewGenerator⁡primes=16,range=1032
Q ≔ proclocaly;x ≔ irem⁡x^2,n;y ≔ irem⁡x,10000000000000000;whiley<100000000000000000000000000000000dox ≔ irem⁡x^2,n;y ≔ 10000000000000000*y+irem⁡x,10000000000000000end do;irem⁡y,100000000000000000000000000000000end proc
Download Help Document