I try to use the num-bigint module to implement such a formula ( ( a ^ b ) % c ), where a, b and c are integers of an arbitrary length and ^ the operation of exponentiation, and % the operation of finding the reminder. But I faced two problems.
seems num-bigint does not have single function implementing ( ( a ^ b ) % c ) optimally
num-bigint is not zero-copy. To make an instance of BigUint you need to make a copy of the original data Vec <u8>, and then copy the result again from BigUint to Vec <u8>.
Is it possible to solve these problems within this module? If not, please advise another module?
Not directly. You have to convert using UBig::from_le_bytes or UBig::from_be_bytes, and then to Modulo in an appropriate ModuloRing.
If your goal is to do this completely without using any additional memory then it's going to be very hard or impossible. Modular exponentiation requires some scratch memory space.
For large exponents, the performance cost of these conversions is going to be negligible compared to the actual modular exponentiation. ibig::modular does the actual exponentiaion in place once all the memory is allocated. I think num-bigint will perform a lot of additional allocations as part of the exponentiation algorithm.
On practice it might. In theory not that hard. If data is little-ended then and it is aligned with usize then it's enough to reinterpret original buffer without copying it. Anyway num currently does not comply Rust's: "Fast, Reliable, Productive . Pick Three ".
Even if you wrote an exponentiation function that could reuse Vec's memory for the input and output numbers, it would still have to allocate some scratch memory for intermediate values while calculating.
Also, exponentiation is a pretty expensive operation. Copying the input is a very cheap operation compared to this.
