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