extra/math/primes/solovay-strassen/solovay-strassen.factor

   1 ! Copyright (C) 2014 John Benediktsson
   2 ! See http://factorcode.org/license.txt for BSD license
   3
   4 USING: combinators kernel math math.extras math.extras.private
   5 math.functions ranges random sequences ;
   6
   7 IN: math.primes.solovay-strassen
   8
   9 <PRIVATE
  10
  11 :: (solovay-strassen) ( n numtrials -- ? )
  12     numtrials <iota> [
  13         drop
  14         n 1 - [1..b) random :> a
  15         a n simple-gcd 1 > [ t ] [
  16             a n jacobi n mod'
  17             a n 1 - 2 /i n ^mod = not
  18         ] if
  19     ] none? ;
  20
  21 PRIVATE>
  22
  23 : solovay-strassen* ( n numtrials -- ? )
  24     {
  25         { [ over 1 <= ] [ 2drop f ] }
  26         { [ over even? ] [ drop 2 = ] }
  27         [ (solovay-strassen) ]
  28     } cond ;
  29
  30 : solovay-strassen ( n -- ? ) 32 solovay-strassen* ;