G chooses a prime in the range by choosing an odd number from a flat distribution within the range and discarding it if composite.
These choices are determined by the state object and calling G changes the object.
A Haskell implementation might need monads here.
{((state 'rbi) n) produces a 0 argument function each invocation of which produces an integer in the range of [0, n−1].
(rbi (quotient sz 2)) chooses a generator for half of the range for we do not want to test even numbers for primality.
(+ ost (* 2 (sg))) chooses from the odd members of the range since ost is odd.}
We use the Miller−Rabin primality test but for robustness it would be better for other implementations to use a different primality test.
Logic of rbi
To choose a member of [0, y−1] randomly we first express y−1 as a numeral base 256.
We use the numeral metaphor to recall how you learned as a child to compare large decimal arabic numerals.
{This is ’rbi logic is in the module RC4 where the numeral is the vector a.}
Then we produce candidate sample numerals high digit first always abandoning the candidate as soon as it is seen to be greater than y−1, and begin again.
We take the high order candidate digit modulo the smallest power of 2 greater than the high digit of y−1.