Skip Menu |
 

This queue is for tickets about the Math-BigInt CPAN distribution.

Report information
The Basics
Id: 63237
Status: resolved
Priority: 0/
Queue: Math-BigInt

People
Owner: Nobody in particular
Requestors: mhasch-cpanbugs [...] cozap.com
Cc:
AdminCc:

Bug Information
Severity: Important
Broken in: 1.99
Fixed in: (no value)



Subject: [PATCH] issues with bmodinv and bmodpow in Math-BigInt-1.99
MIME-Version: 1.0
X-Mailer: MIME-tools 5.427 (Entity 5.427)
X-RT-Original-Encoding: utf-8
Content-Type: multipart/mixed; boundary="----------=_1290449941-2358-437"
Content-Length: 0
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline
Content-Transfer-Encoding: binary
Content-Length: 842
Download (untitled) / with headers
text/plain 842b
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
Subject: mbi-1.99-modulo-issues-fix.patch
MIME-Version: 1.0
Content-Type: text/x-patch; name="mbi-1.99-modulo-issues-fix.patch"
X-Mailer: MIME-tools 5.427 (Entity 5.427)
Content-Disposition: inline; filename="mbi-1.99-modulo-issues-fix.patch"
Content-Transfer-Encoding: binary
Content-Length: 1408
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;
Subject: mbi-1.99-modulo-issues-check.patch
MIME-Version: 1.0
Content-Type: text/x-patch; name="mbi-1.99-modulo-issues-check.patch"
X-Mailer: MIME-tools 5.427 (Entity 5.427)
Content-Disposition: inline; filename="mbi-1.99-modulo-issues-check.patch"
Content-Transfer-Encoding: binary
Content-Length: 1903
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
MIME-Version: 1.0
X-Mailer: MIME-tools 5.427 (Entity 5.427)
Content-Disposition: inline
Content-Type: text/plain; charset="UTF-8"
Message-ID: <rt-3.8.HEAD-2356-1290501019-1454.63237-0-0 [...] rt.cpan.org>
Content-Transfer-Encoding: binary
X-RT-Original-Encoding: utf-8
Content-Length: 1171
Download (untitled) / with headers
text/plain 1.1k
I spotted and fixed this bug a day or two after I introduced it: https://github.com/pjacklam/Math-BigInt/commit/ca5c24f7bc2b27eaf8095b8a1b9dad1a5cca55f8 but I guess Florian (FLORA) hasn't had time to review it and merge it. As far as your comment "I suggest to look at border cases involving modular arithmetic again, with a bit more thoroughness." goes, you ought to look at the bugs I have submitted recently and also compare the old code with my new code. I working hard to find and fix buggy and inconsistent handling of border cases. While not everything is perfect yet, I believe there is at least a trend that Math-BigInt now is moving in the right direction. My aim is also to fix the bugs that have been open for years. One of the problems is that the old code is highly optimized for speed, not correctness or readability, which makes bug fixing hard. In my new code, I try to document extensively and include the mathematical formulas which are underlying the code. In addition, the old test suit is limited, and not (yet) able to catch existing bugs nor newly introduced ones. I will probably release Math-BigInt-1.991 in near future unless Florian does.
MIME-Version: 1.0
X-Mailer: MIME-tools 5.427 (Entity 5.427)
Content-Disposition: inline
Content-Type: text/plain; charset="UTF-8"
Message-ID: <rt-3.8.HEAD-19311-1295352483-1006.63237-0-0 [...] rt.cpan.org>
Content-Transfer-Encoding: binary
X-RT-Original-Encoding: utf-8
Content-Length: 201
Download (untitled) / with headers
text/plain 201b
MIME-Version: 1.0
In-Reply-To: <rt-3.8.HEAD-19311-1295352483-1006.63237-0-0 [...] rt.cpan.org>
X-Mailer: MIME-tools 5.427 (Entity 5.427)
Content-Disposition: inline
References: <rt-3.8.HEAD-19311-1295352483-1006.63237-0-0 [...] rt.cpan.org>
Content-Type: text/plain; charset="UTF-8"
Message-ID: <rt-3.8.HEAD-19315-1295548478-765.63237-0-0 [...] rt.cpan.org>
Content-Transfer-Encoding: binary
X-RT-Original-Encoding: utf-8
Content-Length: 54
Status should be "patched" until a new release is out.
MIME-Version: 1.0
X-Mailer: MIME-tools 5.427 (Entity 5.427)
Content-Disposition: inline
Content-Type: text/plain; charset="UTF-8"
Message-ID: <rt-3.8.HEAD-17550-1297199909-704.63237-0-0 [...] rt.cpan.org>
Content-Transfer-Encoding: binary
X-RT-Original-Encoding: utf-8
Content-Length: 27
Fixed in Math-BigInt-1.991.


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.