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

   1 USING: kernel math sequences namespaces
   2 math.miller-rabin combinators.lib
   3 math.functions accessors random ;
   4 IN: random.blum-blum-shub
   5
   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 ;
   9
  10 <PRIVATE
  11
  12 : generate-bbs-primes ( numbits -- p q )
  13     [ [ random-prime ] curry [ 4 mod 3 = ] generate ] dup bi ;
  14
  15 : next-bbs-bit ( bbs -- bit )
  16     [ [ x>> 2 ] [ n>> ] bi ^mod dup ] keep (>>x) 1 bitand ;
  17
  18 PRIVATE>
  19
  20 : <blum-blum-shub> ( numbits -- blum-blum-shub )
  21     generate-bbs-primes *
  22     [ find-relative-prime ] keep
  23     blum-blum-shub boa ;
  24
  25 M: blum-blum-shub random-32* ( bbs -- r )
  26     0 32 rot
  27     [ next-bbs-bit swap 1 shift bitor ] curry times ;