extra/random/blum-blum-shub/blum-blum-shub.factor

   1 USING: kernel math sequences namespaces
   2 math.miller-rabin math.functions accessors random ;
   3 IN: random.blum-blum-shub
   4
   5 ! Blum Blum Shub, n = pq, x_i+1 = x_i ^ 2 mod n
   6 ! return low bit of x+1
   7 TUPLE: blum-blum-shub x n ;
   8
   9 <PRIVATE
  10
  11 : generate-bbs-prime ( numbits -- p )
  12     dup random-prime dup 4 mod 3 =
  13     [ nip ] [ drop generate-bbs-prime ] if ;
  14
  15 : generate-bbs-primes ( numbits -- p q )
  16     [ generate-bbs-prime ] [ generate-bbs-prime ] bi ;
  17
  18 : next-bbs-bit ( bbs -- bit )
  19     dup [ x>> 2 ] [ n>> ] bi ^mod [ >>x drop ] [ 1 bitand ] bi ;
  20
  21 PRIVATE>
  22
  23 : <blum-blum-shub> ( numbits -- blum-blum-shub )
  24     generate-bbs-primes *
  25     [ find-relative-prime ] keep
  26     blum-blum-shub boa ;
  27
  28 M: blum-blum-shub random-32* ( bbs -- r )
  29     0 32 rot
  30     [ next-bbs-bit swap 1 shift bitor ] curry times ;