Optimal implementation of cryptographic function of exponentiation by modulus

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.

  1. seems num-bigint does not have single function implementing ( ( a ^ b ) % c ) optimally
  2. 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?

Please check out the modpow method.


Thank you, Alice. Seems there is no way to do it zero-copy with num. That's pity.

Try ibig::modular.

The Modulo::pow method uses not zero allocations, but a small, constant number of allocations.

1 Like

Is it possible to reuse vector of bytes?

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.

1 Like

I see. Thank you :slight_smile:

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.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.