[corelib BigInt] Fix implementation of BigInt.modInverse (fixes issue #37008).
A negative result was wrongly returned as a positive value.
Since positive values are preferred, the implementation now adds the modulus
enough times to make the result positive.
Change-Id: I87a2ceb359345846740a749ab6b46b1d45e7ba21
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/103664
Reviewed-by: Lasse R.H. Nielsen <lrn@google.com>
diff --git a/pkg/dev_compiler/tool/input_sdk/patch/core_patch.dart b/pkg/dev_compiler/tool/input_sdk/patch/core_patch.dart
index a8103b3..0524ed38 100644
--- a/pkg/dev_compiler/tool/input_sdk/patch/core_patch.dart
+++ b/pkg/dev_compiler/tool/input_sdk/patch/core_patch.dart
@@ -2316,6 +2316,7 @@
_rsh(uDigits, maxUsed, 1, uDigits);
if (ac) {
if (((aDigits[0] & 1) == 1) || ((bDigits[0] & 1) == 1)) {
+ // a += y
if (aIsNegative) {
if ((aDigits[maxUsed] != 0) ||
(_compareDigits(aDigits, maxUsed, yDigits, maxUsed)) > 0) {
@@ -2327,6 +2328,7 @@
} else {
_absAdd(aDigits, abcdUsed, yDigits, maxUsed, aDigits);
}
+ // b -= x
if (bIsNegative) {
_absAdd(bDigits, abcdUsed, xDigits, maxUsed, bDigits);
} else if ((bDigits[maxUsed] != 0) ||
@@ -2339,6 +2341,7 @@
}
_rsh(aDigits, abcdUsed, 1, aDigits);
} else if ((bDigits[0] & 1) == 1) {
+ // b -= x
if (bIsNegative) {
_absAdd(bDigits, abcdUsed, xDigits, maxUsed, bDigits);
} else if ((bDigits[maxUsed] != 0) ||
@@ -2355,6 +2358,7 @@
_rsh(vDigits, maxUsed, 1, vDigits);
if (ac) {
if (((cDigits[0] & 1) == 1) || ((dDigits[0] & 1) == 1)) {
+ // c += y
if (cIsNegative) {
if ((cDigits[maxUsed] != 0) ||
(_compareDigits(cDigits, maxUsed, yDigits, maxUsed) > 0)) {
@@ -2366,6 +2370,7 @@
} else {
_absAdd(cDigits, abcdUsed, yDigits, maxUsed, cDigits);
}
+ // d -= x
if (dIsNegative) {
_absAdd(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
} else if ((dDigits[maxUsed] != 0) ||
@@ -2378,6 +2383,7 @@
}
_rsh(cDigits, abcdUsed, 1, cDigits);
} else if ((dDigits[0] & 1) == 1) {
+ // d -= x
if (dIsNegative) {
_absAdd(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
} else if ((dDigits[maxUsed] != 0) ||
@@ -2391,8 +2397,10 @@
_rsh(dDigits, abcdUsed, 1, dDigits);
}
if (_compareDigits(uDigits, maxUsed, vDigits, maxUsed) >= 0) {
+ // u -= v
_absSub(uDigits, maxUsed, vDigits, maxUsed, uDigits);
if (ac) {
+ // a -= c
if (aIsNegative == cIsNegative) {
var a_cmp_c = _compareDigits(aDigits, abcdUsed, cDigits, abcdUsed);
if (a_cmp_c > 0) {
@@ -2405,6 +2413,7 @@
_absAdd(aDigits, abcdUsed, cDigits, abcdUsed, aDigits);
}
}
+ // b -= d
if (bIsNegative == dIsNegative) {
var b_cmp_d = _compareDigits(bDigits, abcdUsed, dDigits, abcdUsed);
if (b_cmp_d > 0) {
@@ -2417,8 +2426,10 @@
_absAdd(bDigits, abcdUsed, dDigits, abcdUsed, bDigits);
}
} else {
+ // v -= u
_absSub(vDigits, maxUsed, uDigits, maxUsed, vDigits);
if (ac) {
+ // c -= a
if (cIsNegative == aIsNegative) {
var c_cmp_a = _compareDigits(cDigits, abcdUsed, aDigits, abcdUsed);
if (c_cmp_a > 0) {
@@ -2431,6 +2442,7 @@
_absAdd(cDigits, abcdUsed, aDigits, abcdUsed, cDigits);
}
}
+ // d -= b
if (dIsNegative == bIsNegative) {
var d_cmp_b = _compareDigits(dDigits, abcdUsed, bDigits, abcdUsed);
if (d_cmp_b > 0) {
@@ -2462,25 +2474,18 @@
}
if (dIsNegative) {
- if ((dDigits[maxUsed] != 0) ||
+ while ((dDigits[maxUsed] != 0) ||
(_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
+ // d += x, d still negative
_absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
- if ((dDigits[maxUsed] != 0) ||
- (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
- _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
- } else {
- _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits);
- dIsNegative = false;
- }
- } else {
- _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits);
- dIsNegative = false;
}
- } else if ((dDigits[maxUsed] != 0) ||
- (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
- _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
- if ((dDigits[maxUsed] != 0) ||
- (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
+ // d += x
+ _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits);
+ dIsNegative = false;
+ } else {
+ while ((dDigits[maxUsed] != 0) ||
+ (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) >= 0)) {
+ // d -= x
_absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
}
}
diff --git a/runtime/lib/bigint_patch.dart b/runtime/lib/bigint_patch.dart
index 2046284..19c1919 100644
--- a/runtime/lib/bigint_patch.dart
+++ b/runtime/lib/bigint_patch.dart
@@ -1986,6 +1986,7 @@
_rsh(uDigits, maxUsed, 1, uDigits);
if (ac) {
if (((aDigits[0] & 1) == 1) || ((bDigits[0] & 1) == 1)) {
+ // a += y
if (aIsNegative) {
if ((aDigits[maxUsed] != 0) ||
(_compareDigits(aDigits, maxUsed, yDigits, maxUsed)) > 0) {
@@ -1997,6 +1998,7 @@
} else {
_absAdd(aDigits, abcdUsed, yDigits, maxUsed, aDigits);
}
+ // b -= x
if (bIsNegative) {
_absAdd(bDigits, abcdUsed, xDigits, maxUsed, bDigits);
} else if ((bDigits[maxUsed] != 0) ||
@@ -2009,6 +2011,7 @@
}
_rsh(aDigits, abcdUsed, 1, aDigits);
} else if ((bDigits[0] & 1) == 1) {
+ // b -= x
if (bIsNegative) {
_absAdd(bDigits, abcdUsed, xDigits, maxUsed, bDigits);
} else if ((bDigits[maxUsed] != 0) ||
@@ -2025,6 +2028,7 @@
_rsh(vDigits, maxUsed, 1, vDigits);
if (ac) {
if (((cDigits[0] & 1) == 1) || ((dDigits[0] & 1) == 1)) {
+ // c += y
if (cIsNegative) {
if ((cDigits[maxUsed] != 0) ||
(_compareDigits(cDigits, maxUsed, yDigits, maxUsed) > 0)) {
@@ -2036,6 +2040,7 @@
} else {
_absAdd(cDigits, abcdUsed, yDigits, maxUsed, cDigits);
}
+ // d -= x
if (dIsNegative) {
_absAdd(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
} else if ((dDigits[maxUsed] != 0) ||
@@ -2048,6 +2053,7 @@
}
_rsh(cDigits, abcdUsed, 1, cDigits);
} else if ((dDigits[0] & 1) == 1) {
+ // d -= x
if (dIsNegative) {
_absAdd(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
} else if ((dDigits[maxUsed] != 0) ||
@@ -2061,8 +2067,10 @@
_rsh(dDigits, abcdUsed, 1, dDigits);
}
if (_compareDigits(uDigits, maxUsed, vDigits, maxUsed) >= 0) {
+ // u -= v
_absSub(uDigits, maxUsed, vDigits, maxUsed, uDigits);
if (ac) {
+ // a -= c
if (aIsNegative == cIsNegative) {
var a_cmp_c = _compareDigits(aDigits, abcdUsed, cDigits, abcdUsed);
if (a_cmp_c > 0) {
@@ -2075,6 +2083,7 @@
_absAdd(aDigits, abcdUsed, cDigits, abcdUsed, aDigits);
}
}
+ // b -= d
if (bIsNegative == dIsNegative) {
var b_cmp_d = _compareDigits(bDigits, abcdUsed, dDigits, abcdUsed);
if (b_cmp_d > 0) {
@@ -2087,8 +2096,10 @@
_absAdd(bDigits, abcdUsed, dDigits, abcdUsed, bDigits);
}
} else {
+ // v -= u
_absSub(vDigits, maxUsed, uDigits, maxUsed, vDigits);
if (ac) {
+ // c -= a
if (cIsNegative == aIsNegative) {
var c_cmp_a = _compareDigits(cDigits, abcdUsed, aDigits, abcdUsed);
if (c_cmp_a > 0) {
@@ -2101,6 +2112,7 @@
_absAdd(cDigits, abcdUsed, aDigits, abcdUsed, cDigits);
}
}
+ // d -= b
if (dIsNegative == bIsNegative) {
var d_cmp_b = _compareDigits(dDigits, abcdUsed, bDigits, abcdUsed);
if (d_cmp_b > 0) {
@@ -2132,25 +2144,18 @@
}
if (dIsNegative) {
- if ((dDigits[maxUsed] != 0) ||
+ while ((dDigits[maxUsed] != 0) ||
(_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
+ // d += x, d still negative
_absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
- if ((dDigits[maxUsed] != 0) ||
- (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
- _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
- } else {
- _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits);
- dIsNegative = false;
- }
- } else {
- _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits);
- dIsNegative = false;
}
- } else if ((dDigits[maxUsed] != 0) ||
- (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
- _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
- if ((dDigits[maxUsed] != 0) ||
- (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
+ // d += x
+ _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits);
+ dIsNegative = false;
+ } else {
+ while ((dDigits[maxUsed] != 0) ||
+ (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) >= 0)) {
+ // d -= x
_absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
}
}
diff --git a/sdk/lib/_internal/js_runtime/lib/core_patch.dart b/sdk/lib/_internal/js_runtime/lib/core_patch.dart
index 998f42b..d0a1215 100644
--- a/sdk/lib/_internal/js_runtime/lib/core_patch.dart
+++ b/sdk/lib/_internal/js_runtime/lib/core_patch.dart
@@ -2352,6 +2352,7 @@
_rsh(uDigits, maxUsed, 1, uDigits);
if (ac) {
if (((aDigits[0] & 1) == 1) || ((bDigits[0] & 1) == 1)) {
+ // a += y
if (aIsNegative) {
if ((aDigits[maxUsed] != 0) ||
(_compareDigits(aDigits, maxUsed, yDigits, maxUsed)) > 0) {
@@ -2363,6 +2364,7 @@
} else {
_absAdd(aDigits, abcdUsed, yDigits, maxUsed, aDigits);
}
+ // b -= x
if (bIsNegative) {
_absAdd(bDigits, abcdUsed, xDigits, maxUsed, bDigits);
} else if ((bDigits[maxUsed] != 0) ||
@@ -2375,6 +2377,7 @@
}
_rsh(aDigits, abcdUsed, 1, aDigits);
} else if ((bDigits[0] & 1) == 1) {
+ // b -= x
if (bIsNegative) {
_absAdd(bDigits, abcdUsed, xDigits, maxUsed, bDigits);
} else if ((bDigits[maxUsed] != 0) ||
@@ -2391,6 +2394,7 @@
_rsh(vDigits, maxUsed, 1, vDigits);
if (ac) {
if (((cDigits[0] & 1) == 1) || ((dDigits[0] & 1) == 1)) {
+ // c += y
if (cIsNegative) {
if ((cDigits[maxUsed] != 0) ||
(_compareDigits(cDigits, maxUsed, yDigits, maxUsed) > 0)) {
@@ -2402,6 +2406,7 @@
} else {
_absAdd(cDigits, abcdUsed, yDigits, maxUsed, cDigits);
}
+ // d -= x
if (dIsNegative) {
_absAdd(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
} else if ((dDigits[maxUsed] != 0) ||
@@ -2414,6 +2419,7 @@
}
_rsh(cDigits, abcdUsed, 1, cDigits);
} else if ((dDigits[0] & 1) == 1) {
+ // d -= x
if (dIsNegative) {
_absAdd(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
} else if ((dDigits[maxUsed] != 0) ||
@@ -2427,8 +2433,10 @@
_rsh(dDigits, abcdUsed, 1, dDigits);
}
if (_compareDigits(uDigits, maxUsed, vDigits, maxUsed) >= 0) {
+ // u -= v
_absSub(uDigits, maxUsed, vDigits, maxUsed, uDigits);
if (ac) {
+ // a -= c
if (aIsNegative == cIsNegative) {
var a_cmp_c = _compareDigits(aDigits, abcdUsed, cDigits, abcdUsed);
if (a_cmp_c > 0) {
@@ -2441,6 +2449,7 @@
_absAdd(aDigits, abcdUsed, cDigits, abcdUsed, aDigits);
}
}
+ // b -= d
if (bIsNegative == dIsNegative) {
var b_cmp_d = _compareDigits(bDigits, abcdUsed, dDigits, abcdUsed);
if (b_cmp_d > 0) {
@@ -2453,8 +2462,10 @@
_absAdd(bDigits, abcdUsed, dDigits, abcdUsed, bDigits);
}
} else {
+ // v -= u
_absSub(vDigits, maxUsed, uDigits, maxUsed, vDigits);
if (ac) {
+ // c -= a
if (cIsNegative == aIsNegative) {
var c_cmp_a = _compareDigits(cDigits, abcdUsed, aDigits, abcdUsed);
if (c_cmp_a > 0) {
@@ -2467,6 +2478,7 @@
_absAdd(cDigits, abcdUsed, aDigits, abcdUsed, cDigits);
}
}
+ // d -= b
if (dIsNegative == bIsNegative) {
var d_cmp_b = _compareDigits(dDigits, abcdUsed, bDigits, abcdUsed);
if (d_cmp_b > 0) {
@@ -2498,25 +2510,18 @@
}
if (dIsNegative) {
- if ((dDigits[maxUsed] != 0) ||
+ while ((dDigits[maxUsed] != 0) ||
(_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
+ // d += x, d still negative
_absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
- if ((dDigits[maxUsed] != 0) ||
- (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
- _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
- } else {
- _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits);
- dIsNegative = false;
- }
- } else {
- _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits);
- dIsNegative = false;
}
- } else if ((dDigits[maxUsed] != 0) ||
- (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
- _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
- if ((dDigits[maxUsed] != 0) ||
- (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) {
+ // d += x
+ _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits);
+ dIsNegative = false;
+ } else {
+ while ((dDigits[maxUsed] != 0) ||
+ (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) >= 0)) {
+ // d -= x
_absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits);
}
}
diff --git a/tests/corelib_2/bigint_test.dart b/tests/corelib_2/bigint_test.dart
index 01dea1f..0b5b8c5 100644
--- a/tests/corelib_2/bigint_test.dart
+++ b/tests/corelib_2/bigint_test.dart
@@ -222,6 +222,15 @@
test(mediumNumber, new BigInt.from(137), new BigInt.from(77));
test(new BigInt.from(137), mediumNumber, new BigInt.from(540686667207353));
test(bigNumber, new BigInt.from(137), new BigInt.from(128));
+ var x = BigInt.parse(
+ "28ea16430c1f1072754aa5ebbfda0d790605a507c6c9758e88697b0b5dd9e74c",
+ radix: 16);
+ var m = BigInt.parse(
+ "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f",
+ radix: 16);
+ var r = BigInt.parse("95929095851002583825372225918533539673793386278"
+ "360575987103577151530201707061", radix: 10);
+ test(x, m, r);
}
testGcd() {
