Computational overhead

[SummonY]

hello,

Thank you for open source this Arbitrary-precision arithmetic.
When I use this to test paillier algorithm computational overhead, this function

func power(exponent: BigUInt, modulus: BigUInt) -> BigUInt{}

, the Java modPower computational overhead about 45ms but this function about 2.7s, cause some distortion.
The overhead test code at here: https://github.com/SummonY/Paillier_iOS

Can you help to optimize this function?

Thanks,
Summon Yang

[lorentey]

Interesting! I'm sure power can be improved; if you know a better algorithm than the right-to-left binary method it currently uses, I'd love a pointer to it. (Or even better, a pull request that implements it!)

2.7s vs 45ms seems a bit slow; is that a single function call? How many digits are there in the arguments?

[SummonY]

Yes, it is a single function call. They both use 1024 digits. Ok, I will see the source code of Java modPower when I have time.

[serieuxchat]

(Numbers corrected below) We would be interested in some performance improvements as well.
Trying to use the library for SRP protocol implementation, and, unfortunately, exponentiation of 2100 bit integers takes around 30 seconds on the Simulator and around 7 seconds on an iPhone 7 :-(

[lorentey]

Can you give a concrete example of an expression that is slow to compute?

[serieuxchat]

Here is an example of a long computation:

g.power(a, modulus: N)

g = 2

a = 50BF3A20EBF53DD3CA79620CE47928148A15B25B28D00B25687AA08ABFA455E8641416DF9985A08521D719177D83A33C3B64AD5DA4BC3320C499220D1EF83ABAC9A10F04C44262540DD39FE9ABC590F774906589C72DF4439F63C9D0CE3545B497A8DFB8BDEB97CE2F7521FDB1AD55CE3E23B3634FC1AD2F40E63D68BBB6C0B25526F1729DDFA5130DEFDD142EB8433020C9211D08D6F59B3C3C90BD8FB258BCDF5A2FF87F77E2C427517D55C5C2BE25B9BC923DEB9BEDA25B505E09C5EEA44D584FAF0648DF23A8757B6414B9BF95E5F51C3910C97E70134E6A16A23F8F6AE8068AE01A6E9CE090DD02F6C2EAD70D1918CBFAAB58C78DC565E0B2479D9E51AC

N = E13803363DBE8FC19F85E7DC6E8C26ACE2D78D722C1DE8A17746206BC436EC5BF20C0ACCE8BDACED9F22939836879E31D8F69ABFD7F357A1FA9DF31A3E5AF764E7D3D1CEAF48FF3C28F14004651FDB2D81C0B4E0DE6FD1EA7975BB868AFF65CB163F29205992ED2D80A7055A5BFA8C96456D74E6BA19ECCD4E3F3AE31B2D368DBC627EC3F701423586F77BA76E5A552DBA821DF7241B4FF43E7BDD5BCC55EEB2DBE2120B33F3D4A0EF4A3EA5B9EF8C2DC33447CEC468DD86B7AA23E3005305007433D51EC866228326B38EBED72C582CE121E95544FA08703B51E73F4EED91C26851573D01DDF189C710C29E9DBB4ED382942AF8590BB7AE33BF04FF40D8A003

[lorentey]

Awesome, thank you.

[serieuxchat]

Tried the same operation with imath (https://github.com/creachadair/imath/blob/master/imath.h) - takes 0.15 ms (48 times faster)

[lorentey]

Are you using Debug or Release builds? I can reproduce multi-second calculations only in Debug mode; in Release builds, the example you gave takes about 0.23 s on my CPU. (Unoptimized builds are 20x-40x slower.)

Also, is the imath result 0.15 ms or 0.15 s? (0.15 ms would cause a great deal of concern to me; but your quoted 48x slowdown indicates 0.15s might be the correct value.)

[lorentey]

I'm closing this issue as it seems the reported performance problems were measured in Debug (i.e., non-optimized) builds.

Please reopen the issue if you're able to reproduce slow performance in optimized builds.