1 USING: accessors kernel math math.functions math.primes random ;
2 IN: random.blum-blum-shub
4 ! Blum Blum Shub, n = pq, x_i+1 = x_i ^ 2 mod n
5 ! return low bit of x+1
6 TUPLE: blum-blum-shub x n ;
10 : generate-bbs-prime ( numbits -- p )
11 dup random-prime dup 4 mod 3 =
12 [ nip ] [ drop generate-bbs-prime ] if ;
14 : generate-bbs-primes ( numbits -- p q )
15 [ generate-bbs-prime ] [ generate-bbs-prime ] bi ;
17 : next-bbs-bit ( bbs -- bit )
18 dup [ x>> 2 ] [ n>> ] bi ^mod [ >>x drop ] [ 1 bitand ] bi ;
22 : <blum-blum-shub> ( numbits -- blum-blum-shub )
24 [ find-relative-prime ] keep
27 M: blum-blum-shub random-32*
29 [ next-bbs-bit swap 1 shift bitor ] curry times ;