Bug #61543 for Math-BigInt: [PATCH] bmodpow gives wrong results for powers of zero or negative numbers

I have added a couple of tests for bmodpow (patch #1). Apparently, this operator works only for powers of positive values. This could be fixed with an initial modulo operation (getting rid of negative values and mapping multiples of the modulus to zero) and a better coverage of the zero case. Patch #2 suggests such a solution. Someone with deeper understanding of the module internals, please validate.

diff -ru Math-BigInt-1.95.orig/t/bare_mbi.t Math-BigInt-1.95/t/bare_mbi.t --- Math-BigInt-1.95.orig/t/bare_mbi.t 2010-09-13 16:28:42.000000000 +0200 +++ Math-BigInt-1.95/t/bare_mbi.t 2010-09-22 02:37:42.000000000 +0200 @@ -1,7 +1,7 @@ #!/usr/bin/perl -w use strict; -use Test::More tests => 3279; +use Test::More tests => 3304; BEGIN { unshift @INC, 't'; } diff -ru Math-BigInt-1.95.orig/t/bigintpm.inc Math-BigInt-1.95/t/bigintpm.inc --- Math-BigInt-1.95.orig/t/bigintpm.inc 2010-09-13 16:28:42.000000000 +0200 +++ Math-BigInt-1.95/t/bigintpm.inc 2010-09-22 02:35:22.000000000 +0200 @@ -664,6 +664,46 @@ $x = $class->new(-3); $x %= $x; is ($x, 0); ############################################################################### +# bmodpow + +$y = $class->new(3); + +$z = $class->new(-1); +$x = $z->copy->bmodpow(-2, $y); is ($x, 1); +$x = $z->copy->bmodpow(-1, $y); is ($x, 2); +$x = $z->copy->bmodpow( 0, $y); is ($x, 1); +$x = $z->copy->bmodpow( 1, $y); is ($x, 2); +$x = $z->copy->bmodpow( 2, $y); is ($x, 1); + +$z = $class->new(0); +$x = $z->copy->bmodpow(-2, $y); is ($x->is_nan(), 1); +$x = $z->copy->bmodpow(-1, $y); is ($x->is_nan(), 1); +$x = $z->copy->bmodpow( 0, $y); is ($x, 1); +$x = $z->copy->bmodpow( 1, $y); is ($x, 0); +$x = $z->copy->bmodpow( 2, $y); is ($x, 0); + +$z = $class->new(1); +$x = $z->copy->bmodpow(-2, $y); is ($x, 1); +$x = $z->copy->bmodpow(-1, $y); is ($x, 1); +$x = $z->copy->bmodpow( 0, $y); is ($x, 1); +$x = $z->copy->bmodpow( 1, $y); is ($x, 1); +$x = $z->copy->bmodpow( 2, $y); is ($x, 1); + +$z = $class->new(2); +$x = $z->copy->bmodpow(-2, $y); is ($x, 1); +$x = $z->copy->bmodpow(-1, $y); is ($x, 2); +$x = $z->copy->bmodpow( 0, $y); is ($x, 1); +$x = $z->copy->bmodpow( 1, $y); is ($x, 2); +$x = $z->copy->bmodpow( 2, $y); is ($x, 1); + +$z = $class->new(3); +$x = $z->copy->bmodpow(-2, $y); is ($x->is_nan(), 1); +$x = $z->copy->bmodpow(-1, $y); is ($x->is_nan(), 1); +$x = $z->copy->bmodpow( 0, $y); is ($x, 1); +$x = $z->copy->bmodpow( 1, $y); is ($x, 0); +$x = $z->copy->bmodpow( 2, $y); is ($x, 0); + +############################################################################### # all tests done 1; diff -ru Math-BigInt-1.95.orig/t/bigintpm.t Math-BigInt-1.95/t/bigintpm.t --- Math-BigInt-1.95.orig/t/bigintpm.t 2010-09-13 16:28:42.000000000 +0200 +++ Math-BigInt-1.95/t/bigintpm.t 2010-09-22 02:37:49.000000000 +0200 @@ -1,7 +1,7 @@ #!/usr/bin/perl -w use strict; -use Test::More tests => 3279 + 6; +use Test::More tests => 3304 + 6; use Math::BigInt lib => 'Calc'; diff -ru Math-BigInt-1.95.orig/t/sub_mbi.t Math-BigInt-1.95/t/sub_mbi.t --- Math-BigInt-1.95.orig/t/sub_mbi.t 2010-09-13 16:28:42.000000000 +0200 +++ Math-BigInt-1.95/t/sub_mbi.t 2010-09-22 02:38:02.000000000 +0200 @@ -1,7 +1,7 @@ #!/usr/bin/perl -w use strict; -use Test::More tests => 3279 +use Test::More tests => 3304 + 5; # +5 own tests BEGIN { unshift @INC, 't'; }

diff -ru Math-BigInt-1.95.orig/lib/Math/BigInt/Calc.pm Math-BigInt-1.95/lib/Math/BigInt/Calc.pm --- Math-BigInt-1.95.orig/lib/Math/BigInt/Calc.pm 2010-09-13 16:33:34.000000000 +0200 +++ Math-BigInt-1.95/lib/Math/BigInt/Calc.pm 2010-09-22 02:32:55.000000000 +0200 @@ -2385,10 +2385,17 @@ splice @$num,0,1; $num->[0] = 0; return $num; } - if ((scalar @$num == 1) && (($num->[0] == 0) || ($num->[0] == 1))) + if (scalar @$num == 1) { - $num->[0] = 1; - return $num; + if ($num->[0] == 1 || _is_zero($c, $exp)) + { + $num->[0] = 1; + return $num; + } + if ($num->[0] == 0) + { + return $num; + } } # $num = _mod($c,$num,$mod); # this does not make it faster diff -ru Math-BigInt-1.95.orig/lib/Math/BigInt.pm Math-BigInt-1.95/lib/Math/BigInt.pm --- Math-BigInt-1.95.orig/lib/Math/BigInt.pm 2010-09-14 00:28:40.000000000 +0200 +++ Math-BigInt-1.95/lib/Math/BigInt.pm 2010-09-22 03:11:50.000000000 +0200 @@ -1843,6 +1843,9 @@ # check num for valid values (also NaN if there was no inverse but $exp < 0) return $num->bnan() if $num->{sign} !~ /^[+-]$/; + # project num into the range 0..mod-1 + $num->bmod($mod); + # $mod is positive, sign on $exp is ignored, result also positive $num->{value} = $CALC->_modpow($num->{value},$exp->{value},$mod->{value}); $num;