Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(652)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: runtime/lib/bigint.dart

Issue 1188843004: Implement modInverse for an even modulus. (Closed) Base URL: git@github.com:dart-lang/sdk.git@master
Patch Set: Created 5 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | runtime/lib/integers.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: runtime/lib/bigint.dart
diff --git a/runtime/lib/bigint.dart b/runtime/lib/bigint.dart
index 27c27fa7157c0d374036dc8206613aa0b030048f..04b85b7d4d5610fe8edbf480bbe1f2f83d85fa31 100644
--- a/runtime/lib/bigint.dart
+++ b/runtime/lib/bigint.dart
@@ -1542,100 +1542,210 @@ class _Bigint extends _IntegerImplementation implements int {
int modInverse(int m) {
if (m is! int) throw new ArgumentError(m);
if (m <= 0) throw new RangeError(m);
- if (_used == 0) return 0;
+ if (m == 1) return 0;
m = m._toBigint();
- // TODO(regis): Implement modInverse for an even modulus.
- if (m.isEven) throw new UnimplementedError();
var t = this;
- if ((t._compare(m) >= 0) || t._neg) {
+ if (t._neg || (t._absCompare(m) >= 0)) {
t %= m;
t = t._toBigint();
}
+ final bool ac = m.isEven;
final t_used = t._used;
- if (t_used == 0) {
- return 0; // No inverse.
- }
+ if ((t_used == 1) && (t._digits[0] == 1)) return 1;
+ if ((t_used == 0) || (ac && t.isEven)) throw new RangeError("Not coprime");
final m_digits = m._digits;
final m_used = m._used;
- final uv_len = m_used + (m_used & 1);
- var v_digits = _cloneDigits(t._digits, 0, t_used, uv_len);
- var u_digits = _cloneDigits(m_digits, 0, m_used, uv_len);
-
- // Variables b and d require one more digit for carry.
- final bd_used = m_used + 1;
- final bd_len = bd_used + (bd_used & 1);
- var b_digits = new Uint32List(bd_len);
- var d_digits = new Uint32List(bd_len);
- bool b_neg = false;
- bool d_neg = false;
-
+ final tuv_len = m_used + (m_used & 1);
+ final t_digits = _cloneDigits(t._digits, 0, t_used, tuv_len);
+ var u_digits = _cloneDigits(m_digits, 0, m_used, tuv_len);
+ var v_digits = _cloneDigits(t_digits, 0, t_used, tuv_len);
+
+ // Variables a, b, c, and d require one more digit.
+ final abcd_used = m_used + 1;
+ final abcd_len = abcd_used + (abcd_used & 1) + 2; // +2 to satisfy _absAdd.
+ var a_digits, b_digits, c_digits, d_digits;
+ bool a_neg, b_neg, c_neg, d_neg;
+ if (ac) {
+ a_digits = new Uint32List(abcd_len);
+ a_neg = false;
+ a_digits[0] = 1;
+ c_digits = new Uint32List(abcd_len);
+ c_neg = false;
+ }
+ b_digits = new Uint32List(abcd_len);
+ b_neg = false;
+ d_digits = new Uint32List(abcd_len);
+ d_neg = false;
d_digits[0] = 1;
while (true) {
while ((u_digits[0] & 1) == 0) {
_rsh(u_digits, m_used, 1, u_digits);
- if ((b_digits[0] & 1) == 1) {
- _absSub(m_digits, m_used, b_digits, m_used, b_digits);
- b_neg = !b_neg;
+ if (ac) {
+ if (((a_digits[0] & 1) == 1) || ((b_digits[0] & 1) == 1)) {
+ if (a_neg) {
+ if ((a_digits[m_used] != 0) ||
+ (_compareDigits(a_digits, m_used, t_digits, m_used)) > 0) {
+ _absSub(a_digits, abcd_used, t_digits, m_used, a_digits);
+ } else {
+ _absSub(t_digits, m_used, a_digits, m_used, a_digits);
+ a_neg = false;
+ }
+ } else {
+ _absAdd(a_digits, abcd_used, t_digits, m_used, a_digits);
+ }
+ if (b_neg) {
+ _absAdd(b_digits, abcd_used, m_digits, m_used, b_digits);
+ } else if ((b_digits[m_used] != 0) ||
+ (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(b_digits, abcd_used, m_digits, m_used, b_digits);
+ } else {
+ _absSub(m_digits, m_used, b_digits, m_used, b_digits);
+ b_neg = true;
+ }
+ }
+ _rsh(a_digits, abcd_used, 1, a_digits);
+ } else if ((b_digits[0] & 1) == 1) {
+ if (b_neg) {
+ _absAdd(b_digits, abcd_used, m_digits, m_used, b_digits);
+ } else if ((b_digits[m_used] != 0) ||
+ (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(b_digits, abcd_used, m_digits, m_used, b_digits);
+ } else {
+ _absSub(m_digits, m_used, b_digits, m_used, b_digits);
+ b_neg = true;
+ }
}
- _rsh(b_digits, m_used, 1, b_digits);
+ _rsh(b_digits, abcd_used, 1, b_digits);
}
while ((v_digits[0] & 1) == 0) {
_rsh(v_digits, m_used, 1, v_digits);
- if ((d_digits[0] & 1) == 1) {
- _absSub(m_digits, m_used, d_digits, m_used, d_digits);
- d_neg = !d_neg;
+ if (ac) {
+ if (((c_digits[0] & 1) == 1) || ((d_digits[0] & 1) == 1)) {
+ if (c_neg) {
+ if ((c_digits[m_used] != 0) ||
+ (_compareDigits(c_digits, m_used, t_digits, m_used) > 0)) {
+ _absSub(c_digits, abcd_used, t_digits, m_used, c_digits);
+ } else {
+ _absSub(t_digits, m_used, c_digits, m_used, c_digits);
+ c_neg = false;
+ }
+ } else {
+ _absAdd(c_digits, abcd_used, t_digits, m_used, c_digits);
+ }
+ if (d_neg) {
+ _absAdd(d_digits, abcd_used, m_digits, m_used, d_digits);
+ } else if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ } else {
+ _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ d_neg = true;
+ }
+ }
+ _rsh(c_digits, abcd_used, 1, c_digits);
+ } else if ((d_digits[0] & 1) == 1) {
+ if (d_neg) {
+ _absAdd(d_digits, abcd_used, m_digits, m_used, d_digits);
+ } else if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ } else {
+ _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ d_neg = true;
+ }
}
- _rsh(d_digits, m_used, 1, d_digits);
+ _rsh(d_digits, abcd_used, 1, d_digits);
}
if (_compareDigits(u_digits, m_used, v_digits, m_used) >= 0) {
_absSub(u_digits, m_used, v_digits, m_used, u_digits);
+ if (ac) {
+ if (a_neg == c_neg) {
+ var a_cmp_c =
+ _compareDigits(a_digits, abcd_used, c_digits, abcd_used);
+ if (a_cmp_c > 0) {
+ _absSub(a_digits, abcd_used, c_digits, abcd_used, a_digits);
+ } else {
+ _absSub(c_digits, abcd_used, a_digits, abcd_used, a_digits);
+ a_neg = !a_neg && (a_cmp_c != 0);
+ }
+ } else {
+ _absAdd(a_digits, abcd_used, c_digits, abcd_used, a_digits);
+ }
+ }
if (b_neg == d_neg) {
- if (_compareDigits(b_digits, m_used, d_digits, m_used) >= 0) {
- _absSub(b_digits, m_used, d_digits, m_used, b_digits);
+ var b_cmp_d =
+ _compareDigits(b_digits, abcd_used, d_digits, abcd_used);
+ if (b_cmp_d > 0) {
+ _absSub(b_digits, abcd_used, d_digits, abcd_used, b_digits);
} else {
- _absSub(d_digits, m_used, b_digits, m_used, b_digits);
- b_neg = !b_neg;
+ _absSub(d_digits, abcd_used, b_digits, abcd_used, b_digits);
+ b_neg = !b_neg && (b_cmp_d != 0);
}
} else {
- _absAdd(b_digits, m_used, d_digits, m_used, b_digits);
- if ((b_digits[m_used] > 0) ||
- (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
- _absSub(b_digits, bd_used, m_digits, m_used, b_digits);
- }
+ _absAdd(b_digits, abcd_used, d_digits, abcd_used, b_digits);
}
} else {
_absSub(v_digits, m_used, u_digits, m_used, v_digits);
- if (b_neg == d_neg) {
- if (_compareDigits(d_digits, m_used, b_digits, m_used) >= 0) {
- _absSub(d_digits, m_used, b_digits, m_used, d_digits);
+ if (ac) {
+ if (c_neg == a_neg) {
+ var c_cmp_a =
+ _compareDigits(c_digits, abcd_used, a_digits, abcd_used);
+ if (c_cmp_a > 0) {
+ _absSub(c_digits, abcd_used, a_digits, abcd_used, c_digits);
+ } else {
+ _absSub(a_digits, abcd_used, c_digits, abcd_used, c_digits);
+ c_neg = !c_neg && (c_cmp_a != 0);
+ }
} else {
- _absSub(b_digits, m_used, d_digits, m_used, d_digits);
- d_neg = !d_neg;
+ _absAdd(c_digits, abcd_used, a_digits, abcd_used, c_digits);
}
- } else {
- _absAdd(d_digits, m_used, b_digits, m_used, d_digits);
- if ((d_digits[m_used] > 0) ||
- (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
- _absSub(d_digits, bd_used, m_digits, m_used, d_digits);
+ }
+ if (d_neg == b_neg) {
+ var d_cmp_b =
+ _compareDigits(d_digits, abcd_used, b_digits, abcd_used);
+ if (d_cmp_b > 0) {
+ _absSub(d_digits, abcd_used, b_digits, abcd_used, d_digits);
+ } else {
+ _absSub(b_digits, abcd_used, d_digits, abcd_used, d_digits);
+ d_neg = !d_neg && (d_cmp_ab != 0);
}
+ } else {
+ _absAdd(d_digits, abcd_used, b_digits, abcd_used, d_digits);
}
}
// Exit loop if u == 0.
var i = m_used;
- while ((i > 0) && (u_digits[i - 1] == 0)) {
- --i;
- }
+ while ((i > 0) && (u_digits[i - 1] == 0)) --i;
if (i == 0) break;
}
// No inverse if v != 1.
- for (var i = m_used - 1; i > 0; --i) {
- if (v_digits[i] != 0) return 0; // No inverse.
- }
- if (v_digits[0] != 1) return 0; // No inverse.
+ var i = m_used - 1;
+ while ((i > 0) && (v_digits[i] == 0)) --i;
+ if ((i != 0) || (v_digits[0] != 1)) throw new RangeError("Not coprime");
if (d_neg) {
- _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ } else {
+ _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ d_neg = false;
+ }
+ } else {
+ _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ d_neg = false;
+ }
+ } else if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ }
}
return new _Bigint(false, m_used, d_digits)._toValidInt();
}
« no previous file with comments | « no previous file | runtime/lib/integers.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698