Implement modInverse (bigint version does not support even modulus yet).

Implement modInverse (bigint version does not support even modulus yet).
Added tests.

See #23502

R=srdjan@google.com

Committed: https://github.com/dart-lang/sdk/commit/f6f338ce67eb8801b350417baacf6d3681b26002

[regis, 2015-06-09 23:22:34]

regis@google.com changed reviewers:
+ srdjan@google.com

[regis, 2015-06-09 23:22:35]

Either we submit this version or we wait until I provide a bigint version
supporting an even modulus. My understanding is that the modulus will always be
odd in cryptographic applications.

I do not have a version to compare with in order to judge its speed. DGLogik
could weigh in. This is their version slightly modified and optimized.

Thanks,
Regis

[srdjan, 2015-06-10 16:51:52]

Please measure the improvement of using bigint optimized code vs the naive code
used for non-bigints.

I think we need handling for even modulus as well, but it should be OK to submit
now with support for odd modulus.

https://codereview.chromium.org/1174513004/diff/20001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/1174513004/diff/20001/runtime/lib/bigint.dart...
runtime/lib/bigint.dart:1547: if (m.isEven) return 0;
Maybe throw unimplemented instead of returning 0.

[srdjan, 2015-06-10 17:46:07]

https://codereview.chromium.org/1174513004/diff/20001/sdk/lib/core/int.dart
File sdk/lib/core/int.dart (right):

https://codereview.chromium.org/1174513004/diff/20001/sdk/lib/core/int.dart#n...
sdk/lib/core/int.dart:120: int modInverse(int modulus);
You probably also need to add it to
sdk/lib/_internal/compiler/js_lib/js_number.dart

[regis, 2015-06-10 20:25:56]

PTAL

I have measured this test loop (ReleaseX64) using both the bigint implementation
(in bigint.dart) and the integer implementation (in integers.dart not
dispatching to bigint):

  int count = 10000;
  int m =
142794791369857893518216846152178512365742893193381905408671045383524196038880042688222484665321416966726996826180091369625084659347039997384427839884481875048370565094771341455209579084576003589416828973425288956690619644847967193297411322186095969144940769802524422661706293551748267739368517289465924234003;
  for (int i = 1; i < count; ++i) {
    int v = i.modInverse(m);
    Expect.equals(1, v*i % m);
  }

bigint: 1119ms
int:    8522ms

Thanks,
Regis

https://codereview.chromium.org/1174513004/diff/20001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/1174513004/diff/20001/runtime/lib/bigint.dart...
runtime/lib/bigint.dart:1547: if (m.isEven) return 0;
On 2015/06/10 16:51:52, srdjan wrote:
> Maybe throw unimplemented instead of returning 0.

Done.

https://codereview.chromium.org/1174513004/diff/20001/sdk/lib/core/int.dart
File sdk/lib/core/int.dart (right):

https://codereview.chromium.org/1174513004/diff/20001/sdk/lib/core/int.dart#n...
sdk/lib/core/int.dart:120: int modInverse(int modulus);
On 2015/06/10 17:46:06, srdjan wrote:
> You probably also need to add it to
> sdk/lib/_internal/compiler/js_lib/js_number.dart

Thank for the pointer! Done.

[srdjan, 2015-06-10 21:59:10]

lgtm

[regis, 2015-06-10 22:01:51]

Committed patchset #3 (id:40001) manually as
f6f338ce67eb8801b350417baacf6d3681b26002 (presubmit successful).

[kevmoo, 2015-06-23 20:54:08]

On 2015/06/10 22:01:51, regis wrote:
> Committed patchset #3 (id:40001) manually as
> f6f338ce67eb8801b350417baacf6d3681b26002 (presubmit successful).

Please update CHANGELOG.md when making API changes