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.