Description: ------------ This code becomes 0 only at MATH_BIGINTEGER_MODE_INTERNAL. Test script: --------------- <?php require_once 'Math_BigInteger.php'; $u1 = "55710793074732015987174053664625912300054717442"; $p = "11671236708387678327224206536086899180337891539414163231548040398520841845883184000627860280911468857014406210406182985401875818712804278750455023001090753"; $g = "8390523802553664927497849579280285206671739131891639945934584937465879937204060160958306281843225586442674344146773393578506632957361175802992793531760152"; $b_g = new Math_BigInteger($g); $b_u1 = new Math_BigInteger($u1); $b_p = new Math_BigInteger($p); $result = $b_g->modPow($b_u1, $b_p); var_dump($result->toString()); ?> Expected result: ---------------- MATH_BIGINTEGER_MODE_BCMATH : 8937694487957402259906020926707526536305372570669547798011738379130571226312340600613787287362059992019784710653252012225247381040474199119941769440709823 MATH_BIGINTEGER_MODE_GMP : 8937694487957402259906020926707526536305372570669547798011738379130571226312340600613787287362059992019784710653252012225247381040474199119941769440709823 MATH_BIGINTEGER_MODE_INTERNAL : 8937694487957402259906020926707526536305372570669547798011738379130571226312340600613787287362059992019784710653252012225247381040474199119941769440709823 Actual result: -------------- MATH_BIGINTEGER_MODE_BCMATH : 8937694487957402259906020926707526536305372570669547798011738379130571226312340600613787287362059992019784710653252012225247381040474199119941769440709823 MATH_BIGINTEGER_MODE_GMP : 8937694487957402259906020926707526536305372570669547798011738379130571226312340600613787287362059992019784710653252012225247381040474199119941769440709823 MATH_BIGINTEGER_MODE_INTERNAL : 0

Not enough information was provided for us to be able to handle this bug. Please re-read the instructions at http://bugs.php.net/how-to-report.php If you can provide more information, feel free to add it to this bug and change the status back to "Open". Thank you for your interest in PEAR. On line 1105 (see the following URL), in the _slidingWindow function, there's a for loop whose "while" condition is "$i >= 1". Try changing this to "$i >= 0" and let me know if it fixes the issue. http://cvs.php.net/viewvc.cgi/pear/Math_BigInteger/Math_BigInteger.php?annotate=1.6#l1105

