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
|
(***********************************************************************)
(* poly_test.ml - unit tests for Poly module *)
(* *)
(* 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 Common
open StdLabels
open MoreLabels
module Unix = UnixLabels
open Printf
open ZZp.Infix
let rand_int n = Random.State.int RMisc.det_rng n
let rand_bits () = Random.State.bits RMisc.det_rng
let ctr = ref 0
let test name cond =
printf ".%!";
incr ctr;
if not cond then raise
(Unit_test_failure (sprintf "Poly test %s:%d failed" name !ctr))
let divtest () =
let x = Poly.of_array [| ZZp.one; ZZp.one; ZZp.one; ZZp.one |] in
let c = ZZp.of_int 5 in
let y = Poly.of_array [| c; c; c |] in
let (q,r) = Poly.divmod x y in
test "invtest" (Poly.eq x (Poly.add (Poly.mult y q) r));
test "rtest" (Poly.eq r (Poly.of_array [| ZZp.one |]));
test "qtest" (Poly.eq q (Poly.of_array [| ZZp.zero; ZZp.inv c |]))
let rand_divtest () =
let p1 = Poly.of_array (Array.init (1 + rand_int 20)
~f:(fun i -> ZZp.rand rand_bits)) in
let p2 = Poly.of_array (Array.init (1 + rand_int 20)
~f:(fun i -> ZZp.rand rand_bits)) in
let (q,r) = Poly.divmod p1 p2 in
let z = ZZp.rand rand_bits in
let r_z = Poly.eval r z
and q_z = Poly.eval q z
and p1_z = Poly.eval p1 z
and p2_z = Poly.eval p2 z
in
test "rand_divtest" (p1_z =: p2_z *: q_z +: r_z)
(** returns true iff y divides x *)
let divides x y =
Poly.eq (Poly.modulo x y) Poly.zero
let gcd_test () =
let p1 = Poly.of_array (Array.init (1 + rand_int 20)
~f:(fun i -> ZZp.rand rand_bits)) in
let p2 = Poly.of_array (Array.init (1 + rand_int 20)
~f:(fun i -> ZZp.rand rand_bits)) in
let p3 = Poly.of_array (Array.init (1 + rand_int 20)
~f:(fun i -> ZZp.rand rand_bits)) in
let p1 = Poly.mult p1 p3 in
let p2 = Poly.mult p2 p3 in
let gcd = Poly.gcd p1 p2 in
test "gcd - p3 div" (divides gcd p3);
test "gcd - gcd div 1" (divides p1 gcd);
test "gcd - gcd div 2" (divides p2 gcd);
let p1 = Poly.div p1 gcd in
let p2 = Poly.div p2 gcd in
let gcd = Poly.gcd p1 p2 in
test "gcd - zero" (Poly.degree gcd = 0)
let run () =
begin
for i = 1 to 100 do
rand_divtest ()
done;
for i = 1 to 100 do
gcd_test ()
done;
divtest ();
end
|
