1 USING: kernel math sequences namespaces
2 math.miller-rabin combinators.lib
3 math.functions accessors random ;
4 IN: random.blum-blum-shub
6 ! Blum Blum Shub, n = pq, x_i+1 = x_i ^ 2 mod n
7 ! return low bit of x+1
8 TUPLE: blum-blum-shub x n ;
12 : generate-bbs-primes ( numbits -- p q )
13 [ [ random-prime ] curry [ 4 mod 3 = ] generate ] dup bi ;
15 : next-bbs-bit ( bbs -- bit )
16 dup [ x>> 2 ] [ n>> ] bi ^mod [ >>x drop ] [ 1 bitand ] bi ;
20 : <blum-blum-shub> ( numbits -- blum-blum-shub )
22 [ find-relative-prime ] keep
25 M: blum-blum-shub random-32* ( bbs -- r )
27 [ next-bbs-bit swap 1 shift bitor ] curry times ;