commit e62dd0157e2b0725cb464c34b4622a02aaa954fd
author Régis Crelier <regis@google.com> Mon May 07 21:38:30 2018 +0000
committer Régis Crelier <regis@google.com> Mon May 07 21:38:30 2018 +0000
tree bc9eca370357a79e9533f157d100363d4c49235f
parent 8515d74332968cd0aa27d175fbdcd77120a36b90

[VM bigint] Fix padding length in Montgomery Reduction (fixes #32626).
Add regression test to existing bigint test.

Change-Id: I9e470c4002c25493285ce6bb908375ff913a4e17
Reviewed-on: https://dart-review.googlesource.com/54070
Reviewed-by: Alexander Markov <alexmarkov@google.com>

runtime/lib/bigint_patch.dart

diff --git a/runtime/lib/bigint_patch.dart b/runtime/lib/bigint_patch.dart
index 7516712..0b0cd0f 100644
--- a/runtime/lib/bigint_patch.dart
+++ b/runtime/lib/bigint_patch.dart
@@ -2628,7 +2628,8 @@
   }
 
   _BigIntImpl _revert(Uint32List xDigits, int xUsed) {
-    var resultDigits = _newDigits(2 * _normModulusUsed);
+    // Reserve enough digits for modulus squaring and accumulator carry.
+    var resultDigits = _newDigits(2 * _normModulusUsed + 2);
     var i = xUsed + (xUsed & 1);
     while (--i >= 0) {
       resultDigits[i] = xDigits[i];
@@ -2640,8 +2641,8 @@
   // x = x/R mod _modulus.
   // Returns xUsed.
   int _reduce(Uint32List xDigits, int xUsed) {
-    while (xUsed < 2 * _normModulusUsed) {
-      // Pad x so _mulAdd has enough room later.
+    while (xUsed < 2 * _normModulusUsed + 2) {
+      // Pad x so _mulAdd has enough room later for a possible carry.
       xDigits[xUsed++] = 0;
     }
     var i = 0;

tests/corelib_2/bigint_test.dart

diff --git a/tests/corelib_2/bigint_test.dart b/tests/corelib_2/bigint_test.dart
index e6845d0..290e477 100644
--- a/tests/corelib_2/bigint_test.dart
+++ b/tests/corelib_2/bigint_test.dart
@@ -484,6 +484,29 @@
   e = BigInt.parse("123456789012345678901234567890");
   m = BigInt.parse("123456789012345678901234567899");
   Expect.equals(BigInt.parse("40128068573873018143207285483"), x.modPow(e, m));
+  x = BigInt.parse(
+      "142223781135477974841804437037182877109549636480215350570761436386728140"
+      "00321219503871352719175100865184619168128345594681547640115731246638");
+  e = BigInt.parse(
+      "688057170495263083245752731085731160016625265771524738691797062279575950"
+      "919479651156310413084174304361991240273181430924411258203766946639349880"
+      "404106504114953688890200429043051936362182997575167191584461538746041795"
+      "019663740246921124383173799957296515067912829778249931473903780958741032"
+      "64534184571632120755");
+  m = BigInt.parse(
+      "144173682842817587002196172066264549138375068078359231382946906898412792"
+      "452632726597279520229873489736777248181678202636100459215718497240474064"
+      "366927544074501134727745837254834206456400508719134610847814227274992298"
+      "238973375146473350157304285346424982280927848339601514720098577525635486"
+      "320547905945936448443");
+  Expect.equals(
+      BigInt.parse(
+          "41228476947144730491819644448449646627743926889389391986712371102685"
+          "14984467753960109321610008533258676279344318597060690521027646613453"
+          "25674994677820913027869835916005689276806408148698486814119894325284"
+          "18918299321385420296108046942018595594076729397423805685944237555128"
+          "652606412065971965116137839721723231"),
+      x.modPow(e, m));
 }
 
 testBigintModInverse() {