/pliant/util/crypto/intn.pli
 
 1  abstract 
 2    [A few more functions for the 'Intn' data type: ] 
 3    [these are 'random' 'prime' 'pgcd' and 'inverse'] 
 4   
 5   
 6  module "random.pli" 
 7   
 8  constant prime0_fast true 
 9  constant prime0_maxi 1000 
 10  constant trace false 
 11  constant debug false 
 12   
 13   
 14  doc 
 15    listing 
 16      function random p -> r 
 17        arg Intn p r 
 18    [Returns a strong peuso random number ranging from 0 to p-1.] 
 19    
 20  function random p -> r 
 21    arg Intn r 
 22    binary_decode (random_string (p:nbbits+64)\8) true 
 23    apply_modulus p 
 24   
 25   
 26  doc 
 27    listing 
 28      function prime p error_probability -> r 
 29        arg Intn p ; arg Float error_probability ; arg Intn r 
 30    [Returns a strong peuso random prime number ranging from 0 to p-1.] ; eol 
 31    [The 'error_probability' should be a very small number such as 1e-30. The smaller it is, the slower the algorithm will be.] 
 32   
 33   
 34  if prime0_fast 
 35   
 36    gvar Array:Intn primes 
 37   
 38    function prime0 p -> r 
 39      arg Intn p ; arg Bool r 
 40      if p<2 
 41        := false 
 42      else 
 43        for (var Int i) primes:size-1 
 44          if p%primes:i=0 
 45            return primes:i>=p 
 46        := true 
 47   
 48    for (gvar Int uu) 1 prime0_maxi 
 49      if prime0:uu 
 50        primes += uu 
 51   
 52  else 
 53   
 54    function prime0 p -> r 
 55      arg Intn p ; arg Bool r 
 56      if p<2 
 57       return false 
 58      else 
 59        var Intn i := 2 
 60        while i*i<=p and i<prime0_maxi 
 61          if p%i=0 
 62            return false 
 63          i := i+1 
 64        return true 
 65   
 66   
 67  function prime1 p error_probability -> r 
 68    arg Intn p ; arg Float error_probability ; arg Bool r 
 69    var Bool all := true 
 70    var Float ep := 1 
 71    if trace 
 72      var Int count := 0 
 73    while ep>error_probability 
 74      if trace 
 75        console "prime test " count "  [lf]" 
 76      var Intn := 1+(random p-1) 
 77      var Intn := a^((p-1)\2)%p 
 78      if b=1 
 79        void 
 80      eif b=p-1 
 81        all := false 
 82      else 
 83        return false 
 84      ep := ep*0.5 
 85      if trace 
 86        count := count+1 
 87    return not all 
 88   
 89   
 90  function prime n error_probability -> r 
 91    arg Intn n ; arg Float error_probability ; arg Intn r 
 92    part pick 
 93      := random n 
 94      if debug 
 95        console "? " r 
 96      if not prime0:r 
 97        if debug 
 98          console " A" eol 
 99        restart pick 
 100      if not (prime1 error_probability) 
 101        if debug 
 102          console " B" eol 
 103        restart pick 
 104      if debug 
 105        console " OK" eol 
 106   
 107   
 108  doc 
 109    listing 
 110      function pgcd a b -> g 
 111        arg Intn a b g 
 112    [Computes the greates commun divisor of both 'a' and 'b'.] 
 113   
 114   
 115  function pgcd a b -> g 
 116    arg Intn g 
 117    var Intn := a 
 118    var Intn := b 
 119    := y 
 120    while x>0 
 121      := x 
 122      := y%x 
 123      := g 
 124   
 125   
 126  doc 
 127    listing 
 128      function inverse x n -> r 
 129        arg Intn x n r 
 130    [Finds an inverse 'r' of 'x' modulo 'n'. ] ; eol 
 131    [It means that x*r mod n = 1] 
 132   
 133  function euclide_update un vn q 
 134    arg_rw Intn un vn ; arg Intn q 
 135    var Intn tn := un-vn*q 
 136    un := vn 
 137    vn := tn 
 138   
 139  function euclide u v u1_out u2_out -> r 
 140    arg Intn v ; arg_w Intn u1_out u2_out ; arg Intn r 
 141    var Intn u1 := 1 
 142    var Intn u3 := u 
 143    var Intn v1 := 0 
 144    var Intn v3 := v 
 145    while v3>0 
 146      var Intn := u3\v3 
 147      euclide_update u1 v1 q 
 148      euclide_update u3 v3 q 
 149    u1_out := u1 
 150    u2_out := (u3-u1*u)\v 
 151    return u3 
 152   
 153  function inverse x n -> r 
 154    arg Intn r 
 155    var Intn u1 u2 
 156    var Intn := euclide u1 u2 
 157    if i<>1 
 158      return 0 
 159    eif u1>=0 
 160      return u1 
 161    else 
 162      return u1+n 
 163   
 164   
 165  export random prime pgcd inverse