brick/math method for gmp_invert

[brick]

brick/math method for gmp_invert

[BenMorel]

Hi, thank you for the feature request and for providing working code! 👍

I'll take some time in the coming days to implement it in the library and add some tests.

Question: is there any value in providing gcdExtended() as a public method? Or is it just an implementation detail, with no real value on its own? I can see that Java's BigInteger has a modInverse() method, but no gcdExtended().

Finally, out of curiosity, I'd be interested to know what's your use case for modInverse()!

[BenMorel]

With no feedback received, I've moved forward with throwing a NegativeNumberException when the modulus is negative.

Now available as modInverse() and released as 0.8.16! ✨

[Spomky]

Hi,

I am happy to read that!
The method gcdExtended can be private. At the moment, I don't see any reason for using it directly.
In my context, this function is used for the computation of the Chinese Remainder Theorem (CRT) and especially for RSA encryption algorithm (the CRT reduces the computation time).

[BenMorel]

Hi, I just started implementing modInverse(), however it looks like the algorithm above fails for negative numbers:

gmp_invert('1234567890', '-19'); // 11
modInverse('1234567890', '-19'); // -8

gmp_invert('-1234567890', '19'); // 8
modInverse('-1234567890', '19'); // exception

gmp_invert('-1234567890', '-19'); // 8
modInverse('-1234567890', '-19'); // exception

Any idea how to fix it?

[BenMorel]

Any idea how to fix it?

No worries, I got the right result by borrowing this solution from the JDK.

[BenMorel]

Now the question is, what should we do when $m is negative? Java & Dart throw an exception, while gmp_invert() returns the value of modInverse($x, abs($m)). For now I've allowed negative modulo this way, but I'm not sure this is the right way the API should respond.

[BenMorel]

Otherwise looks good to me now. Could you please test the master branch (with and without GMP please!) and report any issue?

[Spomky]

Thank you! Sorry for the lack of feedback, but it works great.
Regards