# Number Theoretic Bit Generators

## `RandomSequenceRSA(b, t): RngIntElt, RngIntElt -> SeqEnum`

Generates a sequence of $t$ bits using the RSA pseudo-random bit generator with an RSA modulus of approximately $b$ bits in length. The modulus $n$ is computed by finding (pseudo-)random primes with the `RandomPrime` function. If gcd$(\phi(n),\ 3)$ is 1, then the exponent 3 will be used. Otherwise, a (pseudo-)random exponent $e$ is chosen so that gcd$( \phi(n),\ e)=1$. The seed is also chosen as a (pseudo-)random number modulo $n$. Bits are represented as elements of ${\bf F}_{2}$.

## `Example: Rsa Stats (ex-f17b7a)`

The code below counts the number of $1$’s that appear in a sequence of $1000$ bits generated from a 100-bit RSA modulus.

```magma
> Z := Integers();
> &+[ Z | b : b in RandomSequenceRSA(100, 1000) ];
497

```

## `RandomSequenceRSA(n, e, s, t): RngIntElt, RngIntElt, RngIntElt, RngIntElt -> SeqEnum`

Generates a sequence of $t$ bits using the RSA pseudo-random bit generator with modulus $n$, exponent $e$, and seed value $s$. Bits are represented as elements from ${\bf F}_{2}$. The integer $n$ must be larger than 1.

## `RSAModulus(b): RngIntElt -> RngIntElt, RngIntElt`

Returns an RSA Modulus $n$ of $b$ bits in length, and an exponent $e$ such that `Gcd(EulerPhi(n),e)=1`. The resulting values can be used to generate random bits with the function `RandomSequenceRSA`. The argument $b$ must be at least 16. *Warning*: RSA Moduli generated by Magma  should not be used for real world cryptographic applications. Such applications require a “true random” source to seed the random number generator. Magma’s method of seeding may not be sufficiently random to meet the requirements of cryptographic standards.

## `RSAModulus(b, e): RngIntElt, RngIntElt -> RngIntElt`

Returns an RSA Modulus $n$ of $b$ bits in length such that `Gcd(EulerPhi(n),e)=1`. The resulting value can be used with $e$ for the exponent to generate random bits with the function `RandomSequenceRSA`. The argument $b$ must be at least 16. The argument $e$ must be odd and must also be in the range $1 < e < 2^b$. *Warning*: RSA Moduli generated by Magma  should not be used for real world cryptographic applications. Such applications require a “true random” source to seed the random number generator. Magma’s method of seeding may not be sufficiently random to meet the requirements of cryptographic standards.

## `RandomSequenceBlumBlumShub(b, t): RngIntElt, RngIntElt -> SeqEnum`

## `BlumBlumShub(b, t): RngIntElt, RngIntElt -> SeqEnum`

Generates a sequence of $t$ bits using the Blum-Blum-Shub pseudo-random bit generator with a Blum-Blum-Shub modulus of approximately $b$ bits in length. The modulus $n$ is computed within Magma by finding (pseudo-)random primes with the `RandomPrime` function (the condition being that the primes are congruent to $3$ mod $4$). The seed is chosen as a (pseudo-)random number modulo $n$. Bits are represented as elements from ${\bf F}_{2}$. $b$ must be at least $16$.

## `RandomSequenceBlumBlumShub(n, s, t): RngIntElt, RngIntElt, RngIntElt -> SeqEnum`

## `BlumBlumShub(n, s, t): RngIntElt, RngIntElt, RngIntElt -> SeqEnum`

Generates a sequence of $t$ bits using the Blum-Blum-Shub pseudo-random bit generator with modulus $n$ and seed value $s$. Bits are represented as elements from ${\bf F}_{2}$. The argument $n$ must be larger than 1 and gcd($s$, $n$) must be 1.

## `BBSModulus(b): RngIntElt -> RngIntElt`

## `BlumBlumShubModulus(b): RngIntElt -> RngIntElt`

Returns a Blum-Blum-Shub Modulus $b$ bits in length. The resulting value can be used to generate random bits with the function `RandomSequenceBlumBlumShub`. The argument $b$ must be at least 16. *Warning*: Blum-Blum-Shub Moduli generated by Magma should not be used for real world cryptographic applications. Such applications require a “true random” source to seed the random number generator. Magma’s method of seeding may not be sufficiently random to meet the requirements of cryptographic standards.