File: zZp.ml

package info (click to toggle)
sks 1.1.6-14
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 2,296 kB
  • sloc: ml: 15,228; ansic: 1,069; sh: 358; makefile: 347
file content (215 lines) | stat: -rw-r--r-- 5,957 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
(***********************************************************************)
(* zZp.ml - Field of integers mod p (for a settable prime p)           *)
(*                                                                     *)
(* Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, *)
(*               2011, 2012, 2013  Yaron Minsky and Contributors       *)
(*                                                                     *)
(* This file is part of SKS.  SKS is free software; you can            *)
(* redistribute it and/or modify it under the terms of the GNU General *)
(* Public License as published by the Free Software Foundation; either *)
(* version 2 of the License, or (at your option) any later version.    *)
(*                                                                     *)
(* This program is distributed in the hope that it will be useful, but *)
(* WITHOUT ANY WARRANTY; without even the implied warranty of          *)
(* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU   *)
(* General Public License for more details.                            *)
(*                                                                     *)
(* You should have received a copy of the GNU General Public License   *)
(* along with this program; if not, write to the Free Software         *)
(* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 *)
(* USA or see <http://www.gnu.org/licenses/>.                          *)
(***********************************************************************)

open StdLabels
open MoreLabels
module Unix=UnixLabels
open Printf

module N = Number
open Number.Infix
(* open Big_int *)

type zz = Number.z
type zzref = Number.z ref
type mut_array = zz array

let order = ref two
let nbits = ref 0
let nbytes = ref 0

let two = two
let zero = zero
let one = one

let set_order value =
  order := value;
  nbits := N.nbits !order;
  nbytes := !nbits / 8 + (if !nbits mod 8 = 0 then 0 else 1)

let num_bytes () = !nbytes
let of_bytes bytes = N.of_bytes bytes
let to_bytes n = N.to_bytes ~nbytes:!nbytes (n %! !order)
let of_int i  = (Number.of_int i) %! !order
let to_N x = x
let of_N x = x %! !order

let add x y = (x +! y) %! !order
let sub x y = (x -! y) %! !order
let mul x y = (x *! y) %! !order
let mult x y = (x *! y) %! !order
let imult x y = (Number.int_mult y x) %! !order



let add_fast x y = (x +! y)
let mul_fast x y = (x *! y)
let mult_fast x y = (x *! y)
let canonicalize x = x %! !order

let shl x i =
  x *! Number.int_posint_power 2 i

let square x = (x *! x) %! !order
let square_fast x = x *! x

let imul x y = (y *! x) %! !order
let neg x = !order -! x

let inv x =
  if x =! zero then raise (Invalid_argument "ZZp.inv: Attempt to invert 0");
  let (u,_,_) = N.gcd_ex x !order in u %! !order


let div x y = (x *! (inv y)) %! !order
let sub_fast x y = x -! y

let lt = ( <! )
let gt = ( >! )
let eq = ( =! )
let neq x y = not (x =! y)

let to_string = Number.to_string
let of_string = Number.of_string
let print x = print_string (to_string x)

let points n = Array.init n
  ~f:(fun i ->
        let ival = ((i + 1) / 2) * (if i mod 2 = 0 then 1 else (-1)) in
        Number.of_int ival)

let svalues n =
  Array.init n ~f:(fun i -> one)

(* In-place operations.  Since we're using Big_int, there are no in-place operations,
   so we just fake it. *)

let mult_in v x y =
  v := mult x y

let mult_fast_in v x y =
  v := mult_fast x y

let add_in v x y =
  v := add x y

let add_fast_in v x y =
  v := add_fast x y

let sub_in v x y =
  v := sub x y

let sub_fast_in v x y =
  v := x -! y

let copy_in v x = v := x
let copy_out v = !v
let make_ref x = ref x
let look = copy_out

let canonicalize_in v = v := !v %! !order

(* Array-wise functions for adding elements to svalues *)

let add_el_array ~points el =
  Array.init (Array.length points)
    ~f:( fun i ->
           let rval = (points.(i) -! el) %! !order in
           if eq rval zero
           then failwith "Sample point added to set"
           else rval )

let del_el_array ~points el =
  Array.map ~f:inv (add_el_array ~points el)

let mult_array ~svalues array =
  if Array.length svalues <> Array.length array
  then raise (Invalid_argument "ZZp.mult_array: array lengths don't match");
  for i = 0 to Array.length array - 1 do
    svalues.(i) <- mult svalues.(i) array.(i)
  done

(** Element-based functions for adding elements to svalues *)

let add_el ~svalues ~points el =
  if Array.length svalues <> Array.length points
  then raise (Invalid_argument "ZZp.add_el: array lengths don't match");
  for i = 0 to Array.length points - 1 do
    svalues.(i) <- mult svalues.(i) (points.(i) -! el)
  done

(* needs checking *)
let del_el ~svalues ~points el =
  if Array.length svalues <> Array.length points
  then raise (Invalid_argument "ZZp.del_el: array lengths don't match");
  for i = 0 to Array.length points - 1 do
    svalues.(i) <- div svalues.(i) (points.(i) -! el)
  done

let array_mult x y =
  let len = Array.length x in
  Array.init len ~f:(fun i -> mult x.(i) y.(i))

let mut_array_div x y =
  Array.init (Array.length x) ~f:(fun i -> div x.(i) y.(i))

let mut_array_copy ar = Array.copy ar

let cmp = Number.compare

let length array = Array.length array

let mut_array_to_array array = Array.copy array
let mut_array_of_array array = Array.copy array

let to_string_array x =
  Array.init 1 ~f:(fun i -> to_bytes x)

module Set = Set.Make(struct
                        type t = zz
                        let compare = Number.compare
                      end)

let zset_of_list list =
  List.fold_left ~init:Set.empty
    ~f:(fun x y -> Set.add y x) list


let of_number x = x
let canonical_of_number x =
  x %! !order

let to_number x = x

let rand bits =
  let n = Prime.randint bits !order in
  n %! !order

module Infix =
struct
  let ( +: ) = add
  let ( -: ) = sub
  let ( *: ) = mul
  let ( /: ) = div
  let ( =: ) = ( =! )
  let ( <>: ) = ( <>! )
end