need native modInverse and powMod function for big integer

[rinick]

What steps will reproduce the problem?

this is a dart file which I implemented modeInverse function with native dart big int
https://gist.github.com/rinick/9f1f285dc1e2a18d2d75

this is a java file that's doing the same thing, except it's using the builtin java modInverse function.
https://gist.github.com/samrg472/8f0bae6d291ef2bc2b95

What is the expected output? What do you see instead?

it takes 650ms to run the java on my pc, and about 8 seconds to run the dart version (11 seconds in checked mode)

To make dart's native big integer really usable for cryptography purpose, I think it's necessary to have these functions implemented in dartvm. not in dart code:
modInverse, powMod, gcd. it would also be nice if toByteArray and fromByteArray can be implemented too.

[rinick]

sorry about the typo, it's modInverse not modeInverse.

[sethladd]

Added Area-VM, C13, Triaged labels.

[iposva-google]

Have you tried using the modPow function in int? See https://api.dartlang.org/apidocs/channels/stable/dartdoc-viewer/dart:core.int#id_modPow

[a-siva]

cc @sgmitrovic.
cc @crelier.

[rinick]

oh, it's great to see modPow is implemented. I was looking for powMod and didn't realize it's already there.
but unfortunately modInverse doesn't use modPow, so that function's performance is still the same.

[rinick]

I updated modPow to native integer implementation, and the performance of the connection handshake in our application is almost the same.
I think the performance bottleneck is still in modInverse

[rinick]

attached file is a screenshot of the observatory, most dart cpu usage is caused by modInverse. and even in the 34% native code cpu usage, most of them are caused by bitint allocation from modInverse

---

Attachment:
screenshot.png (908.54 KB)

[DartBot]

This comment was originally written by @rinick

---

I implemented modInverse in sdk/runtime/lib/bigint.dart ( for now it only works when modulus is positive and odd)
https://github.com/IOT-DSA/sdk/blob/d626baee3c639eeea9751af17a8f97ed7dd93c3f/runtime/lib/bigint.dart#L1414

the above test case now takes 3.1 seconds on my PC, the cpu time cost on native code BigInt allocation is almost gone. but the total time spent by dart code is still 5 times slower than java :(

[iposva-google]

Set owner to @crelier.
Added Accepted label.

[crelier]

Rick,
Thanks for providing a bigint implementation of modInverse.
I am cleaning it up slightly and will add it to the Dart sdk. The gcd function, if considered useful, will follow later.
One question: how urgent is it for you guys to have a bigint implementation of modInverse supporting an even modulus?

Thanks,
Regis

[sethladd]

Thanks for the update, @crelier !

[rinick]

@crelier we don't need even modInverse at the momenet, but the algorithm in my implementation is same as this one
https://gist.github.com/rinick/9f1f285dc1e2a18d2d75
it shouldn't be difficult to implement it.

[rinick]

after this change, native modInverse is about 8 times faster than the custom modeInverse implementation.
the same test now takes about 950-1000ms on same PC,
https://gist.github.com/rinick/ce88242eb6e0a7c25063

[sethladd]

Thanks @crelier !

[sethladd]

Should we update the CHANGELOG for the SDK?

https://github.com/dart-lang/sdk/blob/master/CHANGELOG.md

cc @kevmoo

[crelier]

Only if these 4 cls are going to be cherry picked for 1.11 (decision is
with Ivan/Kasper/Rico):
https://codereview.chromium.org/1174513004/
https://codereview.chromium.org/1177873002/
https://codereview.chromium.org/1177063002/
https://codereview.chromium.org/1188843004/

Otherwise for 1.12, sure. The sdk change is this addition to class int:
/**

• Returns the modular multiplicative inverse of this integer
• modulo [modulus].
  *
• The [modulus] must be positive.
• Throws a RangeError if no modular inverse exists.
  */
  int modInverse(int modulus);

By the time we ship 1.12, we should also have a gcd method.

Cheers,
Regis

On Thu, Jun 18, 2015 at 11:30 AM, Seth Ladd notifications@github.com
wrote:

Should we update the CHANGELOG for the SDK?

https://github.com/dart-lang/sdk/blob/master/CHANGELOG.md

cc @kevmoo https://github.com/kevmoo

—
Reply to this email directly or view it on GitHub
#23502 (comment).

[rinick]

right now we are not able to use 1.12, since it doesn't support the dart2dart compiler. which means all the dart app deployed on our customer's site will have to be open sourced.

We really hope native modInverse feature can be part of 1.11

[crelier]

Ivan,

Please, see Rick's message below regarding the integration of modInverse
into 1.11.

Cheers,
Regis

On Thu, Jun 18, 2015 at 3:05 PM, Rick Zhou notifications@github.com wrote:

right now we are not able to use 1.12, since it doesn't support the
dart2dart compiler. which means all the dart app deployed on our customer's
site will have to be open sourced.

We really hope native modInverse feature can be part of 1.11

—
Reply to this email directly or view it on GitHub
#23502 (comment).