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