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

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