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