modular arithmetic

[kunerd]

I'm working on a Rust implementation of Paillier cryptosystem (https://github.com/kunerd/rpaillier). After I started I realised a lag of fundamental big number arithmetic functions like mod_pow and mod_inverse. At the moment there is also no way to generate probably primes. So I started to implement them by myself.

Now I want to ask, if there is an interest to add these algorithms to this project?

current state of my implementation:

• mod_pow: Implementation of LR-k-ary algorithm as described in the "Handbook of Applied Cryptography, 14.82".
• mod_inverse: Implementation of "Extended Euclidean Algorithm" as described by Knuth

[Aatch]

I'm not against them. Both look like like good candidates to implement in the low-level part of the library, especially if I decide to implement modular arbitrary-precision integers as a separate type.

The low-level part is mostly all unsafe code and raw pointers, but it shouldn't be too difficult to work with.

[kunerd]

Currently I have transformed my num::bigint mod_pow extension to use ramp. It can be found here: https://github.com/kunerd/rpaillier/blob/master/src/bigint_extensions.rs

But I don't know really how to do this in the low level part, maybe you can give me some hints like possible function signatures or something like that.

By the way, the implementation using ramps Int is much much faster than the same implementation using nums BigInt, so thanks for this great and fast library.

[rozbb]

a low-level extended gcd function like ll::gcd would be much appreciated, if you'd like to contribute one. Otherwise, I may do that in the future.

[kunerd]

This one already exists, or did I miss something? https://github.com/Aatch/ramp/blob/master/src/ll/gcd.rs

[rozbb]

That's a GCD implementation. The extended GCD egcd(x,y) returns integers (a,b,g) such that g = gcd(x,y) and x*a + y*b = g. It shouldn't be too hard to copy most of the ll::gcd code for an egcd function.

[kunerd]

Oh sorry, I missed the extended keyword. Unfortunately I haven't enough time to do further work on ramp, so feel free to take over.