Bug #63237 for Math-BigInt: [PATCH] issues with bmodinv and bmodpow in Math-BigInt-1.99

Math-BigInt-1.99 set out to fix Math::BigInt::Calc::_modpow, but somehow managed to introduce a more severe bug along the way. Powers of one modulo whatever are now zero most of the time! I suggest to look at border cases involving modular arithmetic again, with a bit more thoroughness. Here is a small patch fixing the treatment of modulus one for bmodinv, as well as negative x values and the new bug for bmodpow. Note that in the trivial ring modulo 1, zero actually has a multiplicative inverse, namely itself. I have added a bunch of test cases as a separate patch. Updates for test counts are omitted, as these would be a moving target anyway. These patches supersede those I submitted with #61543, by the way. Thank you for your efforts. I consider Math::BigInt one of the most useful additions to the core language. -Martin

diff -ru Math-BigInt-1.99.orig/lib/Math/BigInt/Calc.pm Math-BigInt-1.99/lib/Math/BigInt/Calc.pm --- Math-BigInt-1.99.orig/lib/Math/BigInt/Calc.pm 2010-11-15 05:42:18.000000000 +0100 +++ Math-BigInt-1.99/lib/Math/BigInt/Calc.pm 2010-11-22 17:16:56.000000000 +0100 @@ -2386,7 +2386,7 @@ # 0^a (mod m) = 0 if m != 0, a != 0 # 0^0 (mod m) = 1 if m != 0 - if (_is_one($c, $num)) { + if (_is_zero($c, $num)) { if (_is_zero($c, $exp)) { @$num = 1; } else { diff -ru Math-BigInt-1.99.orig/lib/Math/BigInt.pm Math-BigInt-1.99/lib/Math/BigInt.pm --- Math-BigInt-1.99.orig/lib/Math/BigInt.pm 2010-11-15 05:42:10.000000000 +0100 +++ Math-BigInt-1.99/lib/Math/BigInt.pm 2010-11-22 18:04:16.000000000 +0100 @@ -1800,6 +1800,7 @@ return $x if $x->modify('bmodinv'); + return $x->bzero() if $y->is_one(); # modulus 1 return $x->bnan() if ($y->{sign} ne '+' # -, NaN, +inf, -inf || $x->is_zero() # or num == 0 @@ -1843,6 +1844,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;

diff -ru Math-BigInt-1.99.orig/t/bigintpm.inc Math-BigInt-1.99/t/bigintpm.inc --- Math-BigInt-1.99.orig/t/bigintpm.inc 2010-11-14 17:24:40.000000000 +0100 +++ Math-BigInt-1.99/t/bigintpm.inc 2010-11-22 18:16:39.000000000 +0100 @@ -2503,3 +2503,173 @@ +inf:inf -inf:-inf NaNas_bin:NaN +&bmodinv +-2:1:0 +-1:1:0 +0:1:0 +1:1:0 +2:1:0 +3:1:0 +4:1:0 +-2:3:1 +-1:3:2 +0:3:NaN +1:3:1 +2:3:2 +3:3:NaN +4:3:1 +-2:4:NaN +-1:4:3 +0:4:NaN +1:4:1 +2:4:NaN +3:4:3 +4:4:NaN +&bmodpow +-2:-2:1:0 +-1:-2:1:0 +0:-2:1:0 +1:-2:1:0 +2:-2:1:0 +3:-2:1:0 +4:-2:1:0 +-2:-1:1:0 +-1:-1:1:0 +0:-1:1:0 +1:-1:1:0 +2:-1:1:0 +3:-1:1:0 +4:-1:1:0 +-2:0:1:0 +-1:0:1:0 +0:0:1:0 +1:0:1:0 +2:0:1:0 +3:0:1:0 +4:0:1:0 +-2:1:1:0 +-1:1:1:0 +0:1:1:0 +1:1:1:0 +2:1:1:0 +3:1:1:0 +4:1:1:0 +-2:2:1:0 +-1:2:1:0 +0:2:1:0 +1:2:1:0 +2:2:1:0 +3:2:1:0 +4:2:1:0 +-2:3:1:0 +-1:3:1:0 +0:3:1:0 +1:3:1:0 +2:3:1:0 +3:3:1:0 +4:3:1:0 +-2:4:1:0 +-1:4:1:0 +0:4:1:0 +1:4:1:0 +2:4:1:0 +3:4:1:0 +4:4:1:0 +-2:-2:3:1 +-1:-2:3:1 +0:-2:3:NaN +1:-2:3:1 +2:-2:3:1 +3:-2:3:NaN +4:-2:3:1 +-2:-1:3:1 +-1:-1:3:2 +0:-1:3:NaN +1:-1:3:1 +2:-1:3:2 +3:-1:3:NaN +4:-1:3:1 +-2:0:3:1 +-1:0:3:1 +0:0:3:1 +1:0:3:1 +2:0:3:1 +3:0:3:1 +4:0:3:1 +-2:1:3:1 +-1:1:3:2 +0:1:3:0 +1:1:3:1 +2:1:3:2 +3:1:3:0 +4:1:3:1 +-2:2:3:1 +-1:2:3:1 +0:2:3:0 +1:2:3:1 +2:2:3:1 +3:2:3:0 +4:2:3:1 +-2:3:3:1 +-1:3:3:2 +0:3:3:0 +1:3:3:1 +2:3:3:2 +3:3:3:0 +4:3:3:1 +-2:4:3:1 +-1:4:3:1 +0:4:3:0 +1:4:3:1 +2:4:3:1 +3:4:3:0 +4:4:3:1 +-2:-2:4:NaN +-1:-2:4:1 +0:-2:4:NaN +1:-2:4:1 +2:-2:4:NaN +3:-2:4:1 +4:-2:4:NaN +-2:-1:4:NaN +-1:-1:4:3 +0:-1:4:NaN +1:-1:4:1 +2:-1:4:NaN +3:-1:4:3 +4:-1:4:NaN +-2:0:4:1 +-1:0:4:1 +0:0:4:1 +1:0:4:1 +2:0:4:1 +3:0:4:1 +4:0:4:1 +-2:1:4:2 +-1:1:4:3 +0:1:4:0 +1:1:4:1 +2:1:4:2 +3:1:4:3 +4:1:4:0 +-2:2:4:0 +-1:2:4:1 +0:2:4:0 +1:2:4:1 +2:2:4:0 +3:2:4:1 +4:2:4:0 +-2:3:4:0 +-1:3:4:3 +0:3:4:0 +1:3:4:1 +2:3:4:0 +3:3:4:3 +4:3:4:0 +-2:4:4:0 +-1:4:4:1 +0:4:4:0 +1:4:4:1 +2:4:4:0 +3:4:4:1 +4:4:4:0