>Not enough information was provided for us to be able to handle this bug. OK. I wrote phpt tests(http://qa.php.net/write-test.php) for Math_BigInteger. Please execute these phpt. verify_internal.phpt is fail. I think that I return the result as which any MODE is the same. Archive: http://project-p.jp/halt/archives/Math_BigInteger_tests.tgz How to use phpt: tar -zxvf tests.tgz pear run-tests ./tests Scripts: verify_bcmath.phpt: --TEST-- modPow test using bcmath --FILE-- <?php $GLOBALS['type'] = 'bcmath'; require_once dirname(__FILE__) . '/verify_lib.php'; ?> --EXPECT-- string(154) "8937694487957402259906020926707526536305372570669547798011738379130571226312340600613787287362059992019784710653252012225247381040474199119941769440709823" verify_gmp.phpt: --TEST-- modPow test using gmp --FILE-- <?php $GLOBALS['type'] = 'gmp'; require_once dirname(__FILE__) . '/verify_lib.php'; ?> --EXPECT-- string(154) "8937694487957402259906020926707526536305372570669547798011738379130571226312340600613787287362059992019784710653252012225247381040474199119941769440709823" verify_internal.phpt: --TEST-- modPow test using internal(Pure PHP) --FILE-- <?php $GLOBALS['type'] = 'internal'; require_once dirname(__FILE__) . '/verify_lib.php'; ?> --EXPECT-- string(154) "8937694487957402259906020926707526536305372570669547798011738379130571226312340600613787287362059992019784710653252012225247381040474199119941769440709823" verify_lib.php: <?php /** * not work modPow in MATH_BIGINTEGER_MODE_INTERNAL * */ require_once 'Math_BigInteger.php'; //require_once 'Math_BigInteger_cvs.php'; //set Math_BigInterger mode from $GLOBALS['type'] if (!defined('MATH_BIGINTEGER_MODE')) { switch($GLOBALS['type']) { case 'gmp': define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_GMP); break; case 'bcmath': define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_BCMATH); break; case 'internal': define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_INTERNAL); break; } } $u1 = "55710793074732015987174053664625912300054717442"; $p = "11671236708387678327224206536086899180337891539414163231548040398520841845883184000627860280911468857014406210406182985401875818712804278750455023001090753"; $g = "8390523802553664927497849579280285206671739131891639945934584937465879937204060160958306281843225586442674344146773393578506632957361175802992793531760152"; $b_g = new Math_BigInteger($g); $b_u1 = new Math_BigInteger($u1); $b_p = new Math_BigInteger($p); $result = $b_g->modPow($b_u1, $b_p); var_dump($result->toString()); ?>

Thank you for taking the time to report a problem with the package. This problem may have been already fixed by a previous change that is in the CVS of the package. Please log into CVS with: cvs -d :pserver:cvsread@cvs.php.net:/repository login and check out the CVS repository of this package and upgrade cvs -d :pserver:cvsread@cvs.php.net:/repository co pear/Math_BigInteger pear upgrade pear/Math_BigInteger/package2.xml or pear upgrade pear/Math_BigInteger/package.xml If you are able to reproduce the bug with the latest CVS, please change the status back to "Open". Again, thank you for your continued support of PEAR. You actually provided enough information in your first post. What I meant when I selected the "Not enough info" option was that I was hoping you could confirm whether or not the fix I proposed worked. I didn't realize it'd auto-add two extra paragraphs to my comments. Anyway, I've committed what I believe is the solution to CVS. If you could confirm that that works (by downloading the latest CVS), that'd be great! :) I also wasn't able to duplicate your problem exactly. MATH_BIGINTEGER_MODE_INTERNAL gave me erroneous output, but it didn't give me 0. This is why I was sorta hoping you could confirm the fix before I committed it.

I can also reproduce this. The fix did not solve it. Changing MATH_BIGINTEGER_MONTGOMERY in this fragment: if ( $n->value[0] & 1 ) { return $this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY); } to either MATH_BIGINTEGER_BARRETT or MATH_BIGINTEGER_CLASSIC fixes the problem, though.

Sorry, I should have said 'makes it return the correct result' rather than 'fixes the problem'. Of course I'm not saying that's a fix, just a diagnosis.

The problem seems to come from _modInverse67108864(). This function returns 0 with argument 50019009 instead of the proper value which is 55290559. The cause appears to be related to some kind of overflow in the last step, namely this line: $result = ($result * (2 - ((($x & 0x3FFFFFF) * $result) & 0x3FFFFFF))) & 0x3FFFFFF; Adding an extra modulus after the subtraction step seems to solve the problem for this case: $result = ($result * ((2 - ((($x & 0x3FFFFFF) * $result) & 0x3FFFFFF)) & 0x3FFFFFF)) & 0x3FFFFFF; // x^-1 mod 2^26 I can't promise it will work for all cases, though. Working that close to the numerical limits can trigger compiler bugs, inconsistent (even if standards-compliant) behaviour, etc. (indeed the fact that Jim can't reproduce this bug may be related to the compiler used for building PHP).

Thanks for that! I'll try to examine the problem in more depth, this weekend, and see what I can do about it :)

Try it in CVS, now!

This bug has been fixed in CVS. If this was a documentation problem, the fix will appear on pear.php.net by the end of next Sunday (CET). If this was a problem with the pear.php.net website, the change should be live shortly. Otherwise, the fix will appear in the package's next release. Thank you for the report and for helping us make PEAR better. Well, based on some emails that I and Pedro Gimeno exchanged, I think this is fixed. The comments of the latest CVS elaborate (specifically, the comments of the _modInverse67... function).