The NewGenerator command outputs a Maple procedure, a pseudo-random number generator, which when called outputs a pseudo-random number. The generator is a Blum-Blum-Shub (BBS) generator. A BBS generator uses the following quadratic recurrence to generate a sequence of integers $x_1,x_2,\dots$ from which cryptographically secure pseudo-random bits $z_1,z_2,\dots$ are extracted:

where

$n$ is a product of two large primes p and q,

$m=⌊{\log }_2\left({\log }_2\left(n\right)\right)⌋$, and

$x_0$ is determined from the seed s.

Each iteration of $z_{k+1}$, the least significant $m$ bits of $x_{k+1}$, generates $m$ cryptographically secure bits. The output of the generator depends on the options described below.

The cryptographic security of the BBS generator assumes that the number theoretic problem of distinguishing a quadratic residue from a pseudo-square in Z mod n is computationally infeasible when n is the product of two primes p and q and the factorization of n is not known. Thus it also assumes that integer factorization is computationally infeasible. Recall the definitions of a quadratic residue and pseudo-square:

Definition: An integer x in Z mod n is a quadratic residue if (i) $\gcd \left(x\,n\right)=1$ and (ii) $x=y^2\mathbf{mod}n$ for some integer y.

Definition: An integer z in Z mod n where $n=pq$ is a pseudo-square if (i) $\gcd \left(z\,n\right)=1$, (ii) z is not a quadratic residue in Z mod p, and (iii) z is not a quadratic residue in Z mod q.

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 both Z mod s and in Z mod t.  This choice guarantees that p and q are both congruent to 3 mod 4 (a requirement for the security of the generator) and also that the period of the generator for $x_0$ for any quadratic residue other than 1 is either $s-1$ or $t-1$ or $\mathrm{lcm}\left(s-1\,t-1\right)$, all of which are large. Random primes p and q, and their product $n=pq$, satisfying these requirements of lengths 512 bits, 768 bits, and 1024 bits, have been precomputed and the prime factorization discarded (Maple does not have the factorizations). Thus there are three choices for $n$ of lengths 308, 462, and 616 decimal digits, providing a range of security for cryptographic applications.

The following optional arguments are supported. They are input as equations in any order.

range=integer..integer or integer

The range option specifies the range from which the integer is chosen.  If a range is given, the returned procedure will generate numbers in this range. If an integer is given, the returned procedure will return integers in the range 0 to value-1. By default the range is 0 to 10^12-1.

seed=integer

The option seed determines the seed for the generator. The value used for $x_0$ must be a "random" quadratic residue which is not equal to 1 (to avoid a short period). The value used for $x_0$ is computed from the value of the seed option.  If a seed is not given, a seed is generated by calling RandomTools[MersenneTwister][GenerateInteger] with the argument range = 10^99..10^100.

The RandomTools[BlumBlumShub] module also exports the NewBitGenerator function. This function provides the user with greater control over the properties of the returned procedure.  For cryptographic applications, the NewBitGenerator function should be used.

$\mathrm{with}\left(\mathrm{RandomTools}\left[\mathrm{BlumBlumShub}\right]\right)$

$\left[\mathrm{NewBitGenerator}\,\mathrm{NewGenerator}\right]$

$s≔1050109365100103751001961108357097849013652340237134723870\:$

$B≔\mathrm{NewGenerator}\left(\mathrm{seed}=2\right)$

$B≔\mathbf{proc}\left(\right)\mathbf{local}n\&comma;p\&semi;p≔\mathbf{proc}\left(\right)\mathbf{local}i\&semi;\mathbf{for}i\mathbf{from}c\mathbf{by}10\mathbf{to}40\mathbf{do}x≔\mathrm{irem}\left(x\&Hat;2\&comma;n\right)\&semi;z≔1024\&ast;z\&plus;\mathrm{irem}\left(x\&comma;1024\right)\mathbf{end\; do}\&semi;c≔i-40\&semi;\mathrm{iquo}\left(z\&comma;2\&Hat;c\&comma;\&apos;z\&apos;\right)\mathbf{end\; proc}\&semi;n≔p\left(\right)\&semi;\mathbf{while}1000000000000<=n\mathbf{do}n≔p\left(\right)\mathbf{end\; do}\&semi;n\mathbf{end\; proc}$

$B\left(\right)$

$493660033144$

$B\left(\right)$

$259218944679$

$\mathrm{seq}\left(B\left(\right)\&comma;i=1..10\right)$

$17627898170,966628291159,628124827667,692163973638,365738744555,283269255713,255572006637,712645761945,712457622044,426819767701$

$B≔\mathrm{NewGenerator}\left(\mathrm{seed}=s\&comma;\mathrm{range}=1..1000\right)\&colon;$

$B\left(\right)$

$722$

$B\left(\right)$

$520$

$B≔\mathrm{NewGenerator}\left(\mathrm{seed}=s\&comma;\mathrm{range}={10}^{20}..{10}^{30}\right)\&colon;$

$B\left(\right)$

$893182270928831182291970575150$

$\mathrm{seq}\left(B\left(\right)\&comma;i=1..5\right)$

$571028873893626957286791880500,149691015279629477184761484186,893310462378765125162315235384,749992797388668654605785130192,462774729207078150350323115146$