1#!/usr/bin/env perl
2use strict;
3use warnings;
4
5use Test::More;
6use Math::Prime::Util::GMP qw/invmod sqrtmod addmod mulmod divmod powmod/;
7use Math::BigInt;  # Don't use GMP so we don't have to work around bug
8
9my $use64 = (~0 > 4294967296 && 18446744073709550592 != ~0);
10my $extra = defined $ENV{EXTENDED_TESTING} && $ENV{EXTENDED_TESTING};
11
12my @invmods = (
13 [ 0, 0, undef],
14 [ 1, 0, undef],
15 [ 0, 1, undef],
16 [ 1, 1, 0],
17 [ 45, 59, 21],
18 [  42,  2017, 1969],
19 [  42, -2017, 1969],
20 [ -42,  2017, 48],
21 [ -42, -2017, 48],
22 [ 14, 28474, undef],
23 [ 13, "9223372036854775808", "5675921253449092805" ],
24 [ 14, "18446744073709551615", "17129119497016012214" ],
25);
26my @sqrtmods = (
27 [ 0, 0, undef],
28 [ 1, 0, undef],
29 [ 0, 1, 0],
30 [ 1, 1, 0],
31 [ 58, 101, 19],
32 [ 111, 113, 26],
33 [ "9223372036854775808", "5675921253449092823", "22172359690642254" ],
34 [ "18446744073709551625", "340282366920938463463374607431768211507", "57825146747270203522128844001742059051" ],
35);
36
37plan tests => 0
38            + scalar(@invmods)
39            + scalar(@sqrtmods)
40            + 4 + 3
41            + 1                      # addmod
42            + 1                      # submod
43            + 2                      # mulmod
44            + 2                      # divmod
45            + 2                      # powmod
46            + 0;
47
48###### invmod
49foreach my $r (@invmods) {
50  my($a, $n, $exp) = @$r;
51  is( invmod($a,$n), $exp, "invmod($a,$n) = ".((defined $exp)?$exp:"<undef>") );
52}
53
54###### sqrtmod
55foreach my $r (@sqrtmods) {
56  my($a, $n, $exp) = @$r;
57  is( sqrtmod($a,$n), $exp, "sqrtmod($a,$n) = ".((defined $exp)?$exp:"<undef>") );
58}
59
60##########################################################################
61
62my $num = ($extra) ? 199 : 39;
63my @i1 = map { nrand() } 0 .. $num;
64my @i2 = map { nrand() } 0 .. $num;
65my @i2t= map { $i2[$_] >> 1 } 0 .. $num;
66my @i3 = map { my $r = 0; $r = nrand() until $r > 1; $r; } 0 .. $num;
67my(@exp,@res);
68
69
70###### add/mul/div/pow with small arguments
71@exp = map { undef } 0..27;
72is_deeply([map { addmod($_ & 3, ($_>>2)-3, 0) } 0..27], \@exp, "addmod(..,0)");
73is_deeply([map { mulmod($_ & 3, ($_>>2)-3, 0) } 0..27], \@exp, "mulmod(..,0)");
74is_deeply([map { divmod($_ & 3, ($_>>2)-3, 0) } 0..27], \@exp, "divmod(..,0)");
75is_deeply([map { powmod($_ & 3, ($_>>2)-3, 0) } 0..27], \@exp, "powmod(..,0)");
76
77@exp = map { 0 } 0..27;
78is_deeply([map { addmod($_ & 3, ($_>>2)-3, 1) } 0..27], \@exp, "addmod(..,1)");
79is_deeply([map { mulmod($_ & 3, ($_>>2)-3, 1) } 0..27], \@exp, "mulmod(..,1)");
80is_deeply([map { powmod($_ & 3, ($_>>2)-3, 1) } 0..27], \@exp, "powmod(..,1)");
81# TODO divmod
82
83
84###### addmod
85@exp = (); @res = ();
86for (0 .. $num) {
87  push @exp, Math::BigInt->new($i1[$_])->badd($i2[$_])->bmod($i3[$_]);
88  push @res, addmod($i1[$_], $i2[$_], $i3[$_]);
89}
90is_deeply( \@res, \@exp, "addmod on ".($num+1)." random inputs" );
91
92###### submod
93@exp = (); @res = ();
94for (0 .. $num) {
95  push @exp, Math::BigInt->new($i1[$_])->bsub($i2t[$_])->bmod($i3[$_]);
96  push @res, addmod($i1[$_], -$i2t[$_], $i3[$_]);
97}
98is_deeply( \@res, \@exp, "addmod with negative second input on ".($num+1)." random inputs" );
99
100###### mulmod
101@exp = (); @res = ();
102for (0 .. $num) {
103  push @exp, Math::BigInt->new($i1[$_])->bmul($i2[$_])->bmod($i3[$_]);
104  push @res, mulmod($i1[$_], $i2[$_], $i3[$_]);
105}
106is_deeply( \@res, \@exp, "mulmod on ".($num+1)." random inputs" );
107
108###### mulmod (neg)
109@exp = (); @res = ();
110for (0 .. $num) {
111  push @exp, Math::BigInt->new($i1[$_])->bmul(-$i2t[$_])->bmod($i3[$_]);
112  push @res, mulmod($i1[$_], -$i2t[$_], $i3[$_]);
113}
114is_deeply( \@res, \@exp, "mulmod with negative second input on ".($num+1)." random inputs" );
115
116###### divmod
117@exp = (); @res = ();
118for (0 .. $num) {
119  push @exp, Math::BigInt->new($i2[$_])->bmodinv($i3[$_])->bmul($i1[$_])->bmod($i3[$_]);
120  push @res, divmod($i1[$_], $i2[$_], $i3[$_]);
121}
122@exp = map { $_->is_nan() ? undef : $_ } @exp;
123is_deeply( \@res, \@exp, "divmod on ".($num+1)." random inputs" );
124
125###### divmod (neg)
126@exp = (); @res = ();
127for (0 .. $num) {
128  push @exp, Math::BigInt->new(-$i2t[$_])->bmodinv($i3[$_])->bmul($i1[$_])->bmod($i3[$_]);
129  push @res, divmod($i1[$_], -$i2t[$_], $i3[$_]);
130}
131@exp = map { $_->is_nan() ? undef : $_ } @exp;
132is_deeply( \@res, \@exp, "divmod with negative second input on ".($num+1)." random inputs" );
133
134my $pnum = int($num/2);
135
136###### powmod
137@exp = (); @res = ();
138for (0 .. $pnum) {
139  push @exp, Math::BigInt->new($i1[$_])->bmodpow($i2[$_],$i3[$_]);
140  push @res, powmod($i1[$_], $i2[$_], $i3[$_]);
141}
142is_deeply( \@res, \@exp, "powmod on ".($pnum+1)." random inputs" );
143
144###### powmod (neg)
145@exp = (); @res = ();
146for (0 .. $pnum) {
147  push @exp, Math::BigInt->new($i1[$_])->bmodpow(-$i2t[$_],$i3[$_]);
148  push @res, powmod($i1[$_], -$i2t[$_], $i3[$_]);
149}
150@exp = map { $_->is_nan() ? undef : $_ } @exp;
151is_deeply( \@res, \@exp, "powmod with negative exponent on ".($pnum+1)." random inputs" );
152
153
154
155sub nrand {
156  return Math::Prime::Util::GMP::urandomb($use64 ? 64 : 32);
157}
